asking for help in connection with a new sequence
Emeric Deutsch
deutsch at duke.poly.edu
Sun Jul 16 21:12:16 CEST 2006
Dear Seqfans,
I intend to submit soon a sequence (actually, a triangle), defined by:
T(n,k) is the number of ternary words of length n on {0,1,2} with k
strictly increasing runs (0<=k<=n). For example, the ternary word
2002100120001 has 9 strictly increasing runs: 2-0-02-1-0-012-0-0-01.
(In the case of binary sequences, it is sequence A119900).
The sequence starts:
1;
0,3;
0,3,6;
0,1,16,10;
0,0,15,51,15;
0,0,6,90,126,21;
Rather laboriously I have derived the bivariate g.f.:
G(t,z)=1/[1-3tz-3t(1-t)z^2-t(1-t)^2*z^3],
which, by expansion, yields the sequence.
Then, ONLY by inspection I noticed that
(*) T(n,k)=coefficient of x^(3n-3k+2) in (1+x+x^2)^(n+1),
i.e. the trinomial coefficient [n+1,3; 3n-3k+2]=[n+1,3; 3k-n].
Consequently, making use of a formula from Mathworld, we have
T(n,k)=sum((-1)^j*binomial(n+1,j)*binomial(2n+2-2j,3k-j-n),j=0..n+1).
My question: can somebody derive (*) either (i) from the generating
function or (ii) combinatorially ?
Many thanks,
Emeric
P.S. In the binary case (A119900) the column sums in the triangle
are the even-indexed Fibonacci numbers while in the above triangle
they form a trisection of the tribonacci numbers (A099464).
More information about the SeqFan
mailing list