A198635 -id:A198635 - cp's OEIS frontend

A198632 Triangle version of the array of the number of closed paths of even length on the graph P_n (n vertices, n-1 edges).

1, 0, 2, 0, 2, 3, 0, 2, 4, 4, 0, 2, 8, 6, 5, 0, 2, 16, 14, 8, 6, 0, 2, 32, 36, 20, 10, 7, 0, 2, 64, 94, 56, 26, 12, 8, 0, 2, 128, 246, 164, 76, 32, 14, 9, 0, 2, 256, 644, 488, 234, 96, 38, 16, 10, 0, 2, 512, 1686, 1460, 740, 304, 116, 44, 18, 11, 0, 2, 1024, 4414, 4376, 2372, 992, 374, 136, 50, 20, 12, 0, 2, 2048, 11556, 13124, 7654, 3296, 1244, 444, 156, 56, 22, 13

Offset: 0

Wolfdieter Lang, Nov 02 2011

This array is an example of counting walks on a graph whose adjacency matrix is given by a special symmetric tridiagonal matrix with nonnegative integer entries, appropriate for orthogonal polynomials. These are quadratic Jacobi matrices J_n with nonnegative entries. The corresponding graphs could be called Jacobi graphs. Here Chebyshev S-polynomials (coefficients A049310) are considered, which belong to the Jacobi class of the classical orthogonal polynomial systems. The corresponding graph has adjacency matrix [[0,1,0,...],[1,0,1,...],[0,1,0,1,...]...[0,...0,1,0]] (n rows and n columns), with characteristic polynomial S(n,x) (see also a comment by Michael Somos on A049310).
w(n,l;p_k->p_m) = ((J_n)^l)(k,m) is the number of walks of length l from vertex p_k to vertex p_m on such a Jacobi graph. w(n,0; p_k->p_m) = delta(k,m), with the Kronecker symbol delta. The total number of closed walks of length l is w(n,l):=Sum_{i=1..n} w(n,l; p_i->p_i) = trace(J_n^l), which is the l-th power sum of the eigenvalues of J_n, i.e., the zeros of the characteristic polynomial for J_n. There are theorems for the o.g.f. of the normalized power sums of these zeros. See, e.g., the given W. Lang reference, p. 244. This results for the S-polynomial in the o.g.f. G(n,x) = Sum_{l=0..infinity} w(n,l)*x^l = y*(d/dy)S(n,y)/S(y) with y=1/x. This can be rewritten in the form given in the formula section (this results from eq. (3.8b) of the W. Lang reference, and in eq. (3.8d) it should be coth, not tanh).
From Wolfdieter Lang, Oct 10 2012: (Start)
For an accompanying paper on path counting on Jacobi graphs see the W. Lang link under A201198.
The total number of round trips of length L on the graph P_n, taken per site, becomes for n -> infinity A126869(L). See the just mentioned link, p. 8. This limit is derived from the limit of G(n,x)/n with G(n,x) given in the formula section.
Thanks go to Clyde P. Kruskal for asking a question which led to this comment.
(End)

			The array w(n,2*k) is
n\k  0  1   2   3   4    5    6     7     8      9 ...
1:   1  0   0   0   0    0    0     0     0      0
2:   2  2   2   2   2    2    2     2     2      2
3:   3  4   8  16  32   64  128   256   512   1024
4:   4  6  14  36  94  246  644  1686  4414  11556
5:   5  8  20  56 164  488 1460  4376 13124  39368
6:   6 10  26  76 234  740 2372  7654 24778  80338
7:   7 12  32  96 304  992 3296 11072 37440 127104
8:   8 14  38 116 374 1244 4220 14504 50294 175454
9:   9 16  44 136 444 1496 5144 17936 63164 224056
...
The triangle is
k\n 1  2    3    4    5    6   7    8   9 10 11 12 ...
0:  1
1:  0  2
2:  0  2    3
3:  0  2    4    4
4:  0  2    8    6    5
5:  0  2   16   14    8    6
6:  0  2   32   36   20   10   7
7:  0  2   64   94   56   26  12    8
8:  0  2  128  246  164   76  32   14   9
9:  0  2  256  644  488  234  96   38  16 10
10: 0  2  512 1686 1460  740 304  116  44 18 11
11: 0  2 1024 4414 4376 2372 992  374 136 50 20 12
...
n=3, l=2*k = 4: graph P_3 as 1-2-3, with eight walks of length 4, namely 12121, 12321, 21212, 23232, 21232, 23212, 32323 and 32123.

S. Barbero, Dickson Polynomials, Chebyshev Polynomials, and Some Conjectures of Jeffery, Journal of Integer Sequences, 17 (2014), #14.3.8.
S. Barbero, U. Cerruti, N. Murru, Identities Involving Zeros of Ramanujan and Shanks Cubic Polynomials, J. Integer Seq., Vol. 16 (2013), Article 13.8.1.
Carlos M. da Fonseca, M. Lawrence Glasser, Victor Kowalenko, Basic trigonometric power sums with applications, arXiv:1601.07839 [math.NT], 2016. See Theorem 5.1.
W. Lang, On sums of powers of zeros of polynomials, J. Comp. Appl. Math., 89 (1998) 237-256.

Column sequences: A000007, 2*A000012, A198633, 2*A005248, A198635, ...

a(k,n)=w(n,2*(k-n+2)), the total number of closed walks (paths) of length 2*(k-n+2) on the graph P_n, which looks like o-o-o...-o, with n vertices (nodes) and n-1 edges (lines), k+1>=n>=1.
O.g.f. G(n,x) for w(n,l), which vanishes for odd l, is
((n+1)*coth((n+1)*log((2*x)/(1-sqrt(1-(2*x)^2)))) - 1/sqrt(1-(2*x)^2))/sqrt(1-(2*x)^2). See the comment above for a version with Chebyshev S-polynomials.
Conjecture: For the array w(n,2*k) in the example below, w(2*q,2*k)/2 = A185095(q,k), q >= 1, k >= 0. - L. Edson Jeffery, Nov 23 2013

A198633 Total number of round trips, each of length 2*n on the graph P_3 (o-o-o).

Original entry on oeis.org

3, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648

Offset: 0

Wolfdieter Lang, Nov 02 2011

See the array and triangle A198632 for the general case for the graph P_N (there N is n and the length is l=2*k).

			With the graph P_3 as 1-2-3:
n=0: 3, from the length 0 walks starting at 1, 2 and 3.
n=2: 8, from the walks of length 4, namely 12121, 12321, 21212, 23232, 21232, 23212, 32323 and 32123.

Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A198632, 2*A005248, A198635.

Essentially the same as A000079, A020707, A077552 etc.

Join[{3},NestList[2#&,4,30]] (* Harvey P. Dale, Nov 07 2020 *)

a(n)=if(n,2<Charles R Greathouse IV, Jan 02 2012

a(n) = w(3,2*n), n>=0, with w(3,l) the total number of closed walks on the graph P_3 (the simple path with 3 points (vertices) and 2 lines (or edges)).
O.g.f. for w(3,l) (with zeros for odd l): y*(d/dy)S(3,y)/S(3,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See A198632, also for a rewritten form.
Empirical g.f.: (3-2*x)/(1-2*x). - Colin Barker, Jan 02 2012
This g.f. follows from the Chebyshev o.g.f. given above with x -> sqrt(x). Therefore a(0) = 3 and a(n) = 2^(n+1), n >= 1. - Wolfdieter Lang, Feb 18 2013.

A198636 One half of total number of round trips, each of length 2n, on the graph P_6 (o-o-o-o-o-o).

Original entry on oeis.org

3, 5, 13, 38, 117, 370, 1186, 3827, 12389, 40169, 130338, 423065, 1373466, 4459278, 14478659, 47011093, 152642789, 495626046, 1609284589, 5225309458, 16966465802, 55089756851, 178875298901, 580804419201, 1885860059450, 6123349080945

Offset: 0

Wolfdieter Lang, Nov 03 2011

See the array and triangle A198632 for the general graph P_N case (there N is n and the length is l=2*k).

			With the graph P_6 as 1-2-3-4-5-6:
n=0: a(0)=3 because w(6,0)=6, the number of vertices.
n=2: a(2)=5 because the 10 round trips of length 2 are 121, 212, 232, 323, 343, 434, 454, 545, 565 and 656.

M. F. Hasler, Table of n, a(n) for n = 0..499
S. Barbero, Dickson Polynomials, Chebyshev Polynomials, and Some Conjectures of Jeffery, Journal of Integer Sequences, 17 (2014), #14.3.8.
S. Barbero, U. Cerruti, N. Murru, Identities Involving Zeros of Ramanujan and Shanks Cubic Polynomials, J. Integer Seq., Vol. 16 (2013), Article 13.8.1, pp. 10-12.
Index entries for linear recurrences with constant coefficients, signature (5,-6,1).

Cf. A198632, A198633, A005248, A198635.

Table[7 (Binomial[2 n - 1, n - 1] + Sum[Binomial[2 n, n - 7 k], {k, Floor[n/7]}]) - 2^(2 n - 1) - (7/2) Boole[n == 0], {n, 0, 25}] (* Michael De Vlieger, Jul 17 2017 *)

vec_A198636(Nmax)=Vec((3-10*x+6*x^2)/(1-5*x+6*x^2-x^3)+O(x^Nmax)) \\ Indices will start at 1 in this vector. - M. F. Hasler, Nov 03 2013

{a(n) = if( n<0, n=-n; polcoeff( (3 - 12*x + 5*x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (3 - 10*x + 6*x^2) / (1 - 5*x + 6*x^2 -x^3) + x * O(x^n), n))}; /* Michael Somos, Jul 17 2017 */

a(n) = w(6,2*n)/2, n>=0, with w(6,l) the total number of closed walks on the graph P_6 (the simple path with 6 points (vertices) and 5 lines (or edges)).
O.g.f. for w(6,l) (with zeros for odd l): y*(d/dy)S(6,y)/S(6,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form.
O.g.f.: (3-10*x+6*x^2)/(1-5*x+6*x^2-x^3). - Colin Barker, Jan 02 2012
Conjecture: a(n) = 2^(2*n)*(sum_{k=1,2,3} (cos(k*Pi/7))^(2*n)). - L. Edson Jeffery, Jan 21 2012 (in fact this conjecture was recently proved in [Barbero, et al.])
a(n) = 7*(binomial(2n-1,n-1) + sum_{k = 1..floor(n/7)} binomial(2n,n-7k)) - 2^(2n-1). - M. Lawrence Glasser, Feb 20 2013
Let r,s,t be the roots of x^3 + x^2 - 2x - 1; then apparently a(n) = r^(2n) + s^(2n) + t^(2n). - James R. Buddenhagen, Nov 03 2013 [This is equivalent to the conjecture by L. Edson Jeffery.]
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). - M. F. Hasler, Nov 05 2013
G.f.: F(x) = (sum_{r=0..2} ((3-r)*(-1)^r*binomial(6-r,r))*x^r)/(sum_{s=0..3} ((-1)^s*binomial(6-s,s))*x^s). - L. Edson Jeffery, Nov 23 2013

A208724 Number of 2n-bead necklaces labeled with numbers 1..5 not allowing reversal, with neighbors differing by exactly 1.

Original entry on oeis.org

4, 7, 12, 25, 52, 131, 316, 835, 2196, 5935, 16108, 44369, 122644, 341803, 956636, 2690845, 7596484, 21524543, 61171660, 174342217, 498112276, 1426419859, 4093181692, 11767920119, 33891544420, 97764131647, 282429537948, 817028472961, 2366564736724, 6863038218843

Offset: 1

R. H. Hardin, Mar 01 2012

nonn

			All solutions for n=3:
..4....1....3....2....1....2....3....1....2....3....1....2
..5....2....4....3....2....3....4....2....3....4....2....3
..4....1....3....2....3....4....3....3....2....5....1....4
..5....2....4....3....2....3....4....4....3....4....2....5
..4....3....3....2....3....4....5....3....4....5....1....4
..5....2....4....3....2....3....4....2....3....4....2....3

Andrew Howroyd, Table of n, a(n) for n = 1..100

Column 5 of A208727.

a[n_] := (1/n)*DivisorSum[n, EulerPhi[n/#] * (2*3^# + 2) &] / 2;
Array[a, 30] (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)

a(n) = (1/n) * Sum_{d | n} totient(n/d) * A198635(d) / 2. - Andrew Howroyd, Mar 18 2017

a(15)-a(30) from Andrew Howroyd, Mar 18 2017

cp's OEIS Frontend

A198632 Triangle version of the array of the number of closed paths of even length on the graph P_n (n vertices, n-1 edges).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A198633 Total number of round trips, each of length 2*n on the graph P_3 (o-o-o).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A198636 One half of total number of round trips, each of length 2n, on the graph P_6 (o-o-o-o-o-o).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A208724 Number of 2n-bead necklaces labeled with numbers 1..5 not allowing reversal, with neighbors differing by exactly 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions