

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;
 R. J. Mathar, Mar 12 2013


LINKS

Table of n, a(n) for n=0..77.
D. S. Hirschberg, Algorithms for the longest subsequence problem, J. ACM, 24 (1977), 664675.
C. Kimberling, Pathcounting and Fibonacci numbers, Fib. Quart. 40 (4) (2002) 328338, Example 1E.
V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310332.


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

A055216 := proc(n, k)
a := 0 ;
for i from 0 to nk do
a := a+binomial(nk, i)*add(binomial(i, j), j=0..ki) ;
end do:
a ;
end proc: # R. J. Mathar, Mar 13 2013


MATHEMATICA

T[n_, k_] := Sum[Binomial[n  k, i]*Sum[Binomial[i, j], {j, 0, k  i}], {i, 0, n  k}];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* JeanFrançois Alcover, Oct 28 2019 *)


CROSSREFS

Row sums: A008937. Central numbers: T(2n, n)=A027914(n) for n >= 0.
Sequence in context: A157283 A067049 A090641 * A216236 A217770 A216219
Adjacent sequences: A055213 A055214 A055215 * A055217 A055218 A055219


KEYWORD

nonn,tabl


AUTHOR

Clark Kimberling, May 07 2000


EXTENSIONS

Better description and references from N. J. A. Sloane, Aug 05 2000


STATUS

approved



