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

Author

R. H. Hardin Nov 23 2011

Keywords

• nonn
• tabl

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

Examples

			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
		

Links

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

Crossrefs

Column 1 is A006355(n+4)

Row 1 is A084990(n+1)

Programs

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 *)

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