A388718 Triangle read by rows: T(n,k) is the number of binary strings of length n which are not all zero and whose shortest run of 1's is of length k.

1, 2, 1, 4, 2, 1, 9, 3, 2, 1, 20, 5, 3, 2, 1, 43, 10, 4, 3, 2, 1, 91, 20, 6, 4, 3, 2, 1, 191, 38, 11, 5, 4, 3, 2, 1, 398, 70, 21, 7, 5, 4, 3, 2, 1, 824, 128, 38, 12, 6, 5, 4, 3, 2, 1, 1697, 234, 65, 22, 8, 6, 5, 4, 3, 2, 1, 3480, 427, 108, 39, 13, 7, 6, 5, 4, 3, 2, 1

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

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. 33, Sect. 2.7.

Formula

T(n,k) = A388146(n,k) - A388146(n,k+1) = A388547(n,k) - A388547(n,k+1).

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

Example

Triangle begins:
    1;
    2,   1;
    4,   2,  1;
    9,   3,  2,  1;
   20,   5,  3,  2, 1;
   43,  10,  4,  3, 2, 1;
   91,  20,  6,  4, 3, 2, 1;
  191,  38, 11,  5, 4, 3, 2, 1;
  398,  70, 21,  7, 5, 4, 3, 2, 1;
  824, 128, 38, 12, 6, 5, 4, 3, 2, 1;
  ...

Prog

(PARI) T(n, k)=sum(i=0, (n+1)\(k+1), binomial(n+1-(k-1)*i, 2*i) - binomial(n+1-k*i, 2*i))

Crossrefs

Columns 1..3 are A384153, A384154, A384155.

Row sums are A000225.

Cf. A048004, A388146, A388547.

Sequence in context: A274106 A354802 A158982 * A127124 A127136 A239101

Adjacent sequences: A388715 A388716 A388717 * A388719 A388720 A388721

Keyword

nonn,tabl

Author

Andrew Howroyd, Sep 19 2025

Status

approved