

A006472


a(n) = n!*(n1)!/2^(n1).
(Formerly M3052)


49



1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, 2571912000, 141455160000, 9336040560000, 728211163680000, 66267215894880000, 6958057668962400000, 834966920275488000000, 113555501157466368000000, 17373991677092354304000000, 2970952576782792585984000000
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Number of ways of transforming n distinguishable objects into n singletons via a sequence of n1 refinements. Example: a(3)=3 because we have XYZ>XYZ>XYZ, XYZ>YXZ>XYZ and XYZ>ZXY>XYZ.  Emeric Deutsch, Jan 23 2005
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
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}.
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)choose2 trees of the next size up. Since the ratio a(n+1)/a(n)=(n+2)choose2, the result follows by induction.
Without the condition on the leaves, these trees are counted by the reduced tangent numbers A002105. (End)
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 onevertex tree by adding successively edges to the existing vertices (the ConnesMoscovici 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 rab 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
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
Conjecture: For n>1, n divides 2*a(n1)+4 if and only if n is prime.  Werner Schulte, Oct 04 2020


REFERENCES

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.
László Lovász, Combinatorial Problems and Exercises, NorthHolland, 1979, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Mike Steel, Phylogeny: Discrete and Random Processes in Evolution, SIAM, 2016, p. 47.


LINKS



FORMULA

a(n) = polygorial(n, 3) = (A000142(n)/A000079(n))*A000142(n+1) = (n!/2^n)*Product_{i=0..n1} (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
a(n1) = (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
a(n) ~ 4*Pi*n^(2*n)/(2^n*exp(2*n)).
Sum_{n>=1} 1/a(n) = BesselI(1,2*sqrt(2))/sqrt(2) = 2.3948330992734... (End)
Dfinite with recurrence 2*a(n) n*(n1)*a(n1)=0.  R. J. Mathar, May 02 2022
Sum_{n>=1} (1)^(n+1)/a(n) = BesselJ(1,2*sqrt(2))/sqrt(2).  Amiram Eldar, Jun 25 2022


EXAMPLE

The (3) = 3 maximal chains in the lattice of set partitions of {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)


MAPLE



MATHEMATICA

FoldList[Times, 1, Accumulate[Range[20]]] (* Harvey P. Dale, Jan 10 2013 *)


PROG

(Magma) [Factorial(n)*Factorial(n1)/2^(n1): n in [1..20]]; // Vincenzo Librandi, Aug 23 2018
(Python)
from math import factorial


CROSSREFS



KEYWORD

nonn,easy,nice


AUTHOR



STATUS

approved



