A200871 T(n,k)=Number of 0..k arrays x(0..n+1) of n+2 elements without any interior element greater than both neighbors or less than both neighbors

6, 17, 10, 36, 37, 16, 65, 94, 77, 26, 106, 195, 236, 163, 42, 161, 356, 567, 602, 343, 68, 232, 595, 1168, 1673, 1528, 723, 110, 321, 932, 2163, 3886, 4917, 3882, 1523, 178, 430, 1389, 3704, 7973, 12890, 14455, 9858, 3209, 288, 561, 1990, 5973, 14932, 29325

Offset

1,1

Comments

Table starts

...6....17.....36......65.....106......161......232.......321.......430

..10....37.....94.....195.....356......595......932......1389......1990

..16....77....236.....567....1168.....2163.....3704......5973......9184

..26...163....602....1673....3886.....7973....14932.....26073.....43066

..42...343...1528....4917...12890....29325....60112....113745....201994

..68...723...3882...14455...42744...107777...241718....495495....945790

.110..1523...9858...42479..141688...395929...971416...2156867...4424298

.178..3209..25038..124851..469726..1454643..3904290...9389377..20696974

.288..6761..63592..366959.1557320..5344795.15693816..40880321..96838448

.466.14245.161514.1078565.5163158.19638715.63085186.177996275.453123270

Links

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

Formula

Empirical for columns:

k=1: a(n) = a(n-1) +a(n-2)

k=2: a(n) = 2*a(n-1) +a(n-4)

k=3: a(n) = 2*a(n-1) +a(n-2) +2*a(n-4) +a(n-5)

k=4: a(n) = 3*a(n-1) -a(n-2) +a(n-3) +4*a(n-4) +a(n-6) +a(n-7)

k=5: a(n) = 3*a(n-1) +a(n-3) +7*a(n-4) +3*a(n-5) +2*a(n-6) +3*a(n-7) +a(n-8)

k=6: a(n) = 4*a(n-1) -3*a(n-2) +4*a(n-3) +9*a(n-4) +7*a(n-6) +6*a(n-7) +a(n-8) +2*a(n-9) +a(n-10)

k=7: a(n) = 4*a(n-1) -2*a(n-2) +4*a(n-3) +15*a(n-4) +6*a(n-5) +12*a(n-6) +16*a(n-7) +7*a(n-8) +5*a(n-9) +4*a(n-10) +a(n-11)

Empirical for rows:

n=1: a(k) = (1/3)*k^3 + 2*k^2 + (8/3)*k + 1

n=2: a(k) = (1/12)*k^4 + (3/2)*k^3 + (47/12)*k^2 + (7/2)*k + 1

n=3: a(k) = (1/60)*k^5 + (3/4)*k^4 + (15/4)*k^3 + (25/4)*k^2 + (127/30)*k + 1

n=4: a(k) = (1/360)*k^6 + (7/24)*k^5 + (197/72)*k^4 + (185/24)*k^3 + (1667/180)*k^2 + 5*k + 1

n=5: a(k) = (1/2520)*k^7 + (17/180)*k^6 + (281/180)*k^5 + (64/9)*k^4 + (4927/360)*k^3 + (2303/180)*k^2 + (604/105)*k + 1

n=6: a(k) = (1/20160)*k^8 + (19/720)*k^7 + (211/288)*k^6 + (1889/360)*k^5 + (44167/2880)*k^4 + (15991/720)*k^3 + (5689/336)*k^2 + (391/60)*k + 1

n=7: a(k) = (1/181440)*k^9 + (131/20160)*k^8 + (8893/30240)*k^7 + (4621/1440)*k^6 + (118933/8640)*k^5 + (83957/2880)*k^4 + (763489/22680)*k^3 + (36343/1680)*k^2 + (9169/1260)*k + 1

Example

Some solutions for n=4 k=3
..3....2....0....0....2....0....1....0....0....2....3....3....1....1....1....3
..2....2....0....2....0....2....2....2....0....3....1....3....2....1....2....3
..2....1....3....3....0....2....2....2....0....3....0....3....2....2....2....3
..2....0....3....3....3....0....1....0....2....3....0....2....2....2....0....2
..2....0....0....1....3....0....1....0....2....3....0....2....2....2....0....2
..3....2....0....1....1....0....2....3....3....2....2....1....3....2....0....0

Mathematica

t[0, k_, x_, y_] := 1; t[n_, k_, x_, y_] := t[n, k, x, y] = Sum[If[z <= x <= y || y <= x <= z, t[n-1, k, z, x], 0], {z, k+1}]; t[n_, k_] := Sum[t[n, k, x, y], {x, k+1}, {y, k+1}]; TableForm@ Table[t[n, k], {n, 8}, {k, 8}] (* Giovanni Resta, Mar 05 2014 *)

Crossrefs

Column 1 is A006355(n+4)

Row 1 is A084990(n+1)

Sequence in context: A323516 A120930 A070395 * A112366 A095421 A063584

Adjacent sequences: A200868 A200869 A200870 * A200872 A200873 A200874

Keyword

nonn,tabl

Author

R. H. Hardin Nov 23 2011

Status

approved