|
| |
|
|
A201198
|
|
Triangle version of the array w(N,L) of the average number of round trips of length L on Laguerre graphs L_N.
|
|
6
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 6, 3, 1, 1, 20, 15, 4, 1, 1, 68, 87, 28, 5, 1, 1, 232, 531, 232, 45, 6, 1, 1, 792, 3303, 2056, 485, 66, 7, 1, 1, 2704, 20691, 18784, 5645, 876, 91, 8, 1, 1, 9232, 129951, 174112, 68245, 12636, 1435, 120, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
For Laguerre graphs see the W. Lang link on Jacobi graphs (named after the symmetric tridiagonal Jacobi adjacency matrices, related to orthogonal polynomials). There one also finds a sketch of the Laguerre graph L_4 in Fig. 3.
The average number of round trips for the Laguerre graph L_N with N vertices, N^2 loops and binomial(N,2) lines between neighboring vertices (in total (3*N-1)*N/2 lines) is w(N,L) = sum(w(N,L;p_n->p_n), n=1..N)/N = Trace((L_N)^L)/N = sum((x_n^{(N)})^L,n = 1..N)/N, with the N x N tridiagonal symmetric adjacency matrix L_N, having non-vanishing elements (L_N)[n,n] = 2*n-1, n=1..N, (L_N)[n,n+1] = (L_N)[n+1,n] = n, n=1..N-1. The eigenvalues of L_N are x_n^{(N)}. They are the zeros of the characteristic polynomial La_N(x):=Det(x*1_N -L_N) with the N x N unit matrix 1_N. These are the ordinary monic Laguerre polynomials with coefficient triangle given in A021009(n,m)*(-1)^n.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(K,N) = w(N,K-N+1), with w(N,L) the total number of round trips of length L on the Laguerre graph L_N divided by N (average length L round trip numbers).
The definition of the graph L_N is given as a comment above.
The o.g.f. of w(N,L) is G(N,x) = (1/N)*y*(d/dx)La_N(x)/La_N(x)) with y=1/x. This can be written as
G(N,x)= 1 + N*La_{N-1}(1/x)/La_N(1/x), where La_N(x) are the monic Laguerre polynomials (see a comment above).
|
|
|
EXAMPLE
|
The array w(N,L) starts:
N\L 0 1 2 4 5 6 7 ...
1: 1 1 1 1 1 1 1 1
2: 1 2 6 20 68 232 792 2704
3: 1 3 15 87 531 3303 20691 129951
4: 1 4 28 232 2056 18784 174112 1625152
5: 1 5 45 485 5645 68245 841725 10495525
6: 1 6 66 876 12636 190296 2935656 45927216
7: 1 7 91 1435 24703 445627 8259727 155635459
8: 1 8 120 2192 43856 922048 19964736 440311936
9: 1 9 153 3177 72441 1739529 43098777 1089331497
...
The triangle a(K,N) = w(N,K-N+1) starts:
K\N 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 1 1
2: 1 2 1
3: 1 6 3 1
4: 1 20 15 4 1
5: 1 68 87 28 5 1
6: 1 232 531 232 45 6 1
7: 1 792 3303 2056 485 66 7 1
8: 1 2704 20691 18784 5645 876 91 8 1
9: 1 9232 129951 174112 68245 12636 1435 120 9 1
...
For the graph L_4, shown in the W. Lang link as Figure 3, the counting for round trips of length L=2 for each of the four vertices V_i, i=1..4, reads, from left to right, as follows.
V_1: 1+1, V_2: 3+2*binomial(3,2)+1+(1+1+2*1),
V_3: 5+2*binomial(5,2)+(1+1+2*1)+(3+2*binomial(3,2)),
V_4: 7+2*binomial(7,2)+(3+2*binomial(3,2)),
this sums to 112, hence the average number is w(4,2)= 112/4 = 28 = a(5,4).
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
