# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a006472
Showing 1-1 of 1

%I A006472 M3052 #193 Apr 16 2024 01:40:42
%S A006472 1,1,3,18,180,2700,56700,1587600,57153600,2571912000,141455160000,
%T A006472 9336040560000,728211163680000,66267215894880000,6958057668962400000,
%U A006472 834966920275488000000,113555501157466368000000,17373991677092354304000000,2970952576782792585984000000
%N A006472 a(n) = n!*(n-1)!/2^(n-1).
%C A006472 Product of first (n-1) positive triangular numbers. - _Amarnath Murthy_, May 19 2002, corrected by _Alex Ratushnyak_, Dec 03 2013
%C A006472 Number of ways of transforming n distinguishable objects into n singletons via a sequence of n-1 refinements. Example: a(3)=3 because we have XYZ->X|YZ->X|Y|Z, XYZ->Y|XZ->X|Y|Z and XYZ->Z|XY->X|Y|Z. - _Emeric Deutsch_, Jan 23 2005
%C A006472 In other words, a(n) is the number of maximal chains in the lattice of set partitions of {1, ..., n} ordered by refinement. - _Gus Wiseman_, Jul 22 2018
%C A006472 From _David Callan_, Aug 27 2009: (Start)
%C A006472 With offset 0, a(n) = number of unordered increasing full binary trees of 2n edges with leaf set {n,n+1,...,2n}, where full binary means each nonleaf vertex has two children, increasing means the vertices are labeled 0,1,2,...,2n and each child is greater than its parent, unordered might as well mean ordered and each pair of sibling vertices is increasing left to right. For example, a(2)=3 counts the trees with edge lists {01,02,13,14}, {01,03,12,14}, {01,04,12,13}.
%C A006472 PROOF. Given such a tree of size n, to produce a tree of size n+1, two new leaves must be added to the leaf n. Choose any two of the leaf set {n+1,...,2n,2n+1,2n+2} for the new leaves and use the rest to replace the old leaves n+1,...,2n, maintaining relative order. Thus each tree of size n yields (n+2)-choose-2 trees of the next size up. Since the ratio a(n+1)/a(n)=(n+2)-choose-2, the result follows by induction.
%C A006472 Without the condition on the leaves, these trees are counted by the reduced tangent numbers A002105. (End)
%C A006472 a(n) = Sum(M(t)N(t)), where summation is over all rooted trees t with n vertices, M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494) and N(t) is  the number of ways to build up t from the one-vertex tree by adding successively edges to the existing vertices (the Connes-Moscovici weight; see A206496). See Remark on p. 3801 of the Hoffman reference. Example: a(3) = 3; indeed, there are two rooted trees with 3 vertices: t' = the path r-a-b and t" = V; we have M(t')=N(t')=1 and M(t") =1, N(t")=2, leading to M(t')N(t') + M(t")N(t")=3. - _Emeric Deutsch_, Jul 20 2012
%C A006472 Number of coalescence sequences or labeled histories for n lineages: the number of sequences by which n distinguishable leaves can coalesce to a single sequence. The coalescence process merges pairs of lineages into new lineages, labeling each newly formed lineage l by a subset of the n initial lineages corresponding to the union of all initial lineages that feed into lineage l. - _Noah A Rosenberg_, Jan 28 2019
%C A006472 Conjecture: For n>1, n divides 2*a(n-1)+4 if and only if n is prime. - _Werner Schulte_, Oct 04 2020
%D A006472 Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.
%D A006472 László Lovász, Combinatorial Problems and Exercises, North-Holland, 1979, p. 165.
%D A006472 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006472 Mike Steel, Phylogeny: Discrete and Random Processes in Evolution, SIAM, 2016, p. 47.
%H A006472 T. D. Noe, <a href="/A006472/b006472.txt">Table of n, a(n) for n = 1..50</a>
%H A006472 Karl Dienger, <a href="/A000217/a000217.pdf">Beiträge zur Lehre von den arithmetischen und geometrischen Reihen höherer Ordnung</a>, Jahres-Bericht Ludwig-Wilhelm-Gymnasium Rastatt, Rastatt, 1910. [Annotated scanned copy]
%H A006472 Daniel Dockery, <a href="https://web.archive.org/web/20140617132401/http://danieldockery.com/res/math/polygorials.pdf">Polygorials, Special "Factorials" of Polygonal Numbers</a>, preprint, 2003.
%H A006472 Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1112.1295">Some combinatorial problems on binary rooted trees occurring in population genetics</a>, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012.
%H A006472 P. Erdős, R. K. Guy and J. W. Moon, <a href="http://dx.doi.org/10.1112/jlms/s2-9.4.565">On refining partitions</a>, J. London Math. Soc., 9 (1975), 565-570.
%H A006472 L. Ferretti, F. Disanto and T. Wiehe, <a href="http://dx.doi.org/10.1371/journal.pone.0060123">The Effect of Single Recombination Events on Coalescent Tree Height and Shape</a>, PLoS ONE 8(4): e60123.
%H A006472 O. Frank and K. Svensson, <a href="http://dx.doi.org/10.1080/00949658108810439">On probability distributions of single-linkage dendrograms</a>, Journal of Statistical Computation and Simulation, 12 (1981), 121-131. (<a href="/A006472/a006472_1.pdf">Annotated scanned copy</a>)
%H A006472 Djamel Himane, <a href="https://arxiv.org/abs/2404.08646">A simple proof of Werner Schulte's conjecture</a>, arXiv:2404.08646 [math.GM], 2024.
%H A006472 M. E. Hoffman, <a href="http://dx.doi.org/10.1090/S0002-9947-03-03317-8 ">Combinatorics of rooted trees and Hopf algebras</a>, Trans. Amer. Math. Soc., 355, 2003, 3795-3811.
%H A006472 Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, <a href="https://arxiv.org/abs/1805.10998">On certain combinatorial expansions of the Legendre-Stirling numbers</a>, arXiv:1805.10998 [math.CO], 2018.
%H A006472 C. L. Mallows, <a href="/A006472/a006472.pdf">Note to N. J. A. Sloane circa 1979</a>.
%H A006472 F. Murtagh, <a href="http://dx.doi.org/10.1016/0166-218X(84)90066-0">Counting dendrograms: a survey</a>, Discrete Applied Mathematics, 7 (1984), 191-199.
%H A006472 N. A. Rosenberg, <a href="https://doi.org/10.1007/s00026-006-0278-6">The mean and variance of the numbers of r-pronged nodes and r-caterpillars in Yule-generated genealogical trees</a>, Annals of Combinatorics, 10 (2006), 129-146.
%H A006472 Thomas Wiehe, <a href="https://arxiv.org/abs/2010.06409">Counting, grafting and evolving binary trees</a>, arXiv:2010.06409 [q-bio.PE], 2020.
%H A006472 Johannes Wirtz, <a href="https://arxiv.org/abs/2211.03632">On the enumeration of leaf-labelled increasing trees with arbitrary node-degree</a>, arXiv:2211.03632 [q-bio.PE], 2022. See page 12.
%H A006472 <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>.
%F A006472 a(n) = a(n-1)*A000217(n-1).
%F A006472 a(n) = A010790(n-1)/2^(n-1).
%F A006472 a(n) = polygorial(n, 3) = (A000142(n)/A000079(n))*A000142(n+1) = (n!/2^n)*Product_{i=0..n-1} (i+2) = (n!/2^n)*Pochhammer(2, n) = (n!^2/2^n)*(n+1) = polygorial(n, 4)/2^n*(n+1). - Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
%F A006472 a(n-1) = (-1)^(n+1)/(n^2*det(M_n)) where M_n is the matrix M_(i, j) = abs(1/i - 1/j). - _Benoit Cloitre_, Aug 21 2003
%F A006472 From _Ilya Gutkovskiy_, Dec 15 2016: (Start)
%F A006472 a(n) ~ 4*Pi*n^(2*n)/(2^n*exp(2*n)).
%F A006472 Sum_{n>=1} 1/a(n) = BesselI(1,2*sqrt(2))/sqrt(2) = 2.3948330992734... (End)
%F A006472 D-finite with recurrence 2*a(n) -n*(n-1)*a(n-1)=0. - _R. J. Mathar_, May 02 2022
%F A006472 Sum_{n>=1} (-1)^(n+1)/a(n) = BesselJ(1,2*sqrt(2))/sqrt(2). - _Amiram Eldar_, Jun 25 2022
%e A006472 From _Gus Wiseman_, Jul 22 2018: (Start)
%e A006472 The (3) = 3 maximal chains in the lattice of set partitions of {1,2,3}:
%e A006472   {{1},{2},{3}} < {{1},{2,3}} < {{1,2,3}}
%e A006472   {{1},{2},{3}} < {{2},{1,3}} < {{1,2,3}}
%e A006472   {{1},{2},{3}} < {{3},{1,2}} < {{1,2,3}}
%e A006472 (End)
%p A006472 A006472 := n -> n!*(n-1)!/2^(n-1):
%t A006472 FoldList[Times,1,Accumulate[Range[20]]] (* _Harvey P. Dale_, Jan 10 2013 *)
%o A006472 (PARI) a(n) = n*(n-1)!^2/2^(n-1) \\ _Charles R Greathouse IV_, May 18 2015
%o A006472 (Magma) [Factorial(n)*Factorial(n-1)/2^(n-1): n in [1..20]]; // _Vincenzo Librandi_, Aug 23 2018
%o A006472 (Python)
%o A006472 from math import factorial
%o A006472 def A006472(n): return n*factorial(n-1)**2 >> n-1 # _Chai Wah Wu_, Jun 22 2022
%Y A006472 Cf. A000110, A000258, A002846, A005121, A213427, A317145.
%Y A006472 Cf. A084939, A084940, A084941, A084942, A084943, A084944.
%Y A006472 For the type B and D analogs, see A001044 and A123385.
%K A006472 nonn,easy,nice
%O A006472 1,3
%A A006472 _N. J. A. Sloane_

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE