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,3

Links

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

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

Example

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)

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}]

Prog

(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

Crossrefs

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

Sequence in context: A199494 A171791 A060908 * A036449 A051500 A206179

Adjacent sequences: A322439 A322440 A322441 * A322443 A322444 A322445

Keyword

nonn

Author

Gus Wiseman, Dec 08 2018

Extensions

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

Status

approved