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
Keywords
Examples
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)
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
Crossrefs
Programs
-
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 *) -
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
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.