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
Examples
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 ...
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.
Programs
-
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 *) -
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 */
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
Comments