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.
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
KEYWORD
nonn
AUTHOR
David Pasino, Dec 06 2008, Dec 08 2008
STATUS
approved