A322442 Number of pairs of set partitions of {1,...,n} where every block of one is a subset or superset of some block of the other.

1, 1, 4, 25, 195, 1894, 22159, 303769, 4790858, 85715595, 1720097275, 38355019080, 942872934661, 25383601383937, 744118939661444, 23635548141900445, 809893084668253151, 29822472337116844174, 1175990509568611058299, 49504723853840395163221, 2218388253903492656783562

Offset: 0

Author

Gus Wiseman, Dec 08 2018

Keywords

• nonn

Examples

			The a(3) = 25 pairs of set partitions (these are actually all pairs of set partitions of {1,2,3}):
  (1)(2)(3)|(1)(2)(3)
  (1)(2)(3)|(1)(23)
  (1)(2)(3)|(12)(3)
  (1)(2)(3)|(13)(2)
  (1)(2)(3)|(123)
    (1)(23)|(1)(2)(3)
    (1)(23)|(1)(23)
    (1)(23)|(12)(3)
    (1)(23)|(13)(2)
    (1)(23)|(123)
    (12)(3)|(1)(2)(3)
    (12)(3)|(1)(23)
    (12)(3)|(12)(3)
    (12)(3)|(13)(2)
    (12)(3)|(123)
    (13)(2)|(1)(2)(3)
    (13)(2)|(1)(23)
    (13)(2)|(12)(3)
    (13)(2)|(13)(2)
    (13)(2)|(123)
      (123)|(1)(2)(3)
      (123)|(1)(23)
      (123)|(12)(3)
      (123)|(13)(2)
      (123)|(123)
Non-isomorphic representatives of the pairs of set partitions of {1,2,3,4} for which the condition fails:
    (12)(34)|(13)(24)
    (12)(34)|(1)(3)(24)
  (1)(2)(34)|(13)(24)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A000110, A000258, A001247, A008277, A059849, A060639, A181939, A318393, A322435, A322437, A322439, A322440, A322441.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
costabQ[s_,t_]:=And@@Cases[s,x_:>Select[t,SubsetQ[x,#]||SubsetQ[#,x]&]!={}];
Table[Length[Select[Tuples[sps[Range[n]],2],And[costabQ@@#,costabQ@@Reverse[#]]&]],{n,5}]

PARI

F(x)={my(bell=(exp(y*(exp(x) - 1))  )); subst(serlaplace( serconvol(bell, bell)), y, exp(exp(x) - 1)-1)}
seq(n) = {my(x=x + O(x*x^n)); Vec(serlaplace( exp( 2*exp(exp(x) - 1) - exp(x) - 1) * F(x) ))} \\ Andrew Howroyd, Jan 19 2024

Formula

E.g.f.: exp(exp(x)-1) * (2*B(x) - 1) where B(x) is the e.g.f. of A319884. - Andrew Howroyd, Jan 19 2024

Extensions

a(8) onwards from Andrew Howroyd, Jan 19 2024