login
A188866
T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally.
13
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,1
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
LINKS
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.
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).
EXAMPLE
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
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 *)
PROG
(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]
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.
Sequence in context: A168521 A244982 A101468 * A235486 A066194 A101283
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Apr 12 2011
STATUS
approved