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
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Jan 23 2012
STATUS
approved