A206455 T(n,k) = number of 0..k arrays of length n avoiding the consecutive pattern 0..k.
2, 3, 3, 4, 9, 4, 5, 16, 26, 5, 6, 25, 64, 75, 6, 7, 36, 125, 255, 216, 7, 8, 49, 216, 625, 1016, 622, 8, 9, 64, 343, 1296, 3124, 4048, 1791, 9, 10, 81, 512, 2401, 7776, 15615, 16128, 5157, 10, 11, 100, 729, 4096, 16807, 46655, 78050, 64257, 14849, 11, 12, 121, 1000
Offset: 1
Examples
Table starts 2 3 4 5 6 7 8 9 10 11 ... 3 9 16 25 36 49 64 81 100 121 ... 4 26 64 125 216 343 512 729 1000 1331 ... 5 75 255 625 1296 2401 4096 6561 10000 14641 ... 6 216 1016 3124 7776 16807 32768 59049 100000 161051 ... 7 622 4048 15615 46655 117649 262144 531441 1000000 1771561 ... 8 1791 16128 78050 279924 823542 2097152 4782969 10000000 19487171 ... 9 5157 64257 390125 1679508 5764787 16777215 43046721 100000000 214358881 ... ...
Links
- R. H. Hardin, Table of n, a(n) for n = 1..10000
- Robert Israel, Proof of recurrence for column k
Programs
-
Maple
N:= 20: # for the first N antidiagonals for k from 1 to N-1 do F[k]:= gfun:-rectoproc({a(n)=(k+1)*a(n-1) - a(n-k-1), seq(a(j)=(k+1)^j,j=1..k),a(k+1)=(k+1)^(k+1)-1},a(n),remember) od: seq(seq(F[m-j](j),j=1..m-1),m=1..N); # Robert Israel, Dec 17 2017 -
Mathematica
nmax = 20; col[k_] := col[k] = Module[{a}, a[n_ /; n>2] := a[n] = (k+1)*a[n-1]-a[n-k-1]; a[0]=1; a[1]=k+1; a[2]=(k+1)^2; a[_?Negative]=0; Array[a, nmax]]; T[n_, k_] := If[k == 1, n+1, col[k][[n]]]; Table[T[n-k+1, k], {n, 1, nmax}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jul 22 2022 *)
Formula
Empirical: T(n,k) = sum{i=0..floor(n/(k+1))} ( (-1)^i * (k+1)^(n-(k+1)*i) * binomial(n-k*i,i) ) (after A076264)
Empirical for column k: a(n) = (k+1)*a(n-1) - a(n-(k+1)).
Formula for column k verified by Robert Israel, Dec 17 2017 (see link).