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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 16 2018
STATUS
approved