A241619 T(n,k)=Number of length n+2 0..k arrays with no consecutive three elements summing to more than k.
4, 10, 6, 20, 20, 9, 35, 50, 40, 13, 56, 105, 125, 76, 19, 84, 196, 315, 295, 147, 28, 120, 336, 686, 889, 711, 287, 41, 165, 540, 1344, 2254, 2567, 1730, 556, 60, 220, 825, 2430, 5040, 7586, 7483, 4175, 1077, 88, 286, 1210, 4125, 10242, 19374, 25774, 21631, 10077
Offset: 1
Examples
Some solutions for n=5 k=4 ..1....0....2....1....0....2....0....1....0....0....0....2....1....0....1....2 ..0....0....1....3....0....0....4....2....1....0....1....1....3....0....0....1 ..0....3....0....0....0....1....0....1....3....0....0....0....0....2....1....0 ..0....0....0....1....2....0....0....0....0....0....1....0....1....1....1....2 ..2....0....3....0....0....2....0....0....0....0....2....1....0....0....0....0 ..0....1....0....1....2....1....2....0....1....0....0....1....1....0....3....1 ..0....0....0....1....0....0....2....4....2....2....0....0....2....0....0....0
Links
- R. H. Hardin, Table of n, a(n) for n = 1..10011
Crossrefs
Programs
-
Maple
for m from 1 to 12 do r:= [seq(seq([i,j],j=0..m-i),i=0..m)]; T[m]:= Matrix((m+1)*(m+2)/2,(m+1)*(m+2)/2, proc(i, j) if r[i][1]=r[j][2] and r[i][1]+r[i][2]+r[j][1]<=m then 1 else 0 fi end proc): U[m,0]:= Vector((m+1)*(m+2)/2,1); od: R:= NULL: for i from 2 to 12 do for j from 1 to i-1 do U[i-j,j]:= T[i-j] . U[i-j,j-1]; R:= R, convert(U[i-j,j],`+`) od od: R; # Robert Israel, Sep 04 2019
Formula
Empirical for column k, apparently a recurrence of order (k+1)*(k+2)/2:
k=1: a(n) = a(n-1) +a(n-3)
k=2: a(n) = a(n-1) +a(n-2) +2*a(n-3) -a(n-5) -a(n-6)
k=3: a(n) = 2*a(n-1) +4*a(n-3) -3*a(n-4) -a(n-5) -3*a(n-6) +2*a(n-7) +a(n-9) -a(n-10)
k=4: [order 15]
k=5: [order 21]
k=6: [order 28]
k=7: [order 36]
k=8: [order 45]
k=9: [order 55]
k=10: [order 66]
k=11: [order 78]
k=12: [order 91]
Empirical for row n, apparently a polynomial of degree n+2:
n=1: a(n) = (1/6)*n^3 + 1*n^2 + (11/6)*n + 1
n=2: a(n) = (1/12)*n^4 + (2/3)*n^3 + (23/12)*n^2 + (7/3)*n + 1
n=3: a(n) = (1/24)*n^5 + (5/12)*n^4 + (13/8)*n^3 + (37/12)*n^2 + (17/6)*n + 1
n=4: [polynomial of degree 6]
n=5: [polynomial of degree 7]
n=6: [polynomial of degree 8]
n=7: [polynomial of degree 9]
From Robert Israel, Sep 04 2019: (Start)
Column k satisfies a recurrence of order (k+1)*(k+2)/2, since a(n)=e^T T^n e where T is a (k+1)*(k+2)/2 matrix and e the vector of all 1's (see proofs at A241615 and A241618).
Row n is the Ehrhart polynomial of degree n+2 corresponding to the polytope {(x(1),...,x(n+2)): all x(i)>=0, x(i)+x(i+1)+x(i+2)<=1 for i=1..n}, whose vertices have all entries in {0,1}. (End)
Comments