A320768 Number of set partitions of the set of nonempty subsets of {1,...,n} where each block's elements are pairwise disjoint sets.

1, 1, 2, 15, 2420, 333947200

Offset: 0

Author

Gus Wiseman, Dec 09 2018

Keywords

• nonn
• more

Examples

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

Crossrefs

Cf. A000110, A000258, A008277, A318391, A318392, A318393, A318394, A319884.

Programs

Mathematica

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
sps[set_]:=spsu[Rest[Subsets[set]],set];
Table[Length[spsu[Sort/@Union@@sps/@Rest[Subsets[Range[n]]],Rest[Subsets[Range[n]]]]],{n,4}]

Extensions

a(5) from, and definition clarified by Christian Sievers, Nov 30 2024