The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #38 May 30 2026 16:40:35
%S 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,
%T 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,
%U 0,1,0,1024,170,128,14,22,0,6,0,2,0,1,0,0
%N 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.
%C 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).
%C 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),
%C 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.
%H Wolfdieter Lang, <a href="https://doi.org/10.1016/S0377-0427(97)00240-9">On sums of powers of zeros of polynomials</a>, J. Comp. Appl. Math. 89 (1998) 237-256.
%F 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.
%F 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.
%F O.g.f. G(N,x) for w(N,L): for N >= 2:
%F 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
%F 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)).
%e The triangle a(K,N) = w(N,K-N+1) begins
%e K\N 1 2 3 4 5 6 7 8 9 10 ...
%e 0: 1
%e 1: 0 1
%e 2: 0 0 1
%e 3: 0 4 0 1
%e 4: 0 0 2 0 1
%e 5: 0 16 2 2 0 1
%e 6: 0 0 6 0 2 0 1
%e 7: 0 64 10 8 0 2 0 1
%e 8: 0 0 22 0 6 0 2 0 1
%e 9: 0 256 42 32 2 6 0 2 0 1
%e ...
%e The array w(N,L) begins
%e N\L 0 1 2 3 4 5 6 7 8 9 10 ...
%e 1: 1 0 0 0 0 0 0 0 0 0 0
%e 2: 1 0 4 0 16 0 64 0 256 0 1024
%e 3: 1 0 2 2 6 10 22 42 86 170 342
%e 4: 1 0 2 0 8 0 32 0 128 0 512
%e 5: 1 0 2 0 6 2 20 14 70 72 254
%e 6: 1 0 2 0 6 0 22 0 86 0 342
%e 7: 1 0 2 0 6 0 20 2 70 18 252
%e 8: 1 0 2 0 6 0 20 0 72 0 272
%e 9: 1 0 2 0 6 0 20 0 70 2 252
%e 10: 1 0 2 0 6 0 20 0 70 0 254
%e ...
%e w(1,0)=1, one vertex considered.
%e 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.
%e w(3,4)=6 from the six return paths 12121, 13131, 12131, 13121, 12321 and 13231.
%e w(5,5)=2 from the two return paths 123451 and 154321.
%Y Cf. A198633 (walks on the P_N graph).
%Y The N=1,...,10 sequences are A000007, A199572, A078008, A199573, A054877, A047849, A094659, A063376, A094233, A095929.
%K nonn,easy,walk,tabl,changed
%O 0,8
%A _Wolfdieter Lang_, Nov 08 2011