asking for help in connection with a new sequence

[Max A.]

On 7/16/06, Emeric Deutsch <deutsch at duke.poly.edu> wrote:

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

Could you please elaborate a little bit on how the 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].

I have not derived this particular formula yet but I've got another
"independent" formula:

T(n,k) = coefficient of x^(n-k) in [1,1,1] * M(x)^k * [1,0,0]^T
where the matrix M(x) is defined as
[ x^2+2*x+1   x^2+2*x    x^2 + x ]
[     x+1            x+1           x     ]
[       1               1            1     ]

PARI/GP code:
{ T(n,k)=polcoeff([1,1,1]*[x^2+2*x+1, x^2+2*x, x^2+x; x+1, x+1, x; 1,
1, 1]^k*[1,0,0]~,n-k) }
? matrix(7,7,n,k,T3(n-1,k-1))
[1 0 0 0 0 0 0]
[0 3 0 0 0 0 0]
[0 3 6 0 0 0 0]
[0 1 16 10 0 0 0]
[0 0 15 51 15 0 0]
[0 0 6 90 126 21 0]
[0 0 1 77 357 266 28]

I believe that this formula can be simplified to somewhat similar to
(*) (using Jordan forms etc.)

Max