login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I #37 Oct 22 2022 16:19:36

%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="http://dx.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

%O 0,8

%A _Wolfdieter Lang_, Nov 08 2011