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

%I #41 Aug 29 2020 07:15:24

%S 1,1,3,15,119,1343,19905,369113,8285261,219627683,6746244739,

%T 236561380795,9356173080985,413251604702069,20215438754502217,

%U 1087524296159855603,63950948621703499839,4089003767746536828183,282970817307108139386841,21107742616278461624923449,1690957890908364634072451893

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

%C 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

%H Vincenzo Librandi, <a href="/A060639/b060639.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 I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, et al., <a href="http://arxiv.org/abs/1408.2021">Enumeration of idempotents in diagram semigroups and algebras</a>, arXiv preprint arXiv:1408.2021 [math.GR], 2014; Table 3.

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

%F 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.

%F 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

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

%t 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]];

%t list[17] Range[0, 17]! (* _Jean-François Alcover_, Nov 03 2018, from PARI *)

%o (PARI) Bell(n)=round(suminf(k=0,k^n/k!)/exp(1))

%o 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

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

%Y Cf. A001188, A318815.

%K nonn

%O 0,3

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

%E More terms from _Vladeta Jovovic_, Apr 18 2001