A094233 -id:A094233 - cp's OEIS frontend

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

Wolfdieter Lang, Nov 08 2011

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.

			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.

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

Cf. A198633 (walks on the P_N graph).

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

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

A095929 Number of closed walks of length 2n at a vertex of the cyclic graph on 10 nodes C_10.

Original entry on oeis.org

1, 2, 6, 20, 70, 254, 948, 3614, 13990, 54740, 215766, 854702, 3396916, 13530350, 53971350, 215492564, 860941798, 3441074654, 13757249460, 55010542910, 219993856006, 879848932052, 3519064567926, 14075391282830, 56299295324980, 225191238869774

Offset: 0

Herbert Kociemba, Jul 12 2004

In general 2^n/m*Sum_{r=0..m-1} cos(2Pi*k*r/m)*cos(2Pi*r/m)^n is the number of walks of length n between two nodes at distance k in the cycle graph C_m. Here we have m=10 and k=0.

The number of round trips of odd length is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011

			a(2)=6 from the six round trips from, say, vertex no. 1: 12121, 1(10)1(10)1, 121(10)1, 1(10)121, 12321 and 1(10)9(10)1. - _Wolfdieter Lang_, Nov 08 2011

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,-13,4).

Cf. A094233, A199571.

f[n_]:=FullSimplify[TrigToExp[(4^n/10)Sum[Cos[Pi*k/5]^(2n), {k, 0, 9}]]];Table[f[n], {n, 0, 35}]
LinearRecurrence[{7,-13,4},{1,2,6},30] (* Harvey P. Dale, Dec 09 2018 *)

Vec((1-5*x+5*x^2)/((1-4*x)*(1-3*x+x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

a(n) = 4^n/10*Sum_{r=0..9} cos(Pi*r/5)^(2*n).
a(n) = 7*a(n-1)-13*a(n-2)+4*a(n-3).
G.f.: (-1+5*x-5*x^2)/((-1+4*x)(1-3*x+x^2)).
a(n/2) = ( 2^n +2*phi^n +2*(phi-1)^n )*(1+(-1)^n)/10, with the golden section phi = A001622. - Wolfdieter Lang, Nov 08 2011
a(n) = (2^(-n)*(8^n+2*(3-sqrt(5))^n+2*(3+sqrt(5))^n))/5. - Colin Barker, Apr 27 2016
a(n) = (4^n + 2*Lucas(2*n))/5. - Ehren Metcalfe, Apr 04 2019
a(n) = Sum_{k=-n..n} binomial(2*n, n+5*k). - Greg Dresden, Jan 05 2023

A094659 Number of closed walks of length n at a vertex of the cyclic graph on 7 nodes C_7.

Original entry on oeis.org

1, 0, 2, 0, 6, 0, 20, 2, 70, 18, 252, 110, 924, 572, 3434, 2730, 12902, 12376, 48926, 54264, 187036, 232562, 720062, 980674, 2789164, 4086550, 10861060, 16878420, 42484682, 69242082, 166823430, 282580872, 657178982, 1148548016, 2595874468

Offset: 0

Herbert Kociemba, Jun 06 2004

In general, a(n,m) = (2^n/m)*Sum_{k=0..m-1} cos(2*Pi*k/m)^n gives the number of closed walks of length n at a vertex of the cyclic graph on m nodes C_m.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,4,-3,-2).

Cf. A199572 (m=2), A078008 (m=3), A199573 (m=4), A054877 (m=5), A047849 (bisection of m=6), A063376 (bisection of m=8), A094233 (m=9), A095929 (bisection of m=10), A087433 (bisection of m=12).

f[n_] := FullSimplify[ TrigToExp[ 2^n/7 Sum[Cos[2Pi*k/7]^n, {k, 0, 6}]]]; Table[ f[n], {n, 0, 36}] (* Robert G. Wilson v, Jun 09 2004 *)
LinearRecurrence[{1,4,-3,-2},{1,0,2,0},40] (* Harvey P. Dale, Jun 12 2014 *)

a(n) = (2^n/7)*Sum_{k=0..6} cos(2*Pi*k/7)^n.
a(n) = 7(a(n-2) - 2a(n-4) + a(n-6)) + 2a(n-7).
G.f.: (1-x-2x^2+x^3)/((2x-1)(-1-x+2x^2+x^3)).
a(0)=1, a(1)=0, a(2)=2, a(3)=0, a(n)=a(n-1)+4*a(n-2)-3*a(n-3)-2*a(n-4). - Harvey P. Dale, Jun 12 2014
7*a(n) = 2^n + 2*A094648(n). - R. J. Mathar, Nov 03 2020

More terms from Robert G. Wilson v, Jun 09 2004

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A095929 Number of closed walks of length 2n at a vertex of the cyclic graph on 10 nodes C_10.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A094659 Number of closed walks of length n at a vertex of the cyclic graph on 7 nodes C_7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions