A318120 - OEIS

%I #22 May 10 2021 07:40:51

%S 1,1,1,4,11,51,162,876,3761,20782,109293,678569,4038388,27644436,

%T 186524145,1379760895,10323844183,82864869803,674798169662,

%U 5832742205056,51385856585637,474708148273586,4486977535287371,44152005855084345,444577220573083896

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

%H Alois P. Heinz, <a href="/A318120/b318120.txt">Table of n, a(n) for n = 0..576</a>

%F 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.

%e The a(4) = 11 set partitions:

%e   {{1},{2},{3},{4}}

%e    {{1},{2},{3,4}}

%e    {{1},{2,3},{4}}

%e    {{1},{2,4},{3}}

%e    {{1,2},{3},{4}}

%e    {{1,3},{2},{4}}

%e    {{1,4},{2},{3}}

%e     {{1},{2,3,4}}

%e     {{1,2,3},{4}}

%e     {{1,2,4},{3}}

%e     {{1,3,4},{2}}

%p b:= proc(n, t) option remember; `if`(n=0, `if`(t<2, 1, 0),

%p       add(b(n-j, igcd(t, j))*binomial(n-1, j-1), j=1..n))

%p     end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Dec 30 2019

%t numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];

%t Table[Total[numSetPtnsOfType/@Select[IntegerPartitions[n],GCD@@#==1&]],{n,10}]

%t (* Second program: *)

%t b[n_, t_] := b[n, t] = If[n == 0, If[t < 2, 1, 0],

%t      Sum[b[n - j, GCD[t, j]]*Binomial[n - 1, j - 1], {j, 1, n}]];

%t a[n_] := b[n, 0];

%t a /@ Range[0, 25] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)

%Y a(n) >= A271426(n).

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Dec 16 2018