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

2, 4, 3, 8, 8, 4, 16, 21, 13, 5, 32, 55, 40, 19, 6, 64, 144, 121, 66, 26, 7, 128, 377, 364, 221, 100, 34, 8, 256, 987, 1093, 728, 364, 143, 43, 9, 512, 2584, 3280, 2380, 1288, 560, 196, 53, 10, 1024, 6765, 9841, 7753, 4488, 2108, 820, 260, 64, 11, 2048, 17711, 29524

Offset: 1

Author

R. H. Hardin, Apr 12 2011

Keywords

• nonn
• tabl

Comments

Table starts

2 4 8 16 32 64 128 256 512 1024 2048 4096

3 8 21 55 144 377 987 2584 6765 17711 46368 121393

4 13 40 121 364 1093 3280 9841 29524 88573 265720 797161

5 19 66 221 728 2380 7753 25213 81927 266110 864201 2806272

6 26 100 364 1288 4488 15504 53296 182688 625184 2137408 7303360

7 34 143 560 2108 7752 28101 100947 360526 1282735 4552624 16131656

8 43 196 820 3264 12597 47652 177859 657800 2417416 8844448 32256553

9 53 260 1156 4845 19551 76912 297275 1134705 4292145 16128061 60304951

10 64 336 1581 6954 29260 119416 476905 1874730 7283640 28048800 107286661

11 76 425 2109 9709 42504 179630 740025 2991495 11920740 46981740 183579396

Examples

			Some solutions for 5 X 3:
  0 0 1    1 1 0    1 1 1    0 1 0    1 1 0    1 1 0    1 1 1
  0 0 0    1 0 0    1 1 0    0 0 0    1 1 0    1 1 0    1 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    1 1 0    0 1 1
  0 0 0    0 0 0    1 1 0    0 0 0    1 0 0    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
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..1741

Crossrefs

Diagonal is A143388.

Column 2 is A034856(n+1).

Column 3 is A137742(n+1).

Row 2 is A001906(n+1).

Row 3 is A003462(n+1).

Row 4 is A005021.

Row 5 is A005022.

Row 6 is A005023.

Row 7 is A005024.

Row 8 is A005025.

Formula

Row recurrence

Empirical: T(n,k) = Sum_{i=1..floor((n+2)/2)} binomial(n+2-i,i)*T(n,k-i)*(-1)^(i-1).

E.g.,

empirical: T(1,k) = 2*T(1,k-1),

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

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

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

empirical: T(5,k) = 6*T(5,k-1) - 10*T(5,k-2) + 4*T(5,k-3),

empirical: T(6,k) = 7*T(6,k-1) - 15*T(6,k-2) + 10*T(6,k-3) - T(6,k-4),

empirical: T(7,k) = 8*T(7,k-1) - 21*T(7,k-2) + 20*T(7,k-3) - 5*T(7,k-4),

empirical: T(8,k) = 9*T(8,k-1) - 28*T(8,k-2) + 35*T(8,k-3) - 15*T(8,k-4) + T(8,k-5).

Columns are polynomials for n > k-3.

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

Empirical: T(n,2) = (1/2)*n^2 + (5/2)*n + 1.

Empirical: T(n,3) = (1/6)*n^3 + 2*n^2 + (35/6)*n.

Empirical: T(n,4) = (1/24)*n^4 + (11/12)*n^3 + (155/24)*n^2 + (163/12)*n - 6 for n > 1.

Empirical: T(n,5) = (1/120)*n^5 + (7/24)*n^4 + (89/24)*n^3 + (473/24)*n^2 + (1877/60)*n - 33 for n > 2.

Empirical: T(n,6) = (1/720)*n^6 + (17/240)*n^5 + (203/144)*n^4 + (647/48)*n^3 + (2659/45)*n^2 + (1379/20)*n - 143 for n > 3.

Empirical: T(n,7) = (1/5040)*n^7 + (1/72)*n^6 + (143/360)*n^5 + (53/9)*n^4 + (33667/720)*n^3 + (12679/72)*n^2 + (9439/70)*n - 572 for n > 4.

Empirical: T(n,8) = (1/40320)*n^8 + (23/10080)*n^7 + (17/192)*n^6 + (269/144)*n^5 + (43949/1920)*n^4 + (228401/1440)*n^3 + (1054411/2016)*n^2 + (9941/56)*n - 2210 for n > 5.