

A055216


Triangle T(n,k) by rows, n >= 0, 0<=k<=n: T(n,k) = Sum_{i=0..nk} binomial(nk,i) *Sum_{j=0..ki} binomial(i,j).


8



1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 3, 1, 1, 5, 10, 8, 3, 1, 1, 6, 15, 17, 9, 3, 1, 1, 7, 21, 31, 23, 9, 3, 1, 1, 8, 28, 51, 50, 26, 9, 3, 1, 1, 9, 36, 78, 96, 66, 27, 9, 3, 1, 1, 10, 45, 113, 168, 147, 76, 27, 9, 3, 1, 1, 11, 55, 157, 274, 294, 192, 80, 27, 9, 3, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

T(n,k) is the maximal number of different sequences that can be obtained from a ternary sequence of length n by deleting k symbols.
T(i,j) is the number of paths from (0,0) to (ij,j) using steps (1 unit right) or (1 unit right and 1 unit up) or (1 unit right and 2 units up).
If m >= 1 and n >= 2, then T(m+n1,m) is the number of strings (s(1),s(2),...,s(n)) of nonnegative integers satisfying s(n)=m and 0<=s(k)s(k1)<=2 for k=2,3,...,n.
T(n,k) is the number of 1100avoiding 01 sequences of length n containing k good 1's. A 1 is bad if it is immediately followed by two or more 1's and then a 0; otherwise it is good. In particular, a 1 with no 0's to its right is good. For example, 110101110111 is 1100avoiding and only the 1 in position 6 is bad and T(4,3) counts 0111, 1011, 1101.  David Callan, Jul 25 2005
The matrix inverse starts:
1;
1,1;
1,2,1;
1,3,3,1;
1,4,6,4,1;
2,8,13,11,5,1;
8,30,45,36,18,6,1;
36,137,207,163,78,27,7,1;
192,732,1112,884,425,144,38,8,1;


LINKS



FORMULA

T(i, 0)=T(i, i)=1 for i >= 0; T(i, 1)=T(i, i1)=i for i >= 2; T(i, j)=T(i1, j)+T(i2, j1)+T(i3, j2) for 2<=j<=i2, i >= 3.


EXAMPLE

8=T(5,2) counts these strings: 013, 023, 113, 123, 133, 223, 233, 333.
Rows:
1;
1,1;
1,2,1;
1,3,3,1;
1,4,6,3,1;
...


MAPLE

a := 0 ;
for i from 0 to nk do
a := a+binomial(nk, i)*add(binomial(i, j), j=0..ki) ;
end do:
a ;


MATHEMATICA

T[n_, k_] := Sum[Binomial[n  k, i]*Sum[Binomial[i, j], {j, 0, k  i}], {i, 0, n  k}];


CROSSREFS



KEYWORD



AUTHOR



EXTENSIONS



STATUS

approved



