login
A318120
Number of set partitions of {1,...,n} with relatively prime block sizes.
1
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
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 *)
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 16 2018
STATUS
approved