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

%I #26 Dec 18 2017 22:46:59

%S 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,

%T 1,792,3303,2056,485,66,7,1,1,2704,20691,18784,5645,876,91,8,1,1,9232,

%U 129951,174112,68245,12636,1435,120,9,1

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

%C 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.

%C 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.

%H Eric W. Weisstein, from MathWorld: <a href="http://mathworld.wolfram.com/LaguerrePolynomial.html">Laguerre Polynomial.</a>

%H Wolfdieter Lang, <a href="/A201198/a201198_1.pdf">Counting walks on Jacobi graphs: an application of orthogonal polynomials.</a>

%F 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).

%F The definition of the graph L_N is given as a comment above.

%F 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

%F 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).

%e The array w(N,L) starts:

%e N\L 0 1 2 4 5 6 7 ...

%e 1: 1 1 1 1 1 1 1 1

%e 2: 1 2 6 20 68 232 792 2704

%e 3: 1 3 15 87 531 3303 20691 129951

%e 4: 1 4 28 232 2056 18784 174112 1625152

%e 5: 1 5 45 485 5645 68245 841725 10495525

%e 6: 1 6 66 876 12636 190296 2935656 45927216

%e 7: 1 7 91 1435 24703 445627 8259727 155635459

%e 8: 1 8 120 2192 43856 922048 19964736 440311936

%e 9: 1 9 153 3177 72441 1739529 43098777 1089331497

%e ...

%e The triangle a(K,N) = w(N,K-N+1) starts:

%e K\N 1 2 3 4 5 6 7 8 9 10 ...

%e 0: 1

%e 1: 1 1

%e 2: 1 2 1

%e 3: 1 6 3 1

%e 4: 1 20 15 4 1

%e 5: 1 68 87 28 5 1

%e 6: 1 232 531 232 45 6 1

%e 7: 1 792 3303 2056 485 66 7 1

%e 8: 1 2704 20691 18784 5645 876 91 8 1

%e 9: 1 9232 129951 174112 68245 12636 1435 120 9 1

%e ...

%e 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.

%e V_1: 1+1, V_2: 3+2*binomial(3,2)+1+(1+1+2*1),

%e V_3: 5+2*binomial(5,2)+(1+1+2*1)+(3+2*binomial(3,2)),

%e V_4: 7+2*binomial(7,2)+(3+2*binomial(3,2)),

%e this sums to 112, hence the average number is w(4,2)= 112/4 = 28 = a(5,4).

%Y A201199 (closed Laguerre graphs).

%K nonn,easy,walk,tabl

%O 0,5

%A _Wolfdieter Lang_, Nov 30 2011