login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005121 Number of ultradissimilarity relations on an n-set.
(Formerly M3649)
17
1, 1, 4, 32, 436, 9012, 262760, 10270696, 518277560, 32795928016, 2542945605432, 237106822506952, 26173354092593696, 3375693096567983232, 502995942483693043200, 85750135569136650473360, 16583651916595710735271248, 3611157196483089769387182064, 879518067472225603327860638128 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

First column in A154960. - Mats Granvik, Jan 18 2009

Number of chains from minimum to maximum in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018

REFERENCES

L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 316-321.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..100

L. Babai and T. Lengyel, A convergence criterion for recurrent sequences with application to the partition lattice, Analysis 12 (1992), 109-119.

D. Barsky, J.-P. Bézivin, p-adic Properties of Lengyel's Numbers, Journal of Integer Sequences, 17 (2014), #14.7.3.

P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 170 - N. J. A. Sloane, Apr 18 2014

Steven R. Finch, Lengyel's Constant [Broken link]

Steven R. Finch, Lengyel's Constant [From the Wayback machine]

T. Lengyel, On a recurrence involving Stirling numbers, Europ. J. Combin., 5 (1984), 313-321.

T. Lengyel, On some 2-adic properties of a recurrence involving Stirling numbers, p-Adic Numbers Ultrametric Anal. Appl. 4, No. 3, 179-186 (2012).

F. Murtagh, Counting dendrograms: a survey, Discrete Appl. Math., 7 (1984), 191-199.

T. Prellberg, On the asymptotic analysis of a class of linear recurrences (slides).

M. Schader, Hierarchical analysis: classification with ordinal object dissimilarities, Metrika, 27 (1980), 127-132.

M. Schader, Hierarchical analysis: classification with ordinal object dissimilarities, Metrika, 27 (1980), 127-132. [Annotated scanned copy]

M. Schader, Letter to N. J. A. Sloane, Aug 25 1981.

Eric Weisstein's World of Mathematics, Lengyel's Constant

FORMULA

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.

a(n) = Sum_{k=1..n-1} Stirling2(n, k)*a(k) [Lengyel]. - Vladeta Jovovic, Apr 16 2003

E.g.f. satisfies Z(z) = 1/2 * (Z(exp(z)-1) - z). [Lengyel]

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

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

EXAMPLE

From Gus Wiseman, Jul 22 2018: (Start)

The (3) = 4 chains from minimum to maximum in the lattice of set partitions of {1,2,3}:

  {{1},{2},{3}} < {{1,2,3}}

  {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}

  {{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}

  {{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}

(End)

MATHEMATICA

a[1] = 1; a[n_] := a[n] = Sum[StirlingS2[n, k]*a[k], {k, 1, n-1}]; Array[a, 19]

(* Jean-François Alcover, Jun 24 2011, after Vladeta Jovovic *)

PROG

(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 */

CROSSREFS

Row sums of A008826.

Cf. A000110, A000258, A002846, A006541, A006472, A213427, A265947, A317145.

Sequence in context: A140178 A088991 A009668 * A214379 A192500 A192486

Adjacent sequences:  A005118 A005119 A005120 * A005122 A005123 A005124

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Apr 16 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 19 22:14 EDT 2019. Contains 325168 sequences. (Running on oeis4.)