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

Ron Hardin rhhardin at att.net
Mon Apr 4 21:37:11 CEST 2011

```Great

So it looks like the ogf for the array is 1/ the recurrence formula given ?
with powers of z for the lagged terms.

How should it be written?  (I can't check ogf's to see that whatever is written
is in fact right)

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

----- Original Message ----
> From: Robert Israel <israel at math.ubc.ca>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Mon, April 4, 2011 2:48:39 PM
> Subject: [seqfan] Re: T(n,k) guess the formula
>
> In such an array, let x_j be the position of the lowest 1 in column j
> (0 if  that column has no 1's).  Then we require x_{j+1} <= x_j + 1.
> So  T(n,k) is the number of sequences of integers (x_1,...,x_k) with
> all 0 <=  x_i <= n and x_{j+1} <= x_j + 1.
>
> Let M be the (n+1) x (n+1) matrix  with entries m_{ij} = 1 for j <= i+1, 0
>otherwise, u the row vector of n 1's,  v the column vector consisting of 1
>followed by n 0's.  Then T(n,k) = u M^k  v.  So the ogf for row n is G_n(z) =
>sum_{k=0}^infty T(n,k) z^k = u (I - z  M)^(-1) v, which is a rational function
>whose poles are reciprocals of the  nonzero eigenvalues of M.  The first few are
>as follows, according to  Maple:
>
>
>                                           1
>                           G[1](z) = - --------
>                                        -1 + 2 z
>
>
>                                          1
>                          G[2](z) = ------------
>                                                2
>                                     1 - 3 z + z
>
>
>                                          1
>                       G[3](z) = ------------------
>                                  (3 z - 1) (-1 + z)
>
>
>                                           1
>                     G[4](z) = - --------------------
>                                                2    3
>                                  -1 + 5 z - 6 z  + z
>
>
>                                           1
>                 G[5](z) = - ---------------------------
>                                             2
>                              (-1 + 2 z) (2 z  - 4 z + 1)
>
>
>                                          1
>                 G[6](z) = ------------------------------
>                                       3      2
>                           (-1 + z) (z  - 9 z   + 6 z - 1)
>
>
>                                          1
>               G[7](z) =  -------------------------------
>                                       2      2
>                          (1 - 3 z + z ) (5 z  - 5 z +  1)
>
>
>                                           1
>           G[8](z) = -  -------------------------------------
>                                        2       3       4     5
>                        -1 + 9 z - 28 z  + 35 z  - 15 z  + z
>
>
>                                           1
>         G[9](z) = - --------------------------------------------
>                                             2
>                     (3 z - 1) (-1 + 2 z)  (z  - 4 z + 1) (-1 + z)
>
>
>                                           1
>        G[10](z) =  ---------------------------------------------
>                                    2       3       4        5    6
>                    1 - 11 z + 45 z  - 84 z  + 70 z  - 21 z  +  z
>
> Robert Israel                                 israel at math.ubc.ca
> Department of  Mathematics        http://www.math.ubc.ca/~israel University of
>
> On Mon, 4 Apr 2011, Ron Hardin wrote:
>
> > 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)
> >
> >
> > _______________________________________________
> >
> > Seqfan  Mailing list - http://list.seqfan.eu/
> >
>
> _______________________________________________
>
> Seqfan Mailing  list - http://list.seqfan.eu/
>

```