login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A188843
T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.
6
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,1
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
LINKS
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.
EXAMPLE
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
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.
Sequence in context: A067179 A318993 A355482 * A209406 A188706 A304408
KEYWORD
nonn,tabl
AUTHOR
R. H. Hardin, Apr 12 2011
STATUS
approved