A185158 Triangular array read by rows: T(n,k) (n>=1, 0<=k<=n-1, except 0<=k<=1 when n=1) = coefficient of x^k in expansion of (1/n)*Sum_{d|n} (mobius(d)*(1+x^d)^(n/d)).

1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1

Offset

1,14

Comments

T(n,k) is the number of binary Lyndon words of length n containing k ones. - Joerg Arndt, Oct 21 2012

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Joerg Arndt, Matters Computational (The Fxtbook), section 18.3.1 "Binary necklaces with fixed density", p. 382.

Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.

Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. See Example 1.

Formula

T(n,k) = 1/n * sum( d divides gcd(n,k), mu(d) * C(n/d,k/d) ). - Joerg Arndt, Oct 21 2012

The prime rows are given by (1+x)^p/p, rounding non-integer coefficients to 0, e.g., (1+x)^2/2 = .5 + x + .5 x^2 gives (0,1,0), row 2 below. - Tom Copeland, Oct 21 2014

Example

The first few polynomials are:
1+x
x
x+x^2
x+x^2+x^3
x+2*x^2+2*x^3+x^4
x+2*x^2+3*x^3+2*x^4+x^5
x+3*x^2+5*x^3+5*x^4+3*x^5+x^6
...
The triangle begins:
[ 1]  1, 1,
[ 2]  0, 1,
[ 3]  0, 1, 1,
[ 4]  0, 1, 1, 1,
[ 5]  0, 1, 2, 2, 1,
[ 6]  0, 1, 2, 3, 2, 1,
[ 7]  0, 1, 3, 5, 5, 3, 1,
[ 8]  0, 1, 3, 7, 8, 7, 3, 1,
[ 9]  0, 1, 4, 9, 14, 14, 9, 4, 1,
[10]  0, 1, 4, 12, 20, 25, 20, 12, 4, 1,
[11]  0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1,
[12]  0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1,
[13]  0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1,
[14]  0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1
...

Maple

with(numtheory);
W:=r->expand((1/r)*add(mobius(d)*(1+x^d)^(r/d), d in divisors(r)));
for n from 1 to 14 do
lprint(W(n));
od:
for n from 1 to 14 do
lprint(seriestolist(series(W(n), x, 50)));
od:

Mathematica

T[n_, k_] := DivisorSum[GCD[n, k], MoebiusMu[#] Binomial[n/#, k/#]&]/n; Table[T[n, k], {n, 1, 14}, {k, 0, Max[1, n-1]}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

Prog

(PARI)
p(n) = if(n<=0, n==0, 'a0 + 1/n * sumdiv(n, d, moebius(d)*(1+x^d)^(n/d) ));
/* print triangle: */
for (n=1, 17, v=Vec( polrecip(Pol(p(n), x)) ); v[1]-='a0; print(v) );
/* Joerg Arndt, Oct 21 2012 */
(PARI)
T(n, k) = 1/n * sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d) );
/* print triangle: */
{ for (n=1, 17, for (k=0, max(1, n-1), print1(T(n, k), ", "); ); print(); ); }
/* Joerg Arndt, Oct 21 2012 */

Crossrefs

Two other versions of this triangle are in A051168 and A092964.

Sequence in context: A104244 A116403 A123149 * A185700 A368494 A061926

Adjacent sequences: A185155 A185156 A185157 * A185159 A185160 A185161

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jan 23 2012

Status

approved