|
%I #11 Dec 13 2021 02:23:51
%S 2,4,3,8,8,4,16,21,13,5,32,55,40,19,6,64,144,121,66,26,7,128,377,364,
%T 221,100,34,8,256,987,1093,728,364,143,43,9,512,2584,3280,2380,1288,
%U 560,196,53,10,1024,6765,9841,7753,4488,2108,820,260,64,11,2048,17711,29524
%N T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally or vertically.
%C Table starts
%C 2 4 8 16 32 64 128 256 512 1024 2048 4096
%C 3 8 21 55 144 377 987 2584 6765 17711 46368 121393
%C 4 13 40 121 364 1093 3280 9841 29524 88573 265720 797161
%C 5 19 66 221 728 2380 7753 25213 81927 266110 864201 2806272
%C 6 26 100 364 1288 4488 15504 53296 182688 625184 2137408 7303360
%C 7 34 143 560 2108 7752 28101 100947 360526 1282735 4552624 16131656
%C 8 43 196 820 3264 12597 47652 177859 657800 2417416 8844448 32256553
%C 9 53 260 1156 4845 19551 76912 297275 1134705 4292145 16128061 60304951
%C 10 64 336 1581 6954 29260 119416 476905 1874730 7283640 28048800 107286661
%C 11 76 425 2109 9709 42504 179630 740025 2991495 11920740 46981740 183579396
%H R. H. Hardin, <a href="/A188843/b188843.txt">Table of n, a(n) for n = 1..1741</a>
%F Row recurrence
%F Empirical: T(n,k) = Sum_{i=1..floor((n+2)/2)} binomial(n+2-i,i)*T(n,k-i)*(-1)^(i-1).
%F E.g.,
%F empirical: T(1,k) = 2*T(1,k-1),
%F empirical: T(2,k) = 3*T(2,k-1) - T(2,k-2),
%F empirical: T(3,k) = 4*T(3,k-1) - 3*T(3,k-2),
%F empirical: T(4,k) = 5*T(4,k-1) - 6*T(4,k-2) + T(4,k-3),
%F empirical: T(5,k) = 6*T(5,k-1) - 10*T(5,k-2) + 4*T(5,k-3),
%F empirical: T(6,k) = 7*T(6,k-1) - 15*T(6,k-2) + 10*T(6,k-3) - T(6,k-4),
%F empirical: T(7,k) = 8*T(7,k-1) - 21*T(7,k-2) + 20*T(7,k-3) - 5*T(7,k-4),
%F 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).
%F Columns are polynomials for n > k-3.
%F Empirical: T(n,1) = n + 1.
%F Empirical: T(n,2) = (1/2)*n^2 + (5/2)*n + 1.
%F Empirical: T(n,3) = (1/6)*n^3 + 2*n^2 + (35/6)*n.
%F Empirical: T(n,4) = (1/24)*n^4 + (11/12)*n^3 + (155/24)*n^2 + (163/12)*n - 6 for n > 1.
%F 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.
%F 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.
%F 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.
%F 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.
%e Some solutions for 5 X 3:
%e 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1
%e 0 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1
%e 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1
%e 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0
%e 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%Y Diagonal is A143388.
%Y Column 2 is A034856(n+1).
%Y Column 3 is A137742(n+1).
%Y Row 2 is A001906(n+1).
%Y Row 3 is A003462(n+1).
%Y Row 4 is A005021.
%Y Row 5 is A005022.
%Y Row 6 is A005023.
%Y Row 7 is A005024.
%Y Row 8 is A005025.
%K nonn,tabl
%O 1,1
%A _R. H. Hardin_, Apr 12 2011
|
