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

1, 0, 1, 7, 50, 481, 5667, 78058, 1238295, 22314627, 451354476, 10148011215, 251584513215, 6831141750512, 201976943666357, 6470392653260939, 223595676728884394, 8302299221314559877, 330075531021130110015, 14006780163088113914026, 632606447496264724088803

Offset

0,4

Links

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

Formula

E.g.f.: (1/2)*(1 + D(x, exp(exp(x) - 1) - 1) ) where D(x,y) = (exp(2*y)/(1 + y)^2) * Sum_{k>=0} x^k*(Sum_{j=0..k} Stirling2(k,j)*y^j)^2/k!. - Andrew Howroyd, Jan 20 2024

Example

The a(3) = 7 pairs of set partitions:
  (1)(2)(3)|(123)
    (1)(23)|(12)(3)
    (1)(23)|(13)(2)
    (1)(23)|(123)
    (12)(3)|(13)(2)
    (12)(3)|(123)
    (13)(2)|(123)

Mathematica

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
costabstrQ[s_, t_]:=And@@Cases[s, x_:>Select[t, x!=#&&(SubsetQ[x, #]||SubsetQ[#, x])&]!={}];
Table[Length[Select[Subsets[sps[Range[n]], {2}], And[costabstrQ@@#, costabstrQ@@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( 1 + exp( 2*(exp(exp(x) - 1) - exp(x)) ) * F(x) )/2)} \\ Andrew Howroyd, Jan 19 2024
(PARI) \\ 2nd prog, following formula - slightly slower
D(n, y) = (exp(2*y)/(1 + y)^2) * sum(k=0, n, x^k*sum(j=0, k, stirling(k, j, 2) * y^j)^2/k!, O(x*x^n))
seq(n) = Vec(serlaplace((1/2)*(1 + D(n, exp(exp(x + O(x*x^n)) - 1) - 1)))) \\ Andrew Howroyd, Jan 20 2024

Crossrefs

Cf. A000110, A000258, A001247, A008277, A059849, A060639, A181939, A322435, A322436, A322437, A322438, A322439, A322440, A322441, A322442.

Sequence in context: A369473 A267243 A197570 * A204463 A041086 A197890

Adjacent sequences: A319881 A319882 A319883 * A319885 A319886 A319887

Keyword

nonn

Author

Gus Wiseman, Dec 09 2018

Extensions

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

Status

approved