|
%I #24 Oct 28 2019 20:04:47
%S 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,
%T 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,
%U 168,147,76,27,9,3,1,1,11,55,157,274,294,192,80,27,9,3,1
%N Triangle T(n,k) by rows, n >= 0, 0<=k<=n: T(n,k) = Sum_{i=0..n-k} binomial(n-k,i) *Sum_{j=0..k-i} binomial(i,j).
%C 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.
%C T(i,j) is the 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).
%C 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.
%C T(n,k) is the 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_, Jul 25 2005
%C The matrix inverse starts:
%C 1;
%C -1,1;
%C 1,-2,1;
%C -1,3,-3,1;
%C 1,-4,6,-4,1;
%C -2,8,-13,11,-5,1;
%C 8,-30,45,-36,18,-6,1;
%C -36,137,-207,163,-78,27,-7,1;
%C 192,-732,1112,-884,425,-144,38,-8,1;
%C - _R. J. Mathar_, Mar 12 2013
%H D. S. Hirschberg, <a href="https://doi.org/10.1145/322033.322044">Algorithms for the longest subsequence problem</a>, J. ACM, 24 (1977), 664-675.
%H C. Kimberling, <a href="https://www.fq.math.ca/Scanned/40-4/kimberling.pdf">Path-counting and Fibonacci numbers</a>, Fib. Quart. 40 (4) (2002) 328-338, Example 1E.
%H V. I. Levenshtein, <a href="https://doi.org/10.1006/jcta.2000.3081">Efficient reconstruction of sequences from their subsequences or supersequences</a>, J. Combin. Theory Ser. A 93 (2001), no. 2, 310-332.
%F 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.
%e 8=T(5,2) counts these strings: 013, 023, 113, 123, 133, 223, 233, 333.
%e Rows:
%e 1;
%e 1,1;
%e 1,2,1;
%e 1,3,3,1;
%e 1,4,6,3,1;
%e ...
%p A055216 := proc(n,k)
%p a := 0 ;
%p for i from 0 to n-k do
%p a := a+binomial(n-k,i)*add(binomial(i,j),j=0..k-i) ;
%p end do:
%p a ;
%p end proc: # _R. J. Mathar_, Mar 13 2013
%t T[n_, k_] := Sum[Binomial[n - k, i]*Sum[Binomial[i, j], {j, 0, k - i}], {i, 0, n - k}];
%t Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Oct 28 2019 *)
%Y Row sums: A008937. Central numbers: T(2n, n)=A027914(n) for n >= 0.
%K nonn,tabl
%O 0,5
%A _Clark Kimberling_, May 07 2000
%E Better description and references from _N. J. A. Sloane_, Aug 05 2000
|
