login
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.
3
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
KEYWORD
nonn,tabl
AUTHOR
Peter Kagey, Nov 30 2021
STATUS
approved