A119808 Triangle read by rows: T(n,k) is the number of ternary words of length n having k runs of consecutive 0's (0<=k<=ceiling(n/2)).

1, 2, 1, 4, 5, 8, 17, 2, 16, 49, 16, 32, 129, 78, 4, 64, 321, 300, 44, 128, 769, 1002, 280, 8, 256, 1793, 3048, 1352, 112, 512, 4097, 8678, 5500, 880, 16, 1024, 9217, 23524, 19892, 5120, 272, 2048, 20481, 61410, 66032, 24600, 2544, 32, 4096, 45057, 155616, 205360

Offset: 0

Author

Emeric Deutsch, May 25 2006

Keywords

• nonn
• tabf

Comments

Row n contains 1+ceiling(n/2) terms. T(n,0) = 2^n (A000079). T(n,1) = 1+(n-1)*2^n = A000337(n) for n>=1. T(n,2) = 2*A055581(n-3) (n>=3). Sum(k*T(n,k),k>=0) = A081038(n-1).

Examples

			T(2,1) = 5 because we have 00, 01, 02, 10 and 20.
Triangle starts:
1;
2,1;
4,5;
8,17,2;
16,49,16;
32,129,78,4;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A000079, A000337, A055581, A081038, A034839.

Programs

Maple

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

Mathematica

nn=15;f[list_]:=Select[list,#>0&]; a = y x/(1-x) +1;Map[f,CoefficientList[ Series[a/(1-2x a),{x,0,nn}],{x,y}]]//Grid  (* Geoffrey Critzer, Nov 19 2012 *)

Formula

G.f.: (1-z+tz)/(1-3z+2z^2-2tz^2). G.f. of column k: 2^(k-1)*z^(2k-1)*/ [(1-z)^k*(1-2z)^(k+1)] (k>=1). Recurrence relation: T(n,k) = 3T(n-1,k) -2T(n-2,k) +2T(n-2,k-1) for n>=2.