A388146 Array read by antidiagonals: T(n,k) is the number of length n binary words in which 1's occur in blocks of at least k, n >= 0, k >= 1.

1, 1, 2, 1, 1, 4, 1, 1, 2, 8, 1, 1, 1, 4, 16, 1, 1, 1, 2, 7, 32, 1, 1, 1, 1, 4, 12, 64, 1, 1, 1, 1, 2, 7, 21, 128, 1, 1, 1, 1, 1, 4, 11, 37, 256, 1, 1, 1, 1, 1, 2, 7, 17, 65, 512, 1, 1, 1, 1, 1, 1, 4, 11, 27, 114, 1024, 1, 1, 1, 1, 1, 1, 2, 7, 16, 44, 200, 2048

Offset

0,3

Comments

In other words, T(n,k) is the number of binary strings of length n without maximal runs of ones of length < k.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]

Formula

T(n,k) = Sum_{i=0..floor((n+1)/(k+1))} binomial(n+1-(k-1)*i,2*i).

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

Example

Array begins:
=================================
n\k |   1  2  3  4  5 6 7 8 9
----+----------------------------
  0 |   1  1  1  1  1 1 1 1 1 ...
  1 |   2  1  1  1  1 1 1 1 1 ...
  2 |   4  2  1  1  1 1 1 1 1 ...
  3 |   8  4  2  1  1 1 1 1 1 ...
  4 |  16  7  4  2  1 1 1 1 1 ...
  5 |  32 12  7  4  2 1 1 1 1 ...
  6 |  64 21 11  7  4 2 1 1 1 ...
  7 | 128 37 17 11  7 4 2 1 1 ...
  8 | 256 65 27 16 11 7 4 2 1 ...
  ...

Prog

(PARI) T(n, k) = polcoef((1 - x + x^k)/(1 - 2*x + x^2 - x^(k+1)) + O(x*x^n), n)
(Python)
from sympy import Matrix
from math import isqrt, comb
def A388146_T(n, k):
    if k == 1: return 1<<n
    A = Matrix([[2, -1]+[0]*(k-2)+[1]]+[[0]*i+[1]+[0]*(k-i) for i in range(k)])
    return (A**(n-k+1)*Matrix([1]*(k+1)))[0]
def A388146(n):
    a = (m:=isqrt(k:=n+1<<1))+(k>m*(m+1))
    x = n-comb(a, 2)
    return A388146_T(x, a-x) # Chai Wah Wu, Jun 11 2026

Crossrefs

Columns k=1..7 are A000079, A005251(n+2), A005252(n+1), A005253, A005689(n+2), A098574(n+1), A217838(n-6).

Cf. A000124, A048887, A217839.

Sequence in context: A333810 A205592 A099238 * A306846 A327315 A141450

Adjacent sequences: A388143 A388144 A388145 * A388147 A388148 A388149

Keyword

nonn,tabl

Author

Andrew Howroyd, Sep 15 2025

Status

approved