cp's OEIS Frontend

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

%I A152525 #43 Dec 17 2019 05:35:53
%S A152525 0,0,1,7,65,811,12762,244588,5574956,148332645,4538695461,
%T A152525 157768581675,6167103354744,268758895112072,12961171404183498,
%U A152525 687270616305277589,39843719438374998543,2512873126513271758171,171643113190082528007702,12647168303374365311984284
%N A152525 a(n) is the number of unordered pairs of disjoint set partitions of an n-element set.
%H A152525 Alois P. Heinz, <a href="/A152525/b152525.txt">Table of n, a(n) for n = 0..200</a>
%H A152525 Frank Ruskey and Jennifer Woodcock, <a href="http://webhome.cs.uvic.ca/~ruskey/Publications/RandDist/RandDist.html">The Rand and block distances of pairs of set partitions</a>, Combinatorial algorithms, 287-299, Lecture Notes in Comput. Sci., 7056, Springer, Heidelberg, 2011.
%H A152525 Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, <a href="https://doi.org/10.1016/j.jda.2012.04.003">Counting and computing the Rand and block distances of pairs of set partitions</a>, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236-248. - From _N. J. A. Sloane_, Oct 03 2012
%F A152525 a(n) = Sum_{k=0..n} binomial(n,k) * (Sum_{j=0..n-k} (-1)^j*A048993(n-k,j)) * binomial(A000110(k),2).
%F A152525 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.
%F A152525 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.
%e A152525 From _Gus Wiseman_, Dec 09 2018: (Start)
%e A152525 The a(3) = 7 unordered pairs:
%e A152525   {{1},{2},{3}}| {{1,2,3}}
%e A152525    {{1},{2,3}} |{{1,2},{3}}
%e A152525    {{1},{2,3}} |{{1,3},{2}}
%e A152525    {{1,2},{3}} |{{1,3},{2}}
%e A152525    {{1},{2,3}} | {{1,2,3}}
%e A152525    {{1,2},{3}} | {{1,2,3}}
%e A152525    {{1,3},{2}} | {{1,2,3}}
%e A152525 (End)
%p A152525 a:= n-> add(binomial(n,k)*binomial(combinat[bell](k),2)*
%p A152525         add(Stirling2(n-k,j)*(-1)^j, j=0..n-k), k=0..n):
%p A152525 seq(a(n), n=0..20);  # _Alois P. Heinz_, May 27 2018
%t A152525 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 *)
%o A152525 (PARI) a000110(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
%o A152525 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
%Y A152525 Cf. A000110, A000258, A001247, A008277, A048993, A059849, A060639, A181939, A193297, A318393, A322441, A322442, A320768.
%K A152525 nonn
%O A152525 0,4
%A A152525 _David Pasino_, Dec 06 2008, Dec 08 2008