A199571 Table version of the array of number of round trips of length L from any of the N vertices of the cycle graph C_N.

1, 0, 1, 0, 0, 1, 0, 4, 0, 1, 0, 0, 2, 0, 1, 0, 16, 2, 2, 0, 1, 0, 0, 6, 0, 2, 0, 1, 0, 64, 10, 8, 0, 2, 0, 1, 0, 0, 22, 0, 6, 0, 2, 0, 1, 0, 256, 42, 32, 2, 6, 0, 2, 0, 1, 0, 0, 86, 0, 20, 0, 6, 0, 2, 0, 1, 0, 1024, 170, 128, 14, 22, 0, 6, 0, 2, 0, 1, 0, 0

Offset: 0

Author

Wolfdieter Lang, Nov 08 2011

Keywords

• nonn
• easy
• walk
• tabl

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.

Examples

			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.
		

Links

• Wolfdieter Lang, On sums of powers of zeros of polynomials, J. Comp. Appl. Math. 89 (1998) 237-256.

Crossrefs

Cf. A198633 (walks on the P_N graph).

The N=1,...,10 sequences are A000007, A199572, A078008, A199573, A054877, A047849, A094659, A063376, A094233, A095929.

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