A201199 -id:A201199 - cp's OEIS frontend

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

Wolfdieter Lang, Nov 30 2011

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.

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

Eric W. Weisstein, from MathWorld: Laguerre Polynomial.
Wolfdieter Lang, Counting walks on Jacobi graphs: an application of orthogonal polynomials.

A201199 (closed Laguerre graphs).

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

A199579 Average number of round trips of length n on the Laguerre graph L_4.

Original entry on oeis.org

1, 4, 28, 232, 2056, 18784, 174112, 1625152, 15220288, 142777600, 1340416768, 12588825088, 118252556800, 1110898849792, 10436554713088, 98050271875072, 921180638875648, 8654518327066624, 81309636020912128

Offset: 0

Wolfdieter Lang, Dec 02 2011

See the general array and triangle for the average number of round trips of length L on (open) Laguerre graphs L_N given in A201198. Here a(n) = w(4,L=n), n>=0, the fourth row in this array. In the corresponding triangle  this is the column no. N=4 without leading zeros: a(n) = A201198(n+3,4), n>=0.
For a sketch of this Laguerre graph L_4 see Figure 3 of the W. Lang link. The o.g.f. is also given there.
By definition the number of zero length round trips of length 0 for a vertex is put to 1 in order to count vertices.

			n=0: a(0)=1 because the average number of vertices is 4/4=1.
a(1)= (1+3+5+7)/4 = 4, from the sum of the self-loops of L_4 divided by the number of vertices 4.
The counting for n=2, a(2)= 112/4 = 28, has been given as an example to A201198.

G. C. Greubel, Table of n, a(n) for n = 0..450
Wolfdieter Lang, Counting walks on Jacobi graphs: an application of orthogonal polynomials.
Index entries for linear recurrences with constant coefficients, signature (16,-72,96,-24)

Cf. A201198, A201199 (closed Laguerre graphs), A201200 (closed L_4 graph).

I:=[1, 4, 28, 232]; [n le 4 select I[n] else 16*Self(n-1) - 72*Self(n-2) + 96*Self(n-3) -24*Self(n-4): n in [1..30]]; // G. C. Greubel, May 14 2018

LinearRecurrence[{16, -72, 96, -24}, {1, 4, 28, 232}, 50] (* G. C. Greubel, May 14 2018 *)

x='x+O('x^30); Vec((1-12*x+36*x^2-24*x^3)/(1-16*x+72*x^2- 96*x^3 +24*x^4)) \\ G. C. Greubel, May 14 2018

a(n) = A201198(n+3,4), n>=0.

O.g.f.: (1-12*x+36*x^2-24*x^3)/(1-16*x+72*x^2-96*x^3+24*x^4).

A201200 Total number of round trips of length n on the closed Laguerre graph Lc_4 divided by 4.

Original entry on oeis.org

1, 4, 30, 256, 2356, 22384, 215640, 2090176, 20315536, 197702464, 1925042400, 18749072896, 182629124416, 1779030655744, 17330352562560, 168824779580416, 1644626142474496, 16021353180980224, 156074394613317120, 1520422660926324736

Offset: 0

Wolfdieter Lang, Dec 02 2011

For the general array and triangle for the total number of round trips of length L on closed Laguerre graphs Lc_N see A201199. Here a(n)=w(4,L=n)/4, n>=0, the fourth row of this array divided by 4. In the corresponding triangle a(n) = A201199(n+3,4)/4, n>=0.
For a sketch of the closed Laguerre graph Lc_4 see Figure 4 of the given W. Lang link. The o.g.f. is also found there.
By definition the number of length 0 round trips for a vertex is put to 1 in order to count vertices.
The average number of round trips of length n on a closed Laguerre graph Lc_N is in general a fraction. Therefore A201199 tabulates the total number of round trips.

Colin Barker, Table of n, a(n) for n = 0..1000
Wolfdieter Lang, Counting walks on Jacobi graphs: an application of orthogonal polynomials.
Index entries for linear recurrences with constant coefficients, signature (16,-68,64,44).

Cf. A201199, A201198 (open Laguerre graphs). A199579 (open L_4 graph).

I:=[1, 4, 30, 256]; [n le 4 select I[n] else 16*Self(n-1) - 68*Self(n-2) + 64*Self(n-3) + 44*Self(n-4): n in [1..30]]; // G. C. Greubel, May 13 2018

LinearRecurrence[{16,-68,64,44}, {1, 4, 30, 256}, 30] (* G. C. Greubel, May 13 2018 *)

Vec((1-8*x)*(1-4*x+2*x^2)/((1-4*x-2*x^2)*(1-12*x+22*x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

a(n) = A201199(n+3,4)/4, n>=0.
O.g.f.: (8*x-1)*(2*x^2-4*x+1) / ( (22*x^2-12*x+1)*(2*x^2+4*x-1) ).
From Colin Barker, Apr 27 2016: (Start)
a(n) = 16*a(n-1)-68*a(n-2)+64*a(n-3)+44*a(n-4) for n>3.
a(n) = ((2-sqrt(6))^n+(2+sqrt(6))^n+(6-sqrt(14))^n+(6+sqrt(14))^n)/4.
(End)
E.g.f.: (exp((2-sqrt(6))*x) + exp((2+sqrt(6))*x) + exp((6-sqrt(14))*x) + exp((6+sqrt(14))*x))/4. - Ilya Gutkovskiy, Apr 27 2016

Typo in formula fixed by Colin Barker, Apr 27 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A199579 Average number of round trips of length n on the Laguerre graph L_4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A201200 Total number of round trips of length n on the closed Laguerre graph Lc_4 divided by 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions