A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.

0, 0, 1, 7, 65, 811, 12762, 244588, 5574956, 148332645, 4538695461, 157768581675, 6167103354744, 268758895112072, 12961171404183498, 687270616305277589, 39843719438374998543, 2512873126513271758171, 171643113190082528007702, 12647168303374365311984284

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Frank Ruskey and Jennifer Woodcock, The Rand and block distances of pairs of set partitions, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.

Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From N. J. A. Sloane, Oct 03 2012

Formula

a(n) = Sum_{k=0..n} binomial(n,k) * (Sum_{j=0..n-k} (-1)^j*A048993(n-k,j)) * binomial(A000110(k),2).

That is, summed on k from 0 to n, the number of k-element subsets of an n-element set, times the alternating sum of row n-k of Stirling2 numbers starting with +S(n-k, 0), times the number of pairs of partitions of k elements.

Obtained by inverting (binomial(A000110(n), 2)) = (Sum_{k=0..n} binomial(n,k)*A000110(n-k)*a(k)), which in turn is gotten by considering that a pair of conjoint partitions is gotten by choosing a partition of a subset and then choosing a pair of disjoint partitions of the complement.

Example

From Gus Wiseman, Dec 09 2018: (Start)
The a(3) = 7 unordered pairs:
  {{1},{2},{3}}| {{1,2,3}}
   {{1},{2,3}} |{{1,2},{3}}
   {{1},{2,3}} |{{1,3},{2}}
   {{1,2},{3}} |{{1,3},{2}}
   {{1},{2,3}} | {{1,2,3}}
   {{1,2},{3}} | {{1,2,3}}
   {{1,3},{2}} | {{1,2,3}}
(End)

Maple

a:= n-> add(binomial(n, k)*binomial(combinat[bell](k), 2)*
        add(Stirling2(n-k, j)*(-1)^j, j=0..n-k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 27 2018

Mathematica

Array[Sum[Binomial[#, k] Sum[(-1)^j*StirlingS2[# - k, j], {j, 0, # - k}] Binomial[BellB@ k, 2], {k, 0, #}] &, 20, 0] (* Michael De Vlieger, May 27 2018 *)

Prog

(PARI) a000110(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
a(n) = sum(k=0, n, binomial(n, k) * sum(j=0, n-k, (-1)^j*stirling(n-k, j, 2) * binomial(a000110(k), 2))); \\ Michel Marcus, May 27 2018

Crossrefs

Cf. A000110, A000258, A001247, A008277, A048993, A059849, A060639, A181939, A193297, A318393, A322441, A322442, A320768.

Sequence in context: A085283 A069015 A097819 * A272646 A220067 A109779

Adjacent sequences: A152522 A152523 A152524 * A152526 A152527 A152528

Keyword

nonn

Author

David Pasino, Dec 06 2008, Dec 08 2008

Status

approved