A276562 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with cyclically adjacent elements differing by 1 or less.

1, 1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 15, 10, 5, 1, 32, 35, 22, 13, 6, 1, 64, 83, 54, 29, 16, 7, 1, 128, 199, 134, 73, 36, 19, 8, 1, 256, 479, 340, 185, 92, 43, 22, 9, 1, 512, 1155, 872, 481, 236, 111, 50, 25, 10, 1, 1024, 2787, 2254, 1265, 622, 287, 130, 57, 28, 11

Offset: 1

Author

Andrew Howroyd, Apr 15 2017

Keywords

• nonn
• tabl

Comments

All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions.

Examples

			Array starts:
   1  1  1   1   1    1    1    1     1     1 ...
   2  4  8  16  32   64  128  256   512  1024 ...
   3  7 15  35  83  199  479 1155  2787  6727 ...
   4 10 22  54 134  340  872 2254  5854 15250 ...
   5 13 29  73 185  481 1265 3361  8993 24193 ...
   6 16 36  92 236  622 1658 4468 12132 33146 ...
   7 19 43 111 287  763 2051 5575 15271 42099 ...
   8 22 50 130 338  904 2444 6682 18410 51052 ...
   9 25 57 149 389 1045 2837 7789 21549 60005 ...
  10 28 64 168 440 1186 3230 8896 24688 68958 ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275
• Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Crossrefs

Rows 3-32 are A124696-A124719, A124726, A124783, A124784, A124799, A124803, A124804.

Cf. A188866, A220062, A285280, A285281, A208777, A208721.

Programs

Mathematica

T[m_, n_] := Sum[(1 + 2*Cos[j*Pi/(m+1)])^n, {j, 1, m}] // FullSimplify;
Table[T[m-n+1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

PARI

\\ from Knopfmacher et al.
ChebyshevU(n,x) = sum(i=0, n/2, 2*poltchebi(n-2*i,x)) + (n%2-1);
RowGf(k,x) = 1 + (k*x*(1+3*x) - 2*(k+1)*x*subst(ChebyshevU(k-1,z)/ChebyshevU(k,z),z,(1-x)/(2*x)))/((1+x)*(1-3*x));
a(m,n)=Vec(RowGf(m,x)+O(x^(n+1)))[n+1];
for(m=1, 10, print(RowGf(m,x)));
for(m=1, 10, for(n=1, 9, print1( a(m,n), ", ") ); print(); );

Formula

T(m, n) = Sum_{j=1..m} (1 + 2*cos(j*pi/(m+1)))^n. - Andrew Howroyd, Apr 15 2017