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,1

Comments

Table starts

...4...10....20.....35......56.......84......120.......165.......220........286

...6...20....50....105.....196......336......540.......825......1210.......1716

...9...40...125....315.....686.....1344.....2430......4125......6655......10296

..13...76...295....889....2254.....5040....10242.....19305.....34243......57772

..19..147...711...2567....7586....19374....44274.....92697....180829.....332761

..28..287..1730...7483...25774....75180...193194....449295....963886....1934647

..41..556..4175..21631...86828...289248...835812...2159025...5093737...11151140

..60.1077.10077..62547..292621..1113348..3617703..10380183..26932543...64309245

..88.2091.24377.181255..988303..4294574.15692003..50011289.142701909..371651553

.129.4057.58928.524877.3335451.16553380.68014233.240772037.755538278.2146210209

Links

R. H. Hardin, Table of n, a(n) for n = 1..10011

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)

Example

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

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

Crossrefs

Column 1 is A000930(n+4)

Row 1 is A000292(n+1)

Row 2 is A002415(n+2)

Row 3 is A006414

Row 4 is A114244

Sequence in context: A347116 A389126 A205016 * A129531 A298264 A014476

Adjacent sequences: A241616 A241617 A241618 * A241620 A241621 A241622

Keyword

nonn,tabl

Author

R. H. Hardin, Apr 26 2014

Status

approved