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

1, 1, 2, 8, 56, 552, 7202, 118456, 2369922, 56230544, 1552048082, 49080888144, 1756527398738, 70427165428648, 3136819046716266, 154090456510590632, 8296738497931578818, 487014208107376581984, 31018372994440588508642, 2134584265273475942046304

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..325

E. R. Canfield, Meet and join in the partition lattice, Electronic Journal of Combinatorics, 8 (2001) R15.

B. Pittel, Where the typical set partitions meet and join, Electronic Journal of Combinatorics, 7 (2000) R5.

Frank Simon, Algebraic Methods for Computing the Reliability of Networks, 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

Formula

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}}.

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}}.

Example

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

Maple

with(combinat):
m:= proc(n) option remember; add(stirling1(n, k)*bell(k)^2, k=0..n) end:
a:= proc(n) option remember;
      m(n) -add(binomial(n-1, k)*m(k)*a(n-k), k=1..n-1)
    end:
seq(a(n), n=0..20); # Alois P. Heinz, Apr 20 2012

Mathematica

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 *)

Crossrefs

Cf. A059849, A060639.

Sequence in context: A201128 A277498 A097691 * A124212 A326009 A349562

Adjacent sequences: A181936 A181937 A181938 * A181940 A181941 A181942

Keyword

nonn,easy

Author

Alexander Steinhardt (asteinh1(AT)hs-mittweida.de), Jens Schreiter (jschrei1(AT)hs-mittweida.de), Frank Simon, Apr 03 2012

Extensions

Terms corrected and more terms added, Alois P. Heinz, Apr 20 2012

Status

approved