login
Number of pairs of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}} and join is {{1,2,...,n}}.
19

%I #57 Oct 15 2024 20:27:23

%S 1,1,2,8,56,552,7202,118456,2369922,56230544,1552048082,49080888144,

%T 1756527398738,70427165428648,3136819046716266,154090456510590632,

%U 8296738497931578818,487014208107376581984,31018372994440588508642,2134584265273475942046304

%N Number of pairs of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}} and join is {{1,2,...,n}}.

%H Alois P. Heinz, <a href="/A181939/b181939.txt">Table of n, a(n) for n = 0..325</a>

%H E. R. Canfield, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r15">Meet and join in the partition lattice</a>, Electronic Journal of Combinatorics, 8 (2001) R15.

%H B. Pittel, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r5">Where the typical set partitions meet and join</a>, Electronic Journal of Combinatorics, 7 (2000) R5.

%H Frank Simon, <a href="https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-101154">Algebraic Methods for Computing the Reliability of Networks</a>, Dissertation, Doctor Rerum Naturalium (Dr. rer. nat.), Fakultät Mathematik und Naturwissenschaften der Technischen Universität Dresden, 2012. See Table 3.3. - _N. J. A. Sloane_, Jan 04 2013

%F E.g.f.: 1+log(M(x)), where M(x) is the e.g.f. of A059849 of all pairs of set partitions of {1,2,...,n} whose meet is {{1},{2},...,{n}}.

%F a(n) = m(n) - Sum_{k=1..n-1} C(n-1,k)*m(k)*a(n-k), where m(n) = A059849(n) of all pairs of set partitions of an n-element set having meet {{1},{2},...,{n}}.

%e For n = 2 there are exactly the following two pairs ({{1,2}},{{1},{2}}), ({{1},{2}},{{1,2}}) satisfying the imposed conditions.

%p with(combinat):

%p m:= proc(n) option remember; add(stirling1(n, k)*bell(k)^2, k=0..n) end:

%p a:= proc(n) option remember;

%p m(n) -add(binomial(n-1,k)*m(k)*a(n-k), k=1..n-1)

%p end:

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Apr 20 2012

%t m[n_] := m[n] = Sum[StirlingS1[n, k]*BellB[k]^2, {k, 0, n}]; a[n_] := a[n] = m[n] - Sum[ Binomial[n-1, k]*m[k]*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jul 15 2015, after _Alois P. Heinz_ *)

%Y Cf. A059849, A060639.

%K nonn,easy

%O 0,3

%A Alexander Steinhardt (asteinh1(AT)hs-mittweida.de), Jens Schreiter (jschrei1(AT)hs-mittweida.de), _Frank Simon_, Apr 03 2012

%E Terms corrected and more terms added, _Alois P. Heinz_, Apr 20 2012