asking for help in connection with a new sequence

[Max A.]

On 7/17/06, Max A. <maxale at gmail.com> 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.

[...]

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

I've found yet another formula using matrices.

Let rows and columns of 3x3 matrix A be enumerated with number 0,1,2.
We define element (i,j) as 1 if going i<j (i.e., transtition from i to
j does not increase the number of runs) and as x otherwise. So the
matrix A equals:
[ x 1 1 ]
[ x x 1 ]
[ x x x ]
Then T(n,k) is the coefficient of x^(k-1) in the sum of all elements
of A^(n-1). Equivalently,
T(n,k) = coefficient of x^(k-1) in [1,1,1] * A^(n-1) * [1,1,1]^T.

Let us use substitution x=y^3 to avoid dealing with fractional powers of x. Then
T(n,k) = coefficient of y^(3k-3) in [1,1,1] * B^(n-1) * [1,1,1]^T
where B =
[ y^3   1     1  ]
[ y^3  y^3   1  ]
[ y^3  y^3 y^3 ]

Let B be represented in a Jordan form: B = P*J*P^(-1). Then
T(n,k) = coefficient of y^(3k-3) in [1,1,1]*P * J^(n-1) * P^(-1)*[1,1,1]^T.

The characteristic polynomial of the matrix A is
w^3 - 3*y^3*w^2 + 3*y^3*(y^3-1)*w - y^3*(y^3-1)^2
= (w - (y^3 + y^2 + y)) * ( w^2 - y*(2*y+1)*(y-1)*w + y^2*(y^2+y+1)*(y-1)^2 )
Its roots (i.e., eigenvalues of A) form the diagonal of the diagonal matrix J:
J = diag( w0, w1, w2 )
where
w0 = y^3 + y^2 + y
w1 = (2*y + 1 + I*sqrt(3))*y*(y-1) / 2
w2 = (2*y + 1 - I*sqrt(3))*y*(y-1) / 2

Vectors [1,1,1]*P and P^(-1)*[1,1,1]^T equal:
[1,1,1]*P = [ w0/y, w1 + 1 - y^3, w2 + 1 - y^3] / 3
P^(-1)*[1,1,1]^T = [ w0, w1, w2 ] / y^3

Therefore,
T(n,k) = coefficient of y^(3k) in 1/3 * (w0^(n+1)/y + w1^(n+1) +
w2^(n+1) + (1-y^3)*(w1^n + w2^n))
BTW, from this formula one can obtain the generating function
(multiplying by z^n and summing over 0..oo).

To simplify further, consider values
z1 = (2*y + 1 + I*sqrt(3)) / 2
z2 = (2*y + 1 - I*sqrt(3)) / 2
that are roots of the equation z^2-(2*y+1)*z+(y^2+y+1)=0. Then
T(n,k) = coefficient of y^(3k-n) in 1/3 * ((1+y+y^2)^(n+1) +
(y-1)^(n+1)*[(y*z1-1-y-y^2)*z1^n + (y*z2-1-y-y^2)*z2^n]

Max