0,5

T(n,k) = maximal number of different sequences that can be obtained from a ternary sequence of length n by deleting k symbols.

T(i,j) = number of paths from (0,0) to (i-j,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+n-1,m) is the number of strings (s(1),s(2),...,s(n)) of nonnegative integers satisfying s(n)=m and 0<=s(k)-s(k-1)<=2 for k=2,3,...,n.

T(n,k) = number of 1100-avoiding 0-1 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 1100-avoiding and only the 1 in position 6 is bad and T(4,3) counts 0111, 1011, 1101. - David Callan (callan(AT)stat.wisc.edu), Jul 25 2005

D. S. Hirschberg, Algorithms for the longest subsequence problem, J. ACM, 24 (1977), 664-675.

V. I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.

T(i, 0)=T(i, i)=1 for i >= 0; T(i, 1)=T(i, i-1)=i for i >= 2; T(i, j)=T(i-1, j)+T(i-2, j-1)+T(i-3, j-2) for 2<=j<=i-2, i >= 3.

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} ...

Row sums: A008937. Central numbers: T(2n, n)=A027914(n) for n >= 0.

Sequence in context: A157283 A067049 A090641 this_sequence A128629 A107065 A008975

Adjacent sequences: A055213 A055214 A055215 this_sequence A055217 A055218 A055219

nonn,tabl

Clark Kimberling (ck6(AT)evansville.edu), May 07 2000

Better description and references from N. J. A. Sloane (njas(AT)research.att.com), Aug 05 2000