A303551 Number of aperiodic multisets of compositions of total weight n.

1, 2, 6, 15, 41, 95, 243, 567, 1366, 3189, 7532, 17428, 40590, 93465, 215331, 493150, 1127978, 2569049, 5841442, 13240351, 29953601, 67596500, 152258270, 342235866, 767895382, 1719813753, 3845442485, 8584197657, 19133459138, 42583565928, 94641591888

Offset

1,2

Comments

A multiset is aperiodic if its multiplicities are relatively prime.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{d|n} mu(d) * A034691(n/d).

Example

The a(4) = 15 aperiodic multisets of compositions are:
{4}, {31}, {22}, {211}, {13}, {121}, {112}, {1111},
{1,3}, {1,21}, {1,12}, {1,111}, {2,11},
{1,1,2}, {1,1,11}.
Missing from this list are {1,1,1,1}, {2,2}, and {11,11}.

Maple

with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(
      d*2^(d-1), d=divisors(j))*b(n-j), j=1..n)/n)
    end:
a:= n-> add(mobius(d)*b(n/d), d=divisors(n)):
seq(a(n), n=1..35);  # Alois P. Heinz, Apr 26 2018

Mathematica

nn=20;
ser=Product[1/(1-x^n)^2^(n-1), {n, nn}]
Table[Sum[MoebiusMu[d]*SeriesCoefficient[ser, {x, 0, n/d}], {d, Divisors[n]}], {n, 1, nn}]

Prog

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
seq(n)={my(u=EulerT(vector(n, n, 2^(n-1)))); vector(n, n, sumdiv(n, d, moebius(d)*u[n/d]))} \\ Andrew Howroyd, Sep 15 2018

Crossrefs

Cf. A000740, A000837, A007716, A007916, A034691, A100953, A255906, A269134, A301700, A303386, A303431, A303546, A303552.

Sequence in context: A061322 A004664 A074446 * A180666 A280788 A121328

Adjacent sequences: A303548 A303549 A303550 * A303552 A303553 A303554

Keyword

nonn

Author

Gus Wiseman, Apr 26 2018

Status

approved