# [seqfan] T(n,k) guess the formula

Ron Hardin rhhardin at att.net
Mon Apr 4 19:39:51 CEST 2011

```Can the entire formula be guessed?

T(n,k)=Number of nXk binary arrays without the pattern 0 1 diagonally or
vertically

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

Empirical recurrences for rows:
T(n,k) = sum( binomial(n+2-i ,i) * T(n,k-i) * (-1)^(i-1) , i=1..floor((n+2)/2) )

e.g., a(n) for rows 1..8
Empirical: a(n)=2*a(n-1)
Empirical: a(n)=3*a(n-1)-a(n-2)
Empirical: a(n)=4*a(n-1)-3*a(n-2)
Empirical: a(n)=5*a(n-1)-6*a(n-2)+a(n-3)
Empirical: a(n)=6*a(n-1)-10*a(n-2)+4*a(n-3)
Empirical: a(n)=7*a(n-1)-15*a(n-2)+10*a(n-3)-a(n-4)
Empirical: a(n)=8*a(n-1)-21*a(n-2)+20*a(n-3)-5*a(n-4)
Empirical: a(n)=9*a(n-1)-28*a(n-2)+35*a(n-3)-15*a(n-4)+a(n-5)

Empirical polynomials for columns:
T(n,1) = n + 1
T(n,2) = (1/2)*n^2 + (5/2)*n + 1
T(n,3) = (1/6)*n^3 + 2*n^2 + (35/6)*n
T(n,4) = (1/24)*n^4 + (11/12)*n^3 + (155/24)*n^2 + (163/12)*n - 6 for n>1
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
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
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
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

rhhardin at mindspring.com
rhhardin at att.net (either)

```