login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set. 2
0, 0, 1, 7, 65, 811, 12762, 244588, 5574956, 148332645, 4538695461, 157768581675, 6167103354744, 268758895112072, 12961171404183498, 687270616305277589, 39843719438374998543, 2512873126513271758171, 171643113190082528007702, 12647168303374365311984284 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 04:48 EST 2020. Contains 332011 sequences. (Running on oeis4.)