A349802 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; table; graph; refs; listen; history; text; internal format)

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