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,3

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

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.

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

Example

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

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

Prog

(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

Crossrefs

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

Cf. A001188, A318815.

Sequence in context: A364621 A145161 A121422 * A068052 A068859 A006454

Adjacent sequences: A060636 A060637 A060638 * A060640 A060641 A060642

Keyword

nonn

Author

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

Extensions

More terms from Vladeta Jovovic, Apr 18 2001

Status

approved