cp's OEIS Frontend

A005121 Number of ultradissimilarity relations on an n-set.

%I A005121 M3649 #67 Feb 16 2025 08:32:28
%S A005121 1,1,4,32,436,9012,262760,10270696,518277560,32795928016,
%T A005121 2542945605432,237106822506952,26173354092593696,3375693096567983232,
%U A005121 502995942483693043200,85750135569136650473360,16583651916595710735271248,3611157196483089769387182064,879518067472225603327860638128
%N A005121 Number of ultradissimilarity relations on an n-set.
%C A005121 First column in A154960. - _Mats Granvik_, Jan 18 2009
%C A005121 Number of chains from minimum to maximum in the lattice of set partitions of {1, ..., n} ordered by refinement. - _Gus Wiseman_, Jul 22 2018
%D A005121 L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.
%D A005121 Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 316-321.
%D A005121 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005121 Vincenzo Librandi, <a href="/A005121/b005121.txt">Table of n, a(n) for n = 1..100</a>
%H A005121 L. Babai and T. Lengyel, <a href="https://citeseerx.ist.psu.edu/pdf/baf7252d4e82948610a04cb027a7c4b75ef54a1a">A convergence criterion for recurrent sequences with application to the partition lattice</a>, Analysis 12 (1992), 109-119.
%H A005121 D. Barsky, J.-P. Bézivin, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barsky/barsky5.html">p-adic Properties of Lengyel's Numbers</a>, Journal of Integer Sequences, 17 (2014), #14.7.3.
%H A005121 P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 170 - _N. J. A. Sloane_, Apr 18 2014
%H A005121 Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/lngy/lngy.html">Lengyel's Constant</a> [Broken link]
%H A005121 Steven R. Finch, <a href="http://web.archive.org/web/20010603070928/http://www.mathsoft.com/asolve/constant/lngy/lngy.html">Lengyel's Constant</a> [From the Wayback machine]
%H A005121 T. Lengyel, <a href="http://dx.doi.org/10.1016/S0195-6698(84)80035-9">On a recurrence involving Stirling numbers</a>, Europ. J. Combin., 5 (1984), 313-321.
%H A005121 T. Lengyel, <a href="https://doi.org/10.1134/s2070046612030028"> On some 2-adic properties of a recurrence involving Stirling numbers</a>, p-Adic Numbers Ultrametric Anal. Appl. 4, No. 3, 179-186 (2012).
%H A005121 F. Murtagh, <a href="http://dx.doi.org/10.1016/0166-218X(84)90066-0">Counting dendrograms: a survey</a>, Discrete Appl. Math., 7 (1984), 191-199.
%H A005121 T. Prellberg, <a href="http://algo.inria.fr/seminars/sem02-03/prellberg1-slides.ps">On the asymptotic analysis of a class of linear recurrences</a> (slides).
%H A005121 M. Schader, <a href="http://dx.doi.org/10.1007/BF01893584">Hierarchical analysis: classification with ordinal object dissimilarities</a>, Metrika, 27 (1980), 127-132.
%H A005121 M. Schader, <a href="/A005121/a005121_1.pdf">Hierarchical analysis: classification with ordinal object dissimilarities</a>, Metrika, 27 (1980), 127-132. [Annotated scanned copy]
%H A005121 M. Schader, <a href="/A005121/a005121.pdf">Letter to N. J. A. Sloane</a>, Aug 25 1981.
%H A005121 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LengyelsConstant.html">Lengyel's Constant</a>
%F A005121 a(n) = Sum_{i=1..n-1} N_i(n), where N_k(m) = Sum_{j=k..m-1} Stirling2(m, j)*N_{k-1}(j), m=3..n, k=2..m-1; N_1(2)=N_1(3)=...=N_1(n)=1.
%F A005121 a(n) = Sum_{k=1..n-1} Stirling2(n, k)*a(k) [Lengyel]. - _Vladeta Jovovic_, Apr 16 2003
%F A005121 E.g.f. satisfies Z(z) = 1/2 * (Z(exp(z)-1) - z). [Lengyel]
%F A005121 Asymptotic growth: a(n) ~ C_L*(n!)^2*(2log(2))^(-n)*n^(-1-1/3*log(2)) (Babai and Lengyel), with C_L = 1.0986858055... = A086053 [Flajolet and Salvy].
%F A005121 Sum_{k>=1} a(k-1)/fallfac(n,k) = -1/n^2 + 2*Sum_{k>=1} a(k-1)/n^k, with the falling factorials fallfac(n,k) = Product_{j=0..k-1}(n-j). - _Vaclav Kotesovec_, Aug 04 2015
%e A005121 From _Gus Wiseman_, Jul 22 2018: (Start)
%e A005121 The (3) = 4 chains from minimum to maximum in the lattice of set partitions of {1,2,3}:
%e A005121   {{1},{2},{3}} < {{1,2,3}}
%e A005121   {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
%e A005121   {{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
%e A005121   {{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
%e A005121 (End)
%t A005121 a[1] = 1; a[n_] := a[n] = Sum[StirlingS2[n, k]*a[k], {k, 1, n-1}]; Array[a, 19]
%t A005121 (* _Jean-François Alcover_, Jun 24 2011, after _Vladeta Jovovic_ *)
%o A005121 (PARI) {a(n) = local(A); if( n<1, 0, for(k=1, n, A = truncate(A) + x*O(x^k); A = x - A + subst(A, x, exp(x + x*O(x^k)) - 1)); n! * polcoeff(A, n))} /* _Michael Somos_, Sep 22 2007 */
%Y A005121 Row sums of A008826.
%Y A005121 Cf. A000110, A000258, A002846, A006541, A006472, A213427, A265947, A317145.
%K A005121 nonn,nice,easy
%O A005121 1,3
%A A005121 _N. J. A. Sloane_
%E A005121 More terms from _Vladeta Jovovic_, Apr 16 2003