cp's OEIS Frontend

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

%I A318120 #22 May 10 2021 07:40:51
%S A318120 1,1,1,4,11,51,162,876,3761,20782,109293,678569,4038388,27644436,
%T A318120 186524145,1379760895,10323844183,82864869803,674798169662,
%U A318120 5832742205056,51385856585637,474708148273586,4486977535287371,44152005855084345,444577220573083896
%N A318120 Number of set partitions of {1,...,n} with relatively prime block sizes.
%H A318120 Alois P. Heinz, <a href="/A318120/b318120.txt">Table of n, a(n) for n = 0..576</a>
%F A318120 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 A318120 The a(4) = 11 set partitions:
%e A318120   {{1},{2},{3},{4}}
%e A318120    {{1},{2},{3,4}}
%e A318120    {{1},{2,3},{4}}
%e A318120    {{1},{2,4},{3}}
%e A318120    {{1,2},{3},{4}}
%e A318120    {{1,3},{2},{4}}
%e A318120    {{1,4},{2},{3}}
%e A318120     {{1},{2,3,4}}
%e A318120     {{1,2,3},{4}}
%e A318120     {{1,2,4},{3}}
%e A318120     {{1,3,4},{2}}
%p A318120 b:= proc(n, t) option remember; `if`(n=0, `if`(t<2, 1, 0),
%p A318120       add(b(n-j, igcd(t, j))*binomial(n-1, j-1), j=1..n))
%p A318120     end:
%p A318120 a:= n-> b(n, 0):
%p A318120 seq(a(n), n=0..25);  # _Alois P. Heinz_, Dec 30 2019
%t A318120 numSetPtnsOfType[ptn_]:=Total[ptn]!/Times@@Factorial/@ptn/Times@@Factorial/@Length/@Split[ptn];
%t A318120 Table[Total[numSetPtnsOfType/@Select[IntegerPartitions[n],GCD@@#==1&]],{n,10}]
%t A318120 (* Second program: *)
%t A318120 b[n_, t_] := b[n, t] = If[n == 0, If[t < 2, 1, 0],
%t A318120      Sum[b[n - j, GCD[t, j]]*Binomial[n - 1, j - 1], {j, 1, n}]];
%t A318120 a[n_] := b[n, 0];
%t A318120 a /@ Range[0, 25] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)
%Y A318120 a(n) >= A271426(n).
%Y A318120 Cf. A000110, A000258, A000311, A000670, A000740, A000837, A005651, A005804, A008277, A124794, A319182, A320289.
%K A318120 nonn
%O A318120 0,4
%A A318120 _Gus Wiseman_, Dec 16 2018