OFFSET
0,3
COMMENTS
Counting the top row as row 0, T(n,k) is the number of strings of nonnegative integers "s(1)s(2)s(3)...s(k)" such that s(1)+s(2)+s(3)+...+s(k) = n and the string does not contain the substring "00". E.g., T(3,5) = 8 because the valid strings are 02010, 01020, 11010, 10110, 10101, 01110, 01101 and 01011. T(4,3) = 13, counting 040, 311, 301, 130, 031, 103, 013, 220, 202, 022, 211, 121 and 112. - Jose Luis Arregui (arregui(AT)unizar.es), Dec 05 2007
FORMULA
T(n, k) = T(n-1, k-2) + T(n-1, k-1) + T(n-1, k), starting with [1], [1, 2, 1], [1, 3, 4, 3, 1].
G.f.: (1+yz)/[1-z(1+y+y^2)].
EXAMPLE
1
1 2 1
1 3 4 3 1
1 4 8 10 8 4 1
1 5 13 22 26 22 13 5 1
MATHEMATICA
T[_, 0] = 1; T[1, 1] = 2; T[n_, k_] /; 0 <= k <= 2n := T[n, k] = T[n-1, k-2] + T[n-1, k-1] + T[n-1, k]; T[_, _] = 0;
Table[T[n, k], {n, 0, 10}, {k, 0, 2n}] // Flatten (* Jean-François Alcover, Jul 22 2018 *)
PROG
(PARI) {T(n, k) = if( k<0 || k>2*n, 0, if( n==0, 1, if( n==1, [1, 2, 1][k+1], if( n==2, [1, 3, 4, 3, 1][k+1], T(n-1, k-2) + T(n-1, k-1) + T(n-1, k)))))};
(PARI) T(n, k)=polcoeff(Ser(polcoeff(Ser((1+y*z)/(1-z*(1+y+y^2)), y), k, y), z), n, z)
(PARI) {T(n, k) = if( k<0 || k>2*n, 0, if(n==0, 1, polcoeff( (1 + x + x^2)^n, k)+ polcoeff( (1 + x + x^2)^(n-1), k-1)))};
CROSSREFS
KEYWORD
nonn,tabf,easy
AUTHOR
EXTENSIONS
Edited by Ralf Stephan, Jan 09 2005
Edited by Clark Kimberling, Jun 20 2012
STATUS
approved