A188866 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally.

2, 4, 3, 8, 7, 4, 16, 17, 10, 5, 32, 41, 26, 13, 6, 64, 99, 68, 35, 16, 7, 128, 239, 178, 95, 44, 19, 8, 256, 577, 466, 259, 122, 53, 22, 9, 512, 1393, 1220, 707, 340, 149, 62, 25, 10, 1024, 3363, 3194, 1931, 950, 421, 176, 71, 28, 11, 2048, 8119, 8362, 5275, 2658, 1193, 502, 203, 80, 31, 12

Offset: 1

Author

R. H. Hardin, Apr 12 2011

Keywords

• nonn
• tabl

Comments

Number of 0..n strings of length k and adjacent elements differing by one or less. (See link for bijection.) Equivalently, number of base (n+1) k digit numbers with adjacent digits differing by one or less. - Andrew Howroyd, Mar 30 2017

All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions. - Andrew Howroyd, Apr 15 2017

Equivalently, the number of walks of length k-1 on the path graph P_{n+1} with a loop added at each vertex. - Pontus von Brömssen, Sep 08 2021

Examples

			Table starts:
   2  4  8  16  32   64  128   256   512   1024   2048    4096    8192    16384
   3  7 17  41  99  239  577  1393  3363   8119  19601   47321  114243   275807
   4 10 26  68 178  466 1220  3194  8362  21892  57314  150050  392836  1028458
   5 13 35  95 259  707 1931  5275 14411  39371 107563  293867  802859  2193451
   6 16 44 122 340  950 2658  7442 20844  58392 163594  458356 1284250  3598338
   7 19 53 149 421 1193 3387  9627 27383  77923 221805  631469 1797957  5119593
   8 22 62 176 502 1436 4116 11814 33942  97582 280676  807574 2324116  6689624
   9 25 71 203 583 1679 4845 14001 40503 117263 339699  984515 2854281  8277153
  10 28 80 230 664 1922 5574 16188 47064 136946 398746 1161634 3385486  9869934
  11 31 89 257 745 2165 6303 18375 53625 156629 457795 1338779 3916897 11463989
Some solutions for 5 X 3:
  1 1 1   1 1 1   1 1 1   1 1 1   0 0 0   1 1 1   1 1 1
  1 1 1   0 0 1   0 1 1   1 1 1   0 0 0   1 0 0   1 0 1
  0 0 0   0 0 0   0 0 1   1 1 1   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   1 1 0   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..1741
• Andrew Howroyd, Bijection with 0..n strings of length k.
• Arnold Knopfmacher, Toufik Mansour, Augustine Munagi and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Crossrefs

Columns 2..8 are A016777, A017257(n-1), A188861-A188865.

Rows 2..31 are A001333(n+1), A126358, A057960(n+1), A126360, A002714, A126362-A126386.

Main diagonal is A188860.

Cf. A276562, A220062.

Programs

Mathematica

rows = 11; rowGf[n_, x_] = 1 + (x*(n - (3*n + 2)*x) + (2*x^2)*(1 + ChebyshevU[n-1, (1-x)/(2*x)])/ChebyshevU[n, (1-x)/(2*x)])/(1-3*x)^2;
row[n_] := rowGf[n+1, x] + O[x]^(rows+1) // CoefficientList[#, x]& // Rest; T = Array[row, rows]; Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 07 2017, after Andrew Howroyd *)

PARI

\\ from Knopfmacher et al.
RowGf(k, x='x) = my(z=(1-x)/(2*x)); 1 + (x*(k-(3*k+2)*x) + (2*x^2)*(1+polchebyshev(k-1, 2, z))/polchebyshev(k, 2, z))/(1-3*x)^2;
T(n,k) = {polcoef(RowGf(n+1) + O(x*x^k),k)}
for(n=1, 10, print(Vec(RowGf(n+1) + O(x^11)))) \\ Andrew Howroyd, Apr 15 2017 [updated Mar 13 2021]

Formula

Empirical: T(n,1) = n + 1.

Empirical: T(n,2) = 3*n + 1.

Empirical: T(n,3) = 9*n - 1.

Empirical: T(n,4) = 27*n - 13 for n > 1.

Empirical: T(n,5) = 81*n - 65 for n > 2.

Empirical: T(n,6) = 243*n - 265 for n > 3.

Empirical: T(n,7) = 729*n - 987 for n > 4.

Empirical: T(n,8) = 2187*n - 3495 for n > 5.

Empirical: T(1,k) = 2*T(1,k-1).

Empirical: T(2,k) = 2*T(2,k-1) + T(2,k-2).

Empirical: T(3,k) = 3*T(3,k-1) - T(3,k-2).

Empirical: T(4,k) = 3*T(4,k-1) - 2*T(4,k-3).

Empirical: T(5,k) = 4*T(5,k-1) - 3*T(5,k-2) - T(5,k-3).

Empirical: T(6,k) = 4*T(6,k-1) - 2*T(6,k-2) - 4*T(6,k-3) + T(6,k-4).

Empirical: T(7,k) = 5*T(7,k-1) - 6*T(7,k-2) - T(7,k-3) + 2*T(7,k-4).

Empirical: T(8,k) = 5*T(8,k-1) - 5*T(8,k-2) - 5*T(8,k-3) + 5*T(8,k-4) + T(8,k-5).