login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A188866 T(n,k) = Number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally. 11
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 (list; table; graph; refs; listen; history; text; internal format)
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

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

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, 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

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.

ChebyshevU(n, x) = sum(i=0, n/2, 2*poltchebi(n-2*i, x)) + (n%2-1);

RowGf(k, x) = 1 + (x*(k-(3*k+2)*x) + (2*x^2)*subst((1+ChebyshevU(k-1, z))/ChebyshevU(k, z), z, (1-x)/(2*x)))/(1-3*x)^2;

a(b, n)=Vec(RowGf(b+1, x)+O(x^(n+1)))[n+1];

for(k=2, 12, print(RowGf(k, x)));

for(b=1, 10, for(n=1, 9, print1( a(b, n), ", ") ); print(); )

\\ Andrew Howroyd, Apr 15 2017

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.

Sequence in context: A168521 A244982 A101468 * A235486 A066194 A101283

Adjacent sequences:  A188863 A188864 A188865 * A188867 A188868 A188869

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Apr 12 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 23 04:46 EDT 2019. Contains 321422 sequences. (Running on oeis4.)