A123385 -id:A123385 - cp's OEIS frontend

A006472 a(n) = n!*(n-1)!/2^(n-1).

1, 1, 3, 18, 180, 2700, 56700, 1587600, 57153600, 2571912000, 141455160000, 9336040560000, 728211163680000, 66267215894880000, 6958057668962400000, 834966920275488000000, 113555501157466368000000, 17373991677092354304000000, 2970952576782792585984000000

Offset: 1

N. J. A. Sloane

Product of first (n-1) positive triangular numbers. - Amarnath Murthy, May 19 2002, corrected by Alex Ratushnyak, Dec 03 2013
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
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
From David Callan, Aug 27 2009: (Start)
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)-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.
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 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
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(n-1) + 4 if and only if n is prime. - Werner Schulte, Oct 04 2020
For a proof of the above conjecture see Himane. The list of primes p such that p^2 divides (2*a(p-1) + 4) (analog of A007540 - Wilson primes) begins [239, 24049, ...]. - Peter Bala, Nov 06 2024

			From _Gus Wiseman_, Jul 22 2018: (Start)
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)

Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.
László Lovász, Combinatorial Problems and Exercises, North-Holland, 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.

T. D. Noe, Table of n, a(n) for n = 1..50
E. H. Dickey, N. A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Karl Dienger, Beiträge zur Lehre von den arithmetischen und geometrischen Reihen höherer Ordnung, Jahres-Bericht Ludwig-Wilhelm-Gymnasium Rastatt, Rastatt, 1910. [Annotated scanned copy]
Daniel Dockery, Polygorials, Special "Factorials" of Polygonal Numbers, preprint, 2003.
Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, arXiv preprint arXiv:1112.1295 [math.CO], 2011-2012.
A. W. F. Edwards, Estimation of the branch points of a branching diffusion Process, J. Royal Stat. Soc. Ser. B 32 (1970), 155-164.
P. Erdős, R. K. Guy and J. W. Moon, On refining partitions, J. London Math. Soc., 9 (1975), 565-570.
L. Ferretti, F. Disanto and T. Wiehe, The Effect of Single Recombination Events on Coalescent Tree Height and Shape, PLoS ONE 8(4): e60123.
O. Frank and K. Svensson, On probability distributions of single-linkage dendrograms, Journal of Statistical Computation and Simulation, 12 (1981), 121-131. (Annotated scanned copy)
Djamel Himane, A simple proof of Werner Schulte's conjecture, arXiv:2404.08646 [math.GM], 2024. See also Notes Num. Theor. Disc. Math., (2025) Vol. 31, No. 2, 251-225.
M. E. Hoffman, Combinatorics of rooted trees and Hopf algebras, Trans. Amer. Math. Soc., 355, 2003, 3795-3811.
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of the Legendre-Stirling numbers, arXiv:1805.10998 [math.CO], 2018.
C. L. Mallows, Note to N. J. A. Sloane circa 1979.
F. Murtagh, Counting dendrograms: a survey, Discrete Applied Mathematics, 7 (1984), 191-199.
N. A. Rosenberg, The mean and variance of the numbers of r-pronged nodes and r-caterpillars in Yule-generated genealogical trees, Annals of Combinatorics, 10 (2006), 129-146.
Thomas Wiehe, Counting, grafting and evolving binary trees, arXiv:2010.06409 [q-bio.PE], 2020.
Johannes Wirtz, On the enumeration of leaf-labelled increasing trees with arbitrary node-degree, arXiv:2211.03632 [q-bio.PE], 2022. See page 12.
Index entries for sequences related to factorial numbers.

Cf. A000110, A000258, A002846, A005121, A213427, A317145, A363679 (sum of reciprocals).
Cf. A084939, A084940, A084941, A084942, A084943, A084944.
For the type B and D analogs, see A001044 and A123385.

[Factorial(n)*Factorial(n-1)/2^(n-1): n in [1..20]]; // Vincenzo Librandi, Aug 23 2018

Maple
```
A006472 := n -> n!*(n-1)!/2^(n-1):
```

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

a(n) = n*(n-1)!^2/2^(n-1) \\ Charles R Greathouse IV, May 18 2015

from math import factorial
def A006472(n): return n*factorial(n-1)**2 >> n-1 # Chai Wah Wu, Jun 22 2022

a(n) = a(n-1)*A000217(n-1).
a(n) = A010790(n-1)/2^(n-1).
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
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
From Ilya Gutkovskiy, Dec 15 2016: (Start)
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)
D-finite with recurrence 2*a(n) -n*(n-1)*a(n-1)=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

A078601 Number of ways to lace a shoe that has n pairs of eyelets, assuming the lacing satisfies certain conditions.

Original entry on oeis.org

1, 3, 42, 1080, 51840, 3758400, 382838400, 52733721600, 9400624128000, 2105593491456000, 579255485276160000, 191957359005941760000, 75420399121328701440000, 34668462695110852608000000, 18432051070888873171353600000, 11223248177765618214764544000000, 7759395812038133743242706944000000

Offset: 1

N. J. A. Sloane, Dec 11 2002

nonn

The lace must follow a Hamiltonian path through the 2n eyelets. At least one of the neighbors of every eyelet must be on the other side of the shoe.

The lace is "undirected": reversing the order of eyelets along the path does not count as a different solution.

			Label the eyelets 1, ..., n from front to back on the left and from n+1, ..., 2n from back to front on the right. For n=2 the three solutions are 1 2 3 4, 3 1 2 4, 1 3 2 4.
For n=3 the first few solutions are 2 4 1 3 5 6, 1 4 2 3 5 6, 2 1 4 3 5 6, 1 2 4 3 5 6, 1 3 4 2 5 6, 3 1 4 2 5 6, 1 4 3 2 5 6, 3 4 1 2 5 6, 3 4 2 1 5 6, 2 4 3 1 5 6, 3 2 4 1 5 6, 2 3 4 1 5 6, 2 3 5 1 4 6, 3 2 5 1 4 6, 2 5 3 1 4 6, 3 5 2 1 4 6, ...

B. Polster, What is the best way to lace your shoes?, Nature, 420 (Dec 05 2002), 476.
Index entries for sequences related to shoe lacings

See A078602 and A078629 for other ways of counting lacings.

Cf. A123385.

A078601 := n->((n!)^2/2)*add(binomial(n-k,k)^2/(n-k),k=0..floor(n/2));

a[n_] := If[n == 1, 1, n!^2/2 Sum[Binomial[n-k, k]^2/(n-k), {k, 0, n/2}]];
a /@ Range[1, 17] (* Jean-François Alcover, Oct 01 2019 *)

a(n)=if(n>1,n!^2*sum(k=0,n\2,binomial(n-k, k)^2/(n-k))/2,1) \\ Charles R Greathouse IV, Sep 10 2015

from sympy import factorial, binomial
a = lambda n:((factorial(n)**2)>>1) * sum((binomial(n-k,k)**2)/(n-k) for k in range(0,(n>>1)+1)) if n > 1 else 1
print([a(n) for n in range(1, 18)]) # Darío Clavijo, Mar 06 2024

a(1)=1; for n > 1, a(n) = ((n!)^2/2)*Sum_{k=0..floor(n/2)} binomial(n-k, k)^2/(n-k).

cp's OEIS Frontend

A006472 a(n) = n!*(n-1)!/2^(n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula