A171855 Triangle read by rows: T(n,k) is the number of binary words of length n that have no pair of adjacent 1's and have k subwords 0000 (n>=0; k=0 for n=0,1,2; 0<=k<=n-3 for n>=3).

1, 2, 3, 5, 7, 1, 10, 2, 1, 15, 3, 2, 1, 22, 6, 3, 2, 1, 32, 11, 6, 3, 2, 1, 47, 18, 12, 6, 3, 2, 1, 69, 30, 20, 13, 6, 3, 2, 1, 101, 50, 34, 22, 14, 6, 3, 2, 1, 148, 81, 59, 38, 24, 15, 6, 3, 2, 1, 217, 130, 99, 68, 42, 26, 16, 6, 3, 2, 1, 318, 208, 163, 118, 77, 46, 28, 17, 6, 3, 2, 1, 466

Offset: 0

Author

Emeric Deutsch, Feb 15 2010

Keywords

• nonn
• tabf

Comments

Row n has n-2 entries.

Sum of entries in row n is the Fibonacci number A000045(n+2).

T(n,0)=A003410(n). Sum(k*T(n,k),k>=0)=A004798(n-3) for n>=4.

Examples

			T(5,1)=2 because we have 00001 and 10000; T(7,2)=3 because we have 0000010, 0100000, and 1000001.
Triangle starts:
1;
2;
3;
5;
7,1;
10,2,1;
15,3,2,1;
22,6,3,2,1;
		

Crossrefs

Cf. A000045, A003410, A004798.

Programs

Maple

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

Formula

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