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,2

Links

Table of n, a(n) for n=0..55.

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 19.

Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting Pattern-Avoiding Permutations by Big Descents, Ann. Comb. (2026). See also arXiv:2408.15111 [math.CO], 2024. See p. 6 (Table 1).

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009. See p. 304.

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))).

Example

Triangle begins:
  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.

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

Crossrefs

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

Row sums give A000079.

Sequence in context: A238344 A299072 A169820 * A352525 A114711 A246186

Adjacent sequences: A334655 A334656 A334657 * A334659 A334660 A334661

Keyword

nonn,tabf

Author

Geoffrey Critzer, Jul 25 2020

Status

approved