OFFSET
0,8
COMMENTS
Let w(N,L) be the number of return paths (round trip walks) of length L >= 0 from any vertex of the cycle graph C_N, N >= 1. (Due to cyclic symmetry, this array w(N,L) is independent of the start vertex.) w(N,L) = trace(AC(N)^L)/N = Sum_{k=0..N-1} x^{(N)}_k, with the N X N adjacency matrix AC(N) of the cycle graph C_N, and x^{(N)}_k are the zeros of the characteristic polynomial C(N,x) of AC(N). See A198637 for the coefficient triangle for C(N,x). C(N,x) = 2*(T(N,x/2)-1) for N >= 2. These zeros are x^{(N)}_k = 2*cos(2*Pi*k/N), N >= 2 (from T(N,x/2)=1). For N=1 one has C(1,x)=x with x^{(1)}_0 = 0. This sum formula for w(n,L) has been given in a comment to A054877 (N=5 case) by H. Kociemba. For N=1 one uses 0^0 := 1 to obtain w(1,L) = delta(L,0) (Kronecker's delta-symbol).
The o.g.f. G(N,x) := Sum_{L>=0} w(N,L)*x^L is, by a general result on moments of zeros of polynomials (see the W. Lang reference, theorem 5, p. 244),
y*(d/dx)C(N,x)/(N*C(N,x)), with y=1/x. This becomes for N >= 2: G(N,x) = y*S(N-1,y)/(2*T(N,y/2)-1) with y=1/x. For N=1 one has G(1,x)=1 (not 1/(1-2*x)). In the formula section this N >= 2 result is given explicitly, using the Binet-de Moivre form of the S- and T-polynomials.
LINKS
Wolfdieter Lang, On sums of powers of zeros of polynomials, J. Comp. Appl. Math. 89 (1998) 237-256.
FORMULA
a(K,L) = w(N,K-N+1), K >= 0, n=1,...,K+1, with w(N,L) defined as return walk numbers of length L of the cycle graph C_N in the comment section above.
w(N,L) = Sum_{k=0..N-1} (2*cos(2*Pi*k)/N)^L, N >= 2. For N=1 one has w(1,0)=1 and w(1,L)=0 if L >= 1.
O.g.f. G(N,x) for w(N,L): for N >= 2:
y*S(N-1,y)/(2*(T(N,y/2)-1)) with y=1/x, and for N=1 one has G(1,x)=1. This can, for N >= 2, be written as
G(N,x) = sinh(N*log(2*x/(1-sqrt(1-(2*x)^2))))/(sqrt(1-(2*x)^2)*(cosh(N*log(2*x/(1-sqrt(1-(2*x)^2))))-1)).
EXAMPLE
The triangle a(K,N) = w(N,K-N+1) begins
K\N 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 0 1
2: 0 0 1
3: 0 4 0 1
4: 0 0 2 0 1
5: 0 16 2 2 0 1
6: 0 0 6 0 2 0 1
7: 0 64 10 8 0 2 0 1
8: 0 0 22 0 6 0 2 0 1
9: 0 256 42 32 2 6 0 2 0 1
...
The array w(N,L) begins
N\L 0 1 2 3 4 5 6 7 8 9 10 ...
1: 1 0 0 0 0 0 0 0 0 0 0
2: 1 0 4 0 16 0 64 0 256 0 1024
3: 1 0 2 2 6 10 22 42 86 170 342
4: 1 0 2 0 8 0 32 0 128 0 512
5: 1 0 2 0 6 2 20 14 70 72 254
6: 1 0 2 0 6 0 22 0 86 0 342
7: 1 0 2 0 6 0 20 2 70 18 252
8: 1 0 2 0 6 0 20 0 72 0 272
9: 1 0 2 0 6 0 20 0 70 2 252
10: 1 0 2 0 6 0 20 0 70 0 254
...
w(1,0)=1, one vertex considered.
For N >= 2 the vertices (nodes) of C_N are numbered consecutively in the positive sense by 1,2,...,N. W.l.o.g. one can take the vertex number 1 as start of the return trip.
w(3,4)=6 from the six return paths 12121, 13131, 12131, 13121, 12321 and 13231.
w(5,5)=2 from the two return paths 123451 and 154321.
CROSSREFS
KEYWORD
AUTHOR
Wolfdieter Lang, Nov 08 2011
STATUS
approved