A318120 Number of set partitions of {1,...,n} with relatively prime block sizes.

1, 1, 1, 4, 11, 51, 162, 876, 3761, 20782, 109293, 678569, 4038388, 27644436, 186524145, 1379760895, 10323844183, 82864869803, 674798169662, 5832742205056, 51385856585637, 474708148273586, 4486977535287371, 44152005855084345, 444577220573083896

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..576

Formula

a(n) = Sum_{|y| = n, GCD(y) = 1} n! / (Product_i y_i! * Product_i (y)_i!) where the sum is over all relatively prime integer partitions of n and (y)_i is the multiplicity of i in y.

Example

The a(4) = 11 set partitions:
  {{1},{2},{3},{4}}
   {{1},{2},{3,4}}
   {{1},{2,3},{4}}
   {{1},{2,4},{3}}
   {{1,2},{3},{4}}
   {{1,3},{2},{4}}
   {{1,4},{2},{3}}
    {{1},{2,3,4}}
    {{1,2,3},{4}}
    {{1,2,4},{3}}
    {{1,3,4},{2}}

Maple

b:= proc(n, t) option remember; `if`(n=0, `if`(t<2, 1, 0),
      add(b(n-j, igcd(t, j))*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 30 2019

Mathematica

numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
Table[Total[numSetPtnsOfType/@Select[IntegerPartitions[n], GCD@@#==1&]], {n, 10}]
(* Second program: *)
b[n_, t_] := b[n, t] = If[n == 0, If[t < 2, 1, 0],
     Sum[b[n - j, GCD[t, j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
a[n_] := b[n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)

Crossrefs

a(n) >= A271426(n).

Cf. A000110, A000258, A000311, A000670, A000740, A000837, A005651, A005804, A008277, A124794, A319182, A320289.

Sequence in context: A149315 A149316 A271426 * A355337 A218957 A149317

Adjacent sequences: A318117 A318118 A318119 * A318121 A318122 A318123

Keyword

nonn

Author

Gus Wiseman, Dec 16 2018

Status

approved