A198632 Triangle version of the array of the number of closed paths of even length on the graph P_n (n vertices, n-1 edges).

1, 0, 2, 0, 2, 3, 0, 2, 4, 4, 0, 2, 8, 6, 5, 0, 2, 16, 14, 8, 6, 0, 2, 32, 36, 20, 10, 7, 0, 2, 64, 94, 56, 26, 12, 8, 0, 2, 128, 246, 164, 76, 32, 14, 9, 0, 2, 256, 644, 488, 234, 96, 38, 16, 10, 0, 2, 512, 1686, 1460, 740, 304, 116, 44, 18, 11, 0, 2, 1024, 4414, 4376, 2372, 992, 374, 136, 50, 20, 12, 0, 2, 2048, 11556, 13124, 7654, 3296, 1244, 444, 156, 56, 22, 13

Offset: 0

Author

Wolfdieter Lang, Nov 02 2011

Keywords

• nonn
• easy
• tabl

Comments

This array is an example of counting walks on a graph whose adjacency matrix is given by a special symmetric tridiagonal matrix with nonnegative integer entries, appropriate for orthogonal polynomials. These are quadratic Jacobi matrices J_n with nonnegative entries. The corresponding graphs could be called Jacobi graphs. Here Chebyshev S-polynomials (coefficients A049310) are considered, which belong to the Jacobi class of the classical orthogonal polynomial systems. The corresponding graph has adjacency matrix [[0,1,0,...],[1,0,1,...],[0,1,0,1,...]...[0,...0,1,0]] (n rows and n columns), with characteristic polynomial S(n,x) (see also a comment by Michael Somos on A049310).

w(n,l;p_k->p_m) = ((J_n)^l)(k,m) is the number of walks of length l from vertex p_k to vertex p_m on such a Jacobi graph. w(n,0; p_k->p_m) = delta(k,m), with the Kronecker symbol delta. The total number of closed walks of length l is w(n,l):=Sum_{i=1..n} w(n,l; p_i->p_i) = trace(J_n^l), which is the l-th power sum of the eigenvalues of J_n, i.e., the zeros of the characteristic polynomial for J_n. There are theorems for the o.g.f. of the normalized power sums of these zeros. See, e.g., the given W. Lang reference, p. 244. This results for the S-polynomial in the o.g.f. G(n,x) = Sum_{l=0..infinity} w(n,l)*x^l = y*(d/dy)S(n,y)/S(y) with y=1/x. This can be rewritten in the form given in the formula section (this results from eq. (3.8b) of the W. Lang reference, and in eq. (3.8d) it should be coth, not tanh).

From Wolfdieter Lang, Oct 10 2012: (Start)

For an accompanying paper on path counting on Jacobi graphs see the W. Lang link under A201198.

The total number of round trips of length L on the graph P_n, taken per site, becomes for n -> infinity A126869(L). See the just mentioned link, p. 8. This limit is derived from the limit of G(n,x)/n with G(n,x) given in the formula section.

Thanks go to Clyde P. Kruskal for asking a question which led to this comment.

(End)

Examples

			The array w(n,2*k) is
n\k  0  1   2   3   4    5    6     7     8      9 ...
1:   1  0   0   0   0    0    0     0     0      0
2:   2  2   2   2   2    2    2     2     2      2
3:   3  4   8  16  32   64  128   256   512   1024
4:   4  6  14  36  94  246  644  1686  4414  11556
5:   5  8  20  56 164  488 1460  4376 13124  39368
6:   6 10  26  76 234  740 2372  7654 24778  80338
7:   7 12  32  96 304  992 3296 11072 37440 127104
8:   8 14  38 116 374 1244 4220 14504 50294 175454
9:   9 16  44 136 444 1496 5144 17936 63164 224056
...
The triangle is
k\n 1  2    3    4    5    6   7    8   9 10 11 12 ...
0:  1
1:  0  2
2:  0  2    3
3:  0  2    4    4
4:  0  2    8    6    5
5:  0  2   16   14    8    6
6:  0  2   32   36   20   10   7
7:  0  2   64   94   56   26  12    8
8:  0  2  128  246  164   76  32   14   9
9:  0  2  256  644  488  234  96   38  16 10
10: 0  2  512 1686 1460  740 304  116  44 18 11
11: 0  2 1024 4414 4376 2372 992  374 136 50 20 12
...
n=3, l=2*k = 4: graph P_3 as 1-2-3, with eight walks of length 4, namely 12121, 12321, 21212, 23232, 21232, 23212, 32323 and 32123.
		

Links

• S. Barbero, Dickson Polynomials, Chebyshev Polynomials, and Some Conjectures of Jeffery, Journal of Integer Sequences, 17 (2014), #14.3.8.
• S. Barbero, U. Cerruti, N. Murru, Identities Involving Zeros of Ramanujan and Shanks Cubic Polynomials, J. Integer Seq., Vol. 16 (2013), Article 13.8.1.
• Carlos M. da Fonseca, M. Lawrence Glasser, Victor Kowalenko, Basic trigonometric power sums with applications, arXiv:1601.07839 [math.NT], 2016. See Theorem 5.1.
• W. Lang, On sums of powers of zeros of polynomials, J. Comp. Appl. Math., 89 (1998) 237-256.

Crossrefs

Column sequences: A000007, 2*A000012, A198633, 2*A005248, A198635, ...

Formula

a(k,n)=w(n,2*(k-n+2)), the total number of closed walks (paths) of length 2*(k-n+2) on the graph P_n, which looks like o-o-o...-o, with n vertices (nodes) and n-1 edges (lines), k+1>=n>=1.

O.g.f. G(n,x) for w(n,l), which vanishes for odd l, is

((n+1)*coth((n+1)*log((2*x)/(1-sqrt(1-(2*x)^2)))) - 1/sqrt(1-(2*x)^2))/sqrt(1-(2*x)^2). See the comment above for a version with Chebyshev S-polynomials.

Conjecture: For the array w(n,2*k) in the example below, w(2*q,2*k)/2 = A185095(q,k), q >= 1, k >= 0. - L. Edson Jeffery, Nov 23 2013