%I #12 Aug 27 2019 23:34:02
%S 1,1,2,1,4,3,1,18,9,4,1,76,53,16,5,1,322,357,120,25,6,1,1364,2489,
%T 1024,233,36,7,1,5778,17509,9424,2545,404,49,8,1,24476,123449,89536,
%U 29985,5400,645,64,9,1,103682,870893,862560,367505,78392,10213,968,81,10
%N Triangle version of the array w(N,L) of the total number of round trips of length L on closed Laguerre graphs Lc_N.
%C For Laguerre graphs (open and closed ones) see the W. Lang link on Jacobi graphs under A201198. There one also finds a sketch of the closed Laguerre graph Lc_4 as Fig.4.
%C The total number of round trips on the closed Laguerre graph Lc_N, for N>=3, with N vertices N^2 loops, binomial(N,2) lines between neighboring vertices and two lines between the first and the last vertex (in total (3*N-1)*N/2+2 = (3*N^2-N+4)/2 lines) is w(N,L) = sum(w(N,L;p_n->p_n),n=1..N) = Trace((L_N)^L) = sum((x_n^{(N)})^L,n=1..N), with the N x N symmetric adjacency matrix, also called Lc_N, having non-vanishing elements (Lc_N)[n,n] = 2*n-1, n=1..N, (Lc_N)[n,n+1] = (Lc_N)[n+1,n] = n, n=1..N-1, and (Lc_N)[1,N]= 2=(Lc_N)[N,1]. The eigenvalues of Lc_N are x_n^{(N)}. They are the zeros of the characteristic polynomial Lac_N(x):=Det(x*1_N -Lc_N) with the N x N unit matrix 1_N. These are the polynomials Lac_N(x) = La(N,x) - 4*La1(N-2,x) - 4*(N-1)!, with the ordinary monic Laguerre polynomials La(N,x) with coefficient array given by A021009(n,m)*(-1)^n and the first associated monic Laguerre polynomials La1(N-2,x) with coefficient array given by A199577(n,m). For N=1 one has Lc_1=L_1 (Laguerre graph with one vertex and one loop) with L_1(x)=x-1, and for N=2 one has a graph where one vertex has one loop, the other three, and there are two lines joining these vertices, hence Lc_2(x)= x^2-4*x-1.
%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),K>=0, N=1,...,K+1, with w(N,L) the total number of round trips of length L on the closed Laguerre graph Lc_N described above in the comment section.
%F The o.g.f. of w(N,L) is: G(N,x)=y*(d/dx)Lac_N(x)/Lac_N(x) with y=1/x.
%F The characteristic polynomial Lac_N(x) has also been given in the comment section above.
%e The array w(N,L) starts:
%e N\L 0 1 2 3 4 5 6 ...
%e 1: 1 1 1 1 1 1 1
%e 2: 2 4 12 40 136 464 1584
%e 3: 3 9 53 357 2489 17509 123449
%e 4: 4 16 120 1024 9424 89536 862560
%e 5: 5 25 233 2545 29985 367505 4599521
%e 6: 6 36 404 5400 78392 1188336 18460016
%e 7: 7 49 645 10213 176473 3195829 59473593
%e 8: 8 64 968 17728 355536 7493504 162671840
%e 9: 9 81 1385 28809 657953 15826041 392792273
%e ...The triangle a(K,N) = w(N,K-N+1) starts:
%e K\N 1 2 3 4 5 6 7 8 9..
%e 0: 1
%e 1: 1 2
%e 2: 1 4 3
%e 3: 1 18 9 4
%e 4: 1 76 53 16 5
%e 5: 1 322 357 120 25 6
%e 6: 1 1364 2489 1024 233 36 7
%e 7: 1 5778 17509 9424 2545 404 49 8
%e 8: 1 24476 123449 89536 29985 5400 645 64 9
%e ...
%e For the graph Lc_4, shown in the W. Lang link as Figure 4, the counting for round trips of length L=2 for each of the four vertices V_i, i=1..4, read from left to right, is as follows.
%e V_1: 1+1+(1+1+2*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))+(1+1+2*1),
%e this sums to the total number w(4,2)= 120 = a(5,4).
%e Compared to the open L_4 graph (see the corresponding A201198 entry 4*28 = 112) one has to add 2*(1+1+2*1)=8 from the new two lines joining V_1 and V_4.
%Y Cf. A201198 (open Laguerre graphs).
%K nonn,easy,walk,tabl
%O 0,3
%A _Wolfdieter Lang_, Nov 30 2011
|