# 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).

```