A119851 Triangle read by rows: T(n,k) is the number of ternary words of length n containing k 012's (n >= 0, 0 <= k <= floor(n/3)).

1, 3, 9, 26, 1, 75, 6, 216, 27, 622, 106, 1, 1791, 387, 9, 5157, 1350, 54, 14849, 4566, 267, 1, 42756, 15102, 1179, 12, 123111, 49113, 4833, 90, 354484, 157622, 18798, 536, 1, 1020696, 500520, 70317, 2775, 15, 2938977, 1575558, 255231, 13068, 135

Offset: 0

Author

Emeric Deutsch, May 26 2006

Keywords

• nonn
• tabf

Comments

Row n has 1+floor(n/3) terms.

Sum of entries in row n is 3^n (A000244).

Sum_{k>=0} k*T(n,k) = (n-2)*3^(n-3) = A027741(n-1).

Examples

			T(4,1)=6 because we have 0012, 0120, 0121, 0122, 1012 and 2012.
Triangle starts:
    1;
    3;
    9;
   26,   1;
   75,   6;
  216,  27;
  622, 106, 1;
		

Crossrefs

Cf. A000244, A076264 (=T(n,0)), A119852 (=T(n,1)), A027741.

Programs

Maple

G:=1/(1-3*z+z^3-t*z^3): Gser:=simplify(series(G,z=0,20)): P[0]:=1: for n from 1 to 15 do P[n]:=sort(coeff(Gser,z^n)) od: for n from 0 to 15 do seq(coeff(P[n],t,j),j=0..floor(n/3)) od; # yields sequence in triangular form

PARI

{ T(n,k) = sum(j=0,n-3*k, if((n-3*k-j)%2,0, binomial(-(k-1),j) *
binomial(j,(n-3*k-j)/2) * (-3)^((3*j+3*k-n)/2) )) } \\ Max Alekseyev

Formula

T(n,k) = Sum_{j=0..n-3k} binomial(-(k-1),j) * binomial(j,(n-3k-j)/2) * (-3)^((3j+3k-n)/2). - Max Alekseyev

G.f.: G(t,z) = 1/(1-3z+z^3-tz^3).

Recurrence relation: T(n,k) = 3*T(n-1,k) - T(n-3,k) + T(n-3,k-1) for n >= 3.