A201198 Triangle version of the array w(N,L) of the average number of round trips of length L on Laguerre graphs L_N.

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

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

Table of n, a(n) for n=0..54.

Eric W. Weisstein, from MathWorld: Laguerre Polynomial.

Wolfdieter Lang, Counting walks on Jacobi graphs: an application of orthogonal polynomials.

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

A201199 (closed Laguerre graphs).

Sequence in context: A332405 A332403 A263341 * A349933 A120258 A201922

Adjacent sequences: A201195 A201196 A201197 * A201199 A201200 A201201

Keyword

nonn,easy,walk,tabl

Author

Wolfdieter Lang, Nov 30 2011

Status

approved