A391669 Triangle read by rows: T(n,k) is the number of binary strings of length n that contain exactly k runs of 1's of even length, 0 <= k <= floor((n+1)/3).

1, 2, 3, 1, 6, 2, 10, 6, 19, 12, 1, 33, 28, 3, 61, 56, 11, 108, 119, 28, 1, 197, 236, 75, 4, 352, 479, 176, 17, 638, 940, 417, 52, 1, 1145, 1859, 930, 157, 5, 2069, 3612, 2067, 420, 24, 3721, 7028, 4450, 1099, 85, 1, 6714, 13538, 9513, 2712, 285, 6

Offset

0,2

Links

Alois P. Heinz, Rows n = 0..345, flattened

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. 38, Sect. 2.8.

Formula

G.f. of column k: x^(3*k-1) * (1-x^2) / (1-x-2*x^2+x^3)^(k+1).

Example

Triangle begins:
  1;
  2;
  3,    1;
  6,    2;
  10,   6;
  19,   12,    1;
  33,   28,    3;
  61,   56,    11;
  108,  119,   28,   1;
  197,  236,   75,   4;
  352,  479,   176,  17;
  638,  940,   417,  52,   1;
  1145, 1859,  930,  157,  5;
  2069, 3612,  2067, 420,  24;
  3721, 7028,  4450, 1099, 85,  1;
  6714, 13538, 9513, 2712, 285, 6;
  ...
where row sums are 2^n.

Maple

b:= proc(n, t) option remember; expand(`if`(n=0, 1, add(
      b(n-j, 1-t)*`if`(t=1 and j::even, x, 1), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
             add(b(n, i), i=0..signum(n))):
seq(T(n), n=0..15);  # Alois P. Heinz, Dec 26 2025

Mathematica

b[n_, t_] := b[n, t] = Expand[If[n == 0, 1, Sum[b[n - j, 1 - t]*If[t == 1 && EvenQ[j], x, 1], {j, 1, n}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][Sum[b[n, i], {i, 0, Sign[n]}]];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Mar 30 2026, after Alois P. Heinz *)

Crossrefs

Cf. A000079, A119473 (the same for odd length).

Cf. A028495 (column 0), A384497 (column 1).

Sequence in context: A062565 A175137 A156344 * A218796 A119440 A165742

Adjacent sequences: A391666 A391667 A391668 * A391670 A391671 A391672

Keyword

nonn,tabf

Author

Félix Balado, Dec 16 2025

Status

approved