login
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
OFFSET
0,4
LINKS
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
KEYWORD
nonn
AUTHOR
David Pasino, Dec 06 2008, Dec 08 2008
STATUS
approved