A060639 Number of pairs of partitions of [n] whose join is the partition {{1,2,...,n}}.

1, 1, 3, 15, 119, 1343, 19905, 369113, 8285261, 219627683, 6746244739, 236561380795, 9356173080985, 413251604702069, 20215438754502217, 1087524296159855603, 63950948621703499839, 4089003767746536828183, 282970817307108139386841, 21107742616278461624923449, 1690957890908364634072451893

Offset: 0

Author

E. R. Canfield (erc(AT)cs.uga.edu), Apr 16 2001

Keywords

• nonn

Comments

It appears that a(n) = 2*A001188(n) - 1 for n > 0. This holds for the first 50 terms. - Charles R Greathouse IV, Mar 21 2012

Examples

			J(2) = 3 because there are two partitions of {1,2} and of the four pairs of partitions, only the pair ( {{1},{2}}, {{1},{2}} ) fails to have join {{1,2}}.
		

Links

• Vincenzo Librandi, 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.
• I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., Enumeration of idempotents in diagram semigroups and algebras, arXiv preprint arXiv:1408.2021 [math.GR], 2014; Table 3.
• 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.

Crossrefs

Bell numbers: A000110, Stirling numbers of the second kind: A000225, number of pairs whose meet equals {{1}, {2}, ..., {n}}: A059849.

Cf. A001188, A318815.

Programs

Mathematica

list[n_] := Module[{t}, t = Table[BellB[k-1]^2/(k-1)!, {k, 1, n+1}]; CoefficientList[1+Log[O[x]^(n+1)+Sum[t[[i]] x^(i-1), {i, 1, Length[t]}]], x]];
list[17] Range[0, 17]! (* Jean-François Alcover, Nov 03 2018, from PARI *)

PARI

Bell(n)=round(suminf(k=0,k^n/k!)/exp(1))
list(n)=my(v=Vec(log(O(x^(n+1))+Polrev(vector(n+1,k,Bell(k-1)^2/(k-1)!)))));concat(1,vector(n,i,v[i]*i!)) \\ Charles R Greathouse IV, Mar 21 2012

Formula

The e.g.f. J(x) satisfies the equation Sum_{n>=0} (B_n)^2 x^n/n! = exp(J(x)-1), where B_n is the n-th Bell number.

a(0) = 1; a(n) = Bell(n)^2 - (1/n) * Sum_{k=1..n-1} binomial(n,k) * Bell(n-k)^2 * k * a(k). - Ilya Gutkovskiy, Jan 17 2020

Extensions

More terms from Vladeta Jovovic, Apr 18 2001