|
| |
|
|
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).
|
|
9
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
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).
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)
|
|
|
LINKS
|
|
|
|
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
|
|
|
EXAMPLE
|
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.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
