A334658 Triangular array read by rows. T(n,k) is the number of length n words on alphabet {0,1} with k maximal runs of 0's having length 2 or more, n>=0, 0<=k<=nearest integer to n/3.

1, 2, 3, 1, 5, 3, 8, 8, 13, 18, 1, 21, 38, 5, 34, 76, 18, 55, 147, 53, 1, 89, 277, 139, 7, 144, 512, 336, 32, 233, 932, 766, 116, 1, 377, 1676, 1670, 364, 9, 610, 2984, 3516, 1032, 50, 987, 5269, 7198, 2714, 215, 1, 1597, 9239, 14402, 6734, 785, 11

Offset: 0

Author

Geoffrey Critzer, Jul 25 2020

Keywords

• nonn
• tabf

Examples

			1,
2,
3,  1,
5,  3,
8,  8,
13, 18,  1,
21, 38,  5,
34, 76,  18,
55, 147, 53, 1
T(6,2) = 5 because we have: 000100, 001000, 001001, 001100, 100100.
		

Links

• Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See p. 6.
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 304.

Crossrefs

Cf. A000045 (column k=0) A006478 (column k=1).

Row sums give A000079.

Programs

Mathematica

nn = 15; c[z_, u_] := ((1 - z^r)/(1 - z) + u z^r/(1 - z))*1/(1 - z ((1 - z^r)/(1 - z) + u z^r/(1 - z))) /. r -> 2; Map[Select[#, # > 0 &] &, CoefficientList[Series[c[z, u], {z, 0, nn}], {z, u}]] // Grid

Formula

O.g.f.: ((u x^2)/(1 - x) + (1 - x^2)/(1 - x))/(1 - x ((u x^2)/(1 - x) + (1 - x^2)/(1 - x))).

Generally, the o.g.f. for such words having maximal runs of length at least r is: ((u x^r)/(1 - x) + (1 - x^r)/(1 - x))/(1 - x ((u x^r)/(1 - x) + (1 - x^r)/(1 - x))).