A349802 Triangle read by rows: T(n,k) is the number of binary Lyndon words of length n that begin with exactly k 0's. 0 <= k <= n.

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 3, 2, 1, 1, 0, 0, 4, 6, 4, 2, 1, 1, 0, 0, 5, 10, 7, 4, 2, 1, 1, 0, 0, 8, 18, 14, 8, 4, 2, 1, 1, 0, 0, 11, 31, 26, 15, 8, 4, 2, 1, 1, 0, 0, 18, 56, 50, 30, 16, 8, 4, 2, 1, 1, 0

Offset

0,17

Comments

Rows sum to A001037.

Conjecture: The Euler transform of column k=1 gives the Fibonacci numbers, the Euler transform of column k=2 gives the tribonacci numbers (A000073), and more generally, the Euler transform of column k >= 1 gives the (k+1)-bonacci numbers (A048887).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows n=0..50)

Formula

T(n,n) = 0 for n >= 2.

T(n,n-1) = 1 for n >= 1.

T(n,n-m) = 2^(m-2) for n >= 2*m - 1 and m >= 2.

Example

For n = 6, the values correspond to the following Lyndon words:
T(6,1) = 2 via 010111 and 011111;
T(6,2) = 3 via 001011, 001101, and 001111;
T(6,3) = 2 via 000101 and 000111;
T(6,4) = 1 via 000011; and
T(6,5) = 1 via 000001.
Table begins:
n\k | 0  1   2   3  4  5  6  7  8  9
----+------------------------------------
  0 | 1
  1 | 1, 1
  2 | 0, 1,  0
  3 | 0, 1,  1,  0
  4 | 0, 1,  1,  1, 0
  5 | 0, 2,  2,  1, 1, 0
  6 | 0, 2,  3,  2, 1, 1, 0
  7 | 0, 4,  6,  4, 2, 1, 1, 0
  8 | 0, 5, 10,  7, 4, 2, 1, 1, 0
  9 | 0, 8, 18, 14, 8, 4, 2, 1, 1, 0
  ...

Prog

(PARI)
B(k, n)=my(g=1/(1 - x*(1-x^k)/(1-x))); Vec(1 + sum(j=1, n, moebius(j)/j * log(subst(g + O(x*x^(n\j)), x, x^j))))
A(n, m)={my(M=Mat(vector(m, k, Col(B(k, n) - B(k-1, n))))); M[1, 1]=M[2, 2]=1; M}
{ my(M=A(10, 10)); for(n=1, #M, print(M[n, 1..n])) } \\ Andrew Howroyd, Dec 05 2021

Crossrefs

Cf. A000045, A000073, A001037, A006206 (k=1), A048887.

Sequence in context: A274370 A128521 A090477 * A368753 A345907 A293019

Adjacent sequences: A349799 A349800 A349801 * A349803 A349804 A349805

Keyword

nonn,tabl

Author

Peter Kagey, Nov 30 2021

Status

approved