A000698 -id:A000698 - cp's OEIS frontend

A001147 Double factorial of odd numbers: a(n) = (2n-1)!! = 135...(2n-1).

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, 13749310575, 316234143225, 7905853580625, 213458046676875, 6190283353629375, 191898783962510625, 6332659870762850625, 221643095476699771875, 8200794532637891559375, 319830986772877770815625

Offset: 0

N. J. A. Sloane

The solution to Schröder's third problem.
Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).
a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022]
a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012
For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001
a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).
a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004
Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number (A008517). - Ross La Haye, Feb 13 2005
Integral representation as n-th moment of a positive function on the positive axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/2)/sqrt(2*Pi*x) dx, n >= 0. - Karol A. Penson, Oct 10 2005
a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006
a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for iDavid Callan, Sep 25 2006
a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006
Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006
a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006
a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan, Mar 30 2007
From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start)
a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations.
This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)
From Ross Drewe, Mar 16 2008: (Start)
This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.
If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.
For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.
By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}
Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)
A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller, Apr 25 2008
a(n+1) = Sum_{j=0..n} A074060(n,j) * 2^j. - Tom Copeland, Sep 01 2008
From Emeric Deutsch, Jun 05 2009: (Start)
a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.
a(n) = Sum_{k>=0} k*A079267(n,k).
(End)
Hankel transform is A137592. - Paul Barry, Sep 18 2009
(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009
a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009
The Hankel transform of a(n+1) is A168467. - Paul Barry, Dec 04 2009
Partial products of odd numbers. - Juri-Stepan Gerasimov, Oct 17 2010
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011
a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). - Leonid Bedratyuk, Jun 01 2012
For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013
a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013
a(n) is the size of the Brauer monoid on 2n points (see A227545). - James Mitchell, Jul 28 2013
For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014
a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014
For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014
Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014
a(n) = the number of relaxed compacted binary trees of right height at most one of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017
Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017
From Christopher J. Smyth, Jan 26 2018: (Start)
a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)
Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.
(End)
a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021
Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021
From Tom Copeland, Jun 14 2021: (Start)
Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).
Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial.
These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991.
a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End)
Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021
b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022

			a(3) = 1*3*5 = 15.
From _Joerg Arndt_, Sep 10 2013: (Start)
There are a(3)=15 involutions of 6 elements without fixed points:
  #:    permutation           transpositions
  01:  [ 1 0 3 2 5 4 ]      (0, 1) (2, 3) (4, 5)
  02:  [ 1 0 4 5 2 3 ]      (0, 1) (2, 4) (3, 5)
  03:  [ 1 0 5 4 3 2 ]      (0, 1) (2, 5) (3, 4)
  04:  [ 2 3 0 1 5 4 ]      (0, 2) (1, 3) (4, 5)
  05:  [ 2 4 0 5 1 3 ]      (0, 2) (1, 4) (3, 5)
  06:  [ 2 5 0 4 3 1 ]      (0, 2) (1, 5) (3, 4)
  07:  [ 3 2 1 0 5 4 ]      (0, 3) (1, 2) (4, 5)
  08:  [ 3 4 5 0 1 2 ]      (0, 3) (1, 4) (2, 5)
  09:  [ 3 5 4 0 2 1 ]      (0, 3) (1, 5) (2, 4)
  10:  [ 4 2 1 5 0 3 ]      (0, 4) (1, 2) (3, 5)
  11:  [ 4 3 5 1 0 2 ]      (0, 4) (1, 3) (2, 5)
  12:  [ 4 5 3 2 0 1 ]      (0, 4) (1, 5) (2, 3)
  13:  [ 5 2 1 4 3 0 ]      (0, 5) (1, 2) (3, 4)
  14:  [ 5 3 4 1 2 0 ]      (0, 5) (1, 3) (2, 4)
  15:  [ 5 4 3 2 1 0 ]      (0, 5) (1, 4) (2, 3)
(End)
G.f. = 1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + 135135*x^7 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, (26.2.28).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 317.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.
Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.
F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.
C. Itzykson and J.-B. Zuber, Quantum Field Theory, McGraw-Hill, 1980, pages 466-467.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.6 and also p. 178.
R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999, p. 73.
G. Watson, The Theory of Bessel Functions, Cambridge Univ. Press, 1922.

Stefano Spezia, Table of n, a(n) for n = 0..400 (first 102 terms from T. D. Noe)
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
José A. Adell and Beáta Bényi, Probabilistic Stirling numbers and applications, Aequat. Math. (2024). See p. 18.
Rudolf Berghammer, Jules Desharnais, and Michael Winter, Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points, arXiv:2505.00140 [cs.DM], 2025. See p. 16.
Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts).
Christian Aebi and Grant Cairns, Generalizations of Wilson's Theorem for Double-, Hyper-, Sub-and Superfactorials, The American Mathematical Monthly 122.5 (2015): 433-443.
D. Arques and J.-F. Beraud, Rooted maps on orientable surfaces, Riccati's equation and continued fractions, Discrete Math., 215 (2000), 1-12.
Fatemeh Bagherzadeh, M. Bremner, and S. Madariaga, Jordan Trialgebras and Post-Jordan Algebras, arXiv preprint arXiv:1611.01214 [math.RA], 2016.
Cyril Banderier, Philippe Marchal, and Michael Wallner, Rectangular Young tableaux with local decreases and the density method for uniform random generation (short version), arXiv:1805.09017 [cs.DM], 2018.
Paul Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011) # 11.4.5.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Paul Barry and A. Hennessy, The Euler-Seidel Matrix, Hankel Matrices and Moment Sequences, J. Int. Seq. 13 (2010) # 10.8.2.
Natasha Blitvić and Einar Steingrímsson, Permutations, moments, measures, arXiv:2001.00280 [math.CO], 2020.
O. Bodini, M. Dien, X. Fontaine, A. Genitrini, and H. K. Hwang, Increasing Diamonds, in LATIN 2016: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings Pages pp. 207-219 2016 DOI 10.1007/978-3-662-49529-2_16; Lecture Notes in Computer Science Series Volume 9644.
H. Bottomley, Illustration for A000108, A001147, A002694, A067310 and A067311
Jonathan Burns, Egor Dolzhenko, Nataša Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, Discrete Applied Mathematics, 161 (2013), 1378-1394.
David Callan, A combinatorial survey of identities for the double factorial, arXiv:0906.1317 [math.CO], 2009.
Peter J. Cameron, Some treelike objects Quart. J. Math. Oxford Ser. 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Carsten Schneider, The Absent-Minded Passengers Problem: A Motivating Challenge Solved by Computer Algebra, arXiv:2003.01921 [math.CO], 2020.
P. Codara, O. M. D'Antona, P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers, arXiv preprint arXiv:1308.1700 [cs.DM], 2013.
Thierry Dana-Picard, Sequences of Definite Integrals, Factorials and Double Factorials, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.6.
Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, arXiv preprint arXiv:1112.1295 [math.CO], 2011.
John Engbers, David Galvin, and Clifford Smyth, Restricted Stirling and Lah numbers and their inverses, arXiv:1610.05803 [math.CO], 2016. See p. 5.
J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)
FindStat - Combinatorial Statistic Finder, Perfect matchings
A. Genitrini, B. Gittenberger, M. Kauers and M. Wallner, Asymptotic Enumeration of Compacted Binary Trees, arXiv:1703.10031 [math.CO], 2017.
Ghislain R. Franssens, On a Number Pyramid Related to the Binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
S. Goodenough and C. Lavault, On subsets of Riordan subgroups and Heisenberg--Weyl algebra, arXiv:1404.1894 [cs.DM], 2014.
S. Goodenough and C. Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16.
W. S. Gray and M. Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 Mar 2013.
Shyam Sunder Gupta, Fascinating Factorials, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 16, 411-442.
Paul W. Haggard, On Legendre numbers, International Journal of Mathematics and Mathematical Sciences, vol. 8, Article ID 787189, 5 pages, 1985. See Table 1 p. 408.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 23.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 106.
J. Jakes-Schauer, D. Anekstein, and P. Wocjan, Carving-width and contraction trees for tensor networks, arXiv:1908.11034 [cs.DM], 2019.
L. B. W. Jolley, Summation of Series, Dover, 1961 p. 48.
M. Kauers and S.-L. Ko, Problem 11545, Amer. Math. Monthly, 118 (2011), p. 84.
A. Khruzin, Enumeration of chord diagrams, arXiv:math/0008209 [math.CO], 2000.
M. Klazar, Twelve countings with rooted plane trees, European Journal of Combinatorics 18 (1997), 195-210; Addendum, 18 (1997), 739-740.
S. Lando and A. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, 141, Springer, 2004.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
F. Larrion, M. A. Pizana, and R. Villarroel-Flores, The clique operator on matching and chessboard graphs Discrete Math. 309 (2009), no. 1, 85-93.
Peter D. Loly and Ian D. Cameron, Frierson's 1907 Parameterization of Compound Magic Squares Extended to Orders 3^L, L = 1, 2, 3, ..., with Information Entropy, arXiv:2008.11020 [math.HO], 2020.
E. Lucas, Theorie des nombres (annotated scans of a few selected pages).
Robert J. Marsh and Paul Martin, Tiling bijections between paths and Brauer diagrams, Journal of Algebraic Combinatorics, Vol 33, No 3 (2011), pp. 427-453.
MathOverflow, Geometric / physical / probabilistic interpretations of Riemann zeta(n>1)?, answer by Tom Copeland posted in Aug 2021.
B. E. Meserve, Double Factorials, American Mathematical Monthly, 55 (1948), 425-426.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
F. Murtagh, Counting dendrograms: a survey, Discrete Applied Mathematics, 7 (1984), 191-199.
G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
R. Ondrejka, Tables of double factorials, Math. Comp., 24 (1970), 231.
L. Pachter and B. Sturmfels, The mathematics of phylogenomics, arXiv:math/0409132 [math.ST], 2004-2005.
K. Phillips, R functions to symbolically compute the central moments of the multivariate normal distribution, Journal of Statistical Software, Feb 2010.
R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
Helmut Prodinger, Descendants in heap ordered trees or a triumph of computer algebra, The Electronic Journal of Combinatorics, Volume 3, Issue 1 (1996), R29.
S. Ramanujan, Question 541, J. Ind. Math. Soc.
D. F. Robinson, Comparison of labeled trees with valency three, J. Combin. Theory Ser. B, 11 (1971), 105-119.
M. D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications, J. Int. Seq. 13 (2010), 10.6.7, (6.27).
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
Y. S. Song, On the combinatorics of rooted binary phylogenetic trees, Annals of Combinatorics, 7, 2003, 365-379. See Lemma 2.1. - _N. J. A. Sloane_, Aug 22 2014
D. Speyer and B. Sturmfels, The tropical Grassmannian, arXiv:0304218 [math.AG], 2003.
Neriman Tokcan, Jonathan Gryak, Kayvan Najarian, and Harm Derksen, Algebraic Methods for Tensor Data, arXiv:2005.12988 [math.RT], 2020.
Michael Torpey, Semigroup congruences: computational techniques and theoretical applications, Ph.D. Thesis, University of St. Andrews (Scotland, 2019).
Andrew Vince and Miklos Bona, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
Michael Wallner, A bijection of plane increasing trees with relaxed binary trees of right height at most one, arXiv:1706.07163 [math.CO], 2017.
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See pp. 12-13.
Eric Weisstein's World of Mathematics, Adjacency Matrix
Eric Weisstein's World of Mathematics, Double Factorial
Eric Weisstein's World of Mathematics, Erf
Eric Weisstein's World of Mathematics, Ladder Rung Graph
Eric Weisstein's World of Mathematics, Normal Distribution Function
Wikipedia, Pfaffian
Wikipedia, Hermite polynomials
Index to divisibility sequences
Index entries for related partition-counting sequences
Index entries for sequences related to factorial numbers
Index entries for sequences related to parenthesizing
Index entries for "core" sequences

Cf. A000085, A006882, A000165 ((2n)!!), A001818, A009445, A039683, A102992, A001190 (no labels), A000680, A132101.
Cf. A086677; A055142 (for this sequence, |a(n+1)| + 1 is the number of distinct products which can be formed using commutative, nonassociative multiplication and a nonempty subset of n given variables).
Constant terms of polynomials in A098503. First row of array A099020.
Cf. A079267, A000698, A029635, A161198, A076795, A123023, A161124, A051125, A181983, A099174, A087547, A028338 (first column).
Subsequence of A248652.
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A053871 (binomial transform).
Cf. A000108, A001813, A033282, A060540, A086810, A094638, A126216, A133437, A134264, A134685, A134991, A344678.

A001147 := function(n) local i, s, t; t := 1; i := 0; Print(t, ", "); for i in [1 .. n] do t := t*(2*i-1); Print(t, ", "); od; end; A001147(100); # Stefano Spezia, Nov 13 2018

a001147 n = product [1, 3 .. 2 * n - 1]
a001147_list = 1 : zipWith (*) [1, 3 ..] a001147_list
-- Reinhard Zumkeller, Feb 15 2015, Dec 03 2011

A001147:=func< n | n eq 0 select 1 else &*[ k: k in [1..2*n-1 by 2] ] >; [ A001147(n): n in [0..20] ]; // Klaus Brockhaus, Jun 22 2011

I:=[1,3]; [1] cat [n le 2 select I[n]  else (3*n-2)*Self(n-1)-(n-1)*(2*n-3)*Self(n-2): n in [1..25] ]; // Vincenzo Librandi, Feb 19 2015

f := n->(2*n)!/(n!*2^n);
A001147 := proc(n) doublefactorial(2*n-1); end: # R. J. Mathar, Jul 04 2009
A001147 := n -> 2^n*pochhammer(1/2, n); # Peter Luschny, Aug 09 2009
G(x):=(1-2*x)^(-1/2): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..19); # Zerinvary Lajos, Apr 03 2009; aligned with offset by Johannes W. Meijer, Aug 11 2009
series(hypergeom([1,1/2],[],2*x),x=0,20); # Mark van Hoeij, Apr 07 2013

Table[(2 n - 1)!!, {n, 0, 19}] (* Robert G. Wilson v, Oct 12 2005 *)
a[ n_] := 2^n Gamma[n + 1/2] / Gamma[1/2]; (* Michael Somos, Sep 18 2014 *)
Join[{1}, Range[1, 41, 2]!!] (* Harvey P. Dale, Jan 28 2017 *)
a[ n_] := If[ n < 0, (-1)^n / a[-n], SeriesCoefficient[ Product[1 - (1 - x)^(2 k - 1), {k, n}], {x, 0, n}]]; (* Michael Somos, Jun 27 2017 *)
(2 Range[0, 20] - 1)!! (* Eric W. Weisstein, Jul 22 2017 *)

a(n):=if n=0 then 1 else sum(sum(binomial(n-1,i)*binomial(n-i-1,j)*a(i)*a(j)*a(n-i-j-1),j,0,n-i-1),i,0,n-1); /* Vladimir Kruchinin, May 06 2020 */

{a(n) = if( n<0, (-1)^n / a(-n), (2*n)! / n! / 2^n)}; /* Michael Somos, Sep 18 2014 */

x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) \\ Joerg Arndt, Apr 24 2011

from sympy import factorial2
def a(n): return factorial2(2 * n - 1)
print([a(n) for n in range(101)])  # Indranil Ghosh, Jul 22 2017

[rising_factorial(n+1,n)/2^n for n in (0..15)] # Peter Luschny, Jun 26 2012

E.g.f.: 1 / sqrt(1 - 2*x).
D-finite with recurrence: a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/A000165(n).
a(n) ~ sqrt(2) * 2^n * (n/e)^n.
Rational part of numerator of Gamma(n+1/2): a(n) * sqrt(Pi) / 2^n = Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001
With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry, Jun 27 2003
The Ramanujan polynomial psi(n+1, n) has value a(n). - Ralf Stephan, Apr 16 2004
a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k). - Philippe Deléham, Oct 29 2005
Log(1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + ...) = x + 5/2*x^2 + 37/3*x^3 + 353/4*x^4 + 4081/5*x^5 + 55205/6*x^6 + ..., where [1, 5, 37, 353, 4081, 55205, ...] = A004208. - Philippe Deléham, Jun 20 2006
1/3 + 2/15 + 3/105 + ... = 1/2. [Jolley eq. 216]
Sum_{j=1..n} j/a(j+1) = (1 - 1/a(n+1))/2. [Jolley eq. 216]
1/1 + 1/3 + 2/15 + 6/105 + 24/945 + ... = Pi/2. - Gary W. Adamson, Dec 21 2006
a(n) = (1/sqrt(2*Pi))*Integral_{x>=0} x^n*exp(-x/2)/sqrt(x). - Paul Barry, Jan 28 2008
a(n) = A006882(2n-1). - R. J. Mathar, Jul 04 2009
G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). - Paul Barry, Sep 18 2009
a(n) = (-1)^n*subs({log(e)=1,x=0},coeff(simplify(series(e^(x*t-t^2/2),t,2*n+1)),t^(2*n))*(2*n)!). - Leonid Bedratyuk, Oct 31 2009
a(n) = 2^n*gamma(n+1/2)/gamma(1/2). - Jaume Oliver Lafont, Nov 09 2009
G.f.: 1/(1-x/(1-2x/(1-3x/(1-4x/(1-5x/(1- ...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
The g.f. of a(n+1) is 1/(1-3x/(1-2x/(1-5x/(1-4x/(1-7x/(1-6x/(1-.... (continued fraction). - Paul Barry, Dec 04 2009
a(n) = Sum_{i=1..n} binomial(n,i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
E.g.f.: A(x) = 1 - sqrt(1-2*x) satisfies the differential equation A'(x) - A'(x)*A(x) - 1 = 0. - Vladimir Kruchinin, Jan 17 2011
a(n) = A123023(2*n). - Michael Somos, Jul 24 2011
a(n) = (1/2)*Sum_{i=1..n} binomial(n+1,i)*a(i-1)*a(n-i). See link above. - Dennis P. Walsh, Dec 02 2011
a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k) [Kauers and Ko].
a(n) = A035342(n, 1), n >= 1 (first column of triangle).
a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = upper left term of M^n and sum of top row terms of M^(n-1), where M = a variant of the (1,2) Pascal triangle (Cf. A029635) as the following production matrix:
  1, 2, 0, 0, 0, ...
  1, 3, 2, 0, 0, ...
  1, 4, 5, 2, 0, ...
  1, 5, 9, 7, 2, ...
  ...
For example, a(3) = 15 is the left term in top row of M^3: (15, 46, 36, 8) and a(4) = 105 = (15 + 46 + 36 + 8).
(End)
G.f.: A(x) = 1 + x/(W(0) - x); W(k) = 1 + x + x*2*k - x*(2*k + 3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) = Sum_{i=1..n} binomial(n,i-1)*a(i-1)*a(n-i). - Dennis P. Walsh, Dec 02 2011
a(n) = A009445(n) / A014481(n). - Reinhard Zumkeller, Dec 03 2011
a(n) = (-1)^n*Sum_{k=0..n} 2^(n-k)*s(n+1,k+1), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
a(n) = (2*n)4! = Gauss_factorial(2*n,4) = Product{j=1..2*n, gcd(j,4)=1} j. - Peter Luschny, Oct 01 2012
G.f.: (1 - 1/Q(0))/x where Q(k) = 1 - x*(2*k - 1)/(1 - x*(2*k + 2)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013
G.f.: 1 + x/Q(0), where Q(k) = 1 + (2*k - 1)*x - 2*x*(k + 1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 2*x*(2*k + 1)/(2*x*(2*k + 1) - 1 + 2*x*(2*k + 2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(2*k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k + 1)/(4*k + 2 - 2*x*(2*k + 1)*(4*k + 3)/(x*(4*k + 3) + 2*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013
a(n) = (2*n - 3)*a(n-2) + (2*n - 2)*a(n-1), n > 1. - Ivan N. Ianakiev, Jul 08 2013
G.f.: G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 04 2013
a(n) = 2*a(n-1) + (2n-3)^2*a(n-2), a(0) = a(1) = 1. - Philippe Deléham, Oct 27 2013
G.f. of reciprocals: Sum_{n>=0} x^n/a(n) = 1F1(1; 1/2; x/2), confluent hypergeometric Function. - R. J. Mathar, Jul 25 2014
0 = a(n)*(+2*a(n+1) - a(n+2)) + a(n+1)*(+a(n+1)) for all n in Z. - Michael Somos, Sep 18 2014
a(n) = (-1)^n / a(-n) = 2*a(n-1) + a(n-1)^2 / a(n-2) for all n in Z. - Michael Somos, Sep 18 2014
From Peter Bala, Feb 18 2015: (Start)
Recurrence equation: a(n) = (3*n - 2)*a(n-1) - (n - 1)*(2*n - 3)*a(n-2) with a(1) = 1 and a(2) = 3.
The sequence b(n) = A087547(n), beginning [1, 4, 52, 608, 12624, ... ], satisfies the same second-order recurrence equation. This leads to the generalized continued fraction expansion lim_{n -> infinity} b(n)/a(n) = Pi/2 = 1 + 1/(3 - 6/(7 - 15/(10 - ... - n*(2*n - 1)/((3*n + 1) - ... )))). (End)
E.g.f of the sequence whose n-th element (n = 1,2,...) equals a(n-1) is 1-sqrt(1-2*x). - Stanislav Sykora, Jan 06 2017
Sum_{n >= 1} a(n)/(2*n-1)! = exp(1/2). - Daniel Suteu, Feb 06 2017
a(n) = A028338(n, 0), n >= 0. - Wolfdieter Lang, May 27 2017
a(n) = (Product_{k=0..n-2} binomial(2*(n-k),2))/n!. - Stefano Spezia, Nov 13 2018
a(n) = Sum_{i=0..n-1} Sum_{j=0..n-i-1} C(n-1,i)*C(n-i-1,j)*a(i)*a(j)*a(n-i-j-1), a(0)=1, - Vladimir Kruchinin, May 06 2020
From Amiram Eldar, Jun 29 2020: (Start)
Sum_{n>=1} 1/a(n) = sqrt(e*Pi/2)*erf(1/sqrt(2)), where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(Pi/(2*e))*erfi(1/sqrt(2)), where erfi is the imaginary error function. (End)
G.f. of reciprocals: R(x) = Sum_{n>=0} x^n/a(n) satisfies (1 + x)*R(x) = 1 + 2*x*R'(x). - Werner Schulte, Nov 04 2024

Removed erroneous comments: neither the number of n X n binary matrices A such that A^2 = 0 nor the number of simple directed graphs on n vertices with no directed path of length two are counted by this sequence (for n = 3, both are 13). - Dan Drake, Jun 02 2009

A003319 Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.

Original entry on oeis.org

1, 1, 1, 3, 13, 71, 461, 3447, 29093, 273343, 2829325, 31998903, 392743957, 5201061455, 73943424413, 1123596277863, 18176728317413, 311951144828863, 5661698774848621, 108355864447215063, 2181096921557783605, 46066653228356851631, 1018705098450570562877

Offset: 0

N. J. A. Sloane

Also the number of permutations with no global descents, as introduced by Aguiar and Sottile [Corollaries 6.3, 6.4 and Remark 6.5].
Also the dimensions of the homogeneous components of the space of primitive elements of the Malvenuto-Reutenauer Hopf algebra of permutations. This result, due to Poirier and Reutenauer [Theoreme 2.1] is stated in this form in the work of Aguiar and Sottile [Corollary 6.3] and also in the work of Duchamp, Hivert and Thibon [Section 3.3].
Related to number of subgroups of index n-1 in free group of rank 2 (i.e., maximal number of subgroups of index n-1 in any 2-generator group). See Problem 5.13(b) in Stanley's Enumerative Combinatorics, Vol. 2.
Also the left border of triangle A144107, with row sums = n!. - Gary W. Adamson, Sep 11 2008
Hankel transform is A059332. Hankel transform of aerated sequence is A137704(n+1). - Paul Barry, Oct 07 2008
For every n, a(n+1) is also the moment of order n for the probability density function rho(x) = exp(x)/(Ei(1,-x)*(Ei(1,-x) + 2*I*Pi)) on the interval 0..infinity, with Ei the exponential-integral function. - Groux Roland, Jan 16 2009
Also (apparently), a(n+1) is the number of rooted hypermaps with n darts on a surface of any genus (see Walsh 2012). - N. J. A. Sloane, Aug 01 2012
Also recurrent sequence A233824 (for n > 0) in Panaitopol's formula for pi(x), the number of primes <= x. - Jonathan Sondow, Dec 19 2013
Also the number of mobiles (cyclic rooted trees) with an arrow from each internal vertex to a descendant of that vertex. - Brad R. Jones, Sep 12 2014
Up to sign, Möbius numbers of the shard intersection orders of type A, see Theorem 1.3 in Reading reference. - F. Chapoton, Apr 29 2015
Also, a(n) is the number of distinct leaf matrices of complete non-ambiguous trees of size n. - Daniel Chen, Oct 23 2022

			G.f. = 1 + x + x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 461*x^6 + 3447*x^7 + 29093*x^8 + ...
From _Peter Luschny_, Aug 03 2022: (Start)
A permutation p in [n] (where n >= 0) is reducible if there exists an i in 1..n-1 such that for all j in the range 1..i and all k in the range i+1..n it is true that p(j) < p(k). (Note that a range a..b includes a and b.) If such an i exists we say that i splits the permutation at i.
Examples:
* () is not reducible since there is no index i which splits (). (=> a(0) = 1)
* (1) is not reducible since there is no index i which splits (1). (=> a(1) = 1)
* (1, 2) is reducible since index 1 splits (1, 2) as p(1) < p(2).
* (2, 1) is not reducible since at the only potential splitting point i = 1 we have p(1) > p(2). (=> a(2) = 1)
* For n = 3 we have (1, 2, 3), (1, 3, 2), and (2, 1, 3) are reducible and (2, 3, 1), (3, 1, 2), and (3, 2, 1) are irreducible. (End)

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25, Example 20.
E. W. Bowen, Letter to N. J. A. Sloane, Aug 27 1976.
L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 84 (#25), 262 (#14) and 295 (#16).
P. de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 23, N_{n,2}.
I. M. Gessel and R. P. Stanley, Algebraic Enumeration, chapter 21 in Handbook of Combinatorics, Vol. 2, edited by R. L. Graham et al., The MIT Press, Mass, 1995.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 22.
H. P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 1, Ex. 128; Vol. 2, 1999, see Problem 5.13(b).

Seiichi Manyama, Table of n, a(n) for n = 0..449 (first 102 terms from T. D. Noe)
Marcelo Aguiar and Frank Sottile, Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, arXiv:math/0203282 [math.CO], 2002-2005.
Marcelo Aguiar and Aaron Lauve, Convolution Powers of the Identity, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, pp.1053-1064, 2013, DMTCS Proceedings. .
M. Aguiar and A. Lauve, Antipode and Convolution Powers of the Identity in Graded Connected Hopf Algebras, FPSAC 2013 Paris, France DMTCS Proc. AS, 2013, 1083-1094.
M. Aguiar and A. Lauve, The characteristic polynomial of the Adams operators on graded connected Hopf algebras, 2014.
Marcelo Aguiar and Swapneel Mahajan, On the Hadamard product of Hopf monoids, 2013.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 10.
Joerg Arndt, Generating Random Permutations, PhD thesis, Australian National University, Canberra, Australia, (2010).
Joerg Arndt, Matters Computational (The Fxtbook), p. 281
Roland Bacher and Christophe Reutenauer, Number of right ideals and a q-analogue of indecomposable permutations, arXiv preprint arXiv:1511.00426 [math.CO], 2015.
Paul Barry, A note on number triangles that are almost their own production matrix, arXiv:1804.06801 [math.CO], 2018.
Julien Berestycki, Eric Brunet and Zhan Shi, How many evolutionary histories only increase fitness?, arXiv preprint arXiv:1304.0246 [math.PR], 2013.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
E. W. Bowen and N. J. A. Sloane, Correspondence, 1976.
Glenn Bruda, Asymptotic expansions for the reciprocal Hardy-Littlewood logarithmic integrals, arXiv:2412.19866 [math.CO], 2024. See pages 1, 7.
David Callan, Counting Stabilized-Interval-Free Permutations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.1.8.
Peter Cameron's Blog, The symmetric group, 11, Posted 09/04/2011.
Mahir Bilen Can, Luke Nelson, and Kevin Treat, A Catalanization Map on the Symmetric Group, Enum. Comb. Appl. (2022) Vol. 2, No. 4, #S4PP7.
Daniel Chen and Sebastian Ohlig, Associated Permutations of Complete Non-Ambiguous Trees and Zubieta's Conjecture, arXiv:2210.11117 [math.CO], 2022.
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.
L. Comtet, Sur les coefficients de l'inverse de la série formelle Sum n! t^n, Comptes Rend. Acad. Sci. Paris, A 275 (1972), 569-572.
L. Comtet, Series inversions, C. R. Acad. Sc. Paris, t. 275 (25 septembre 1972), 569-572. (Annotated scanned copy)
Xinle Dai, Jordan Long, and Karen Yeats, Subdivergence-free gluings of trees, arXiv:2106.07494 [math.CO], 2021.
M. A. Deryagina and A. D. Mednykh, On the enumeration of circular maps with given number of edges, Siberian Mathematical Journal, 54, No. 6, 2013, 624-639.
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969) 199-205.
John D. Dixon, Asymptotics of Generating the Symmetric and Alternating Groups, Electronic Journal of Combinatorics, vol 11(2), R56.
G. Duchamp, F. Hivert, and J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, arXiv:math/0105065 [math.CO], 2001.
G. A. Edgar, Transseries for beginners, arXiv:0801.4877 [math.RA], 2008-2009.
Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 19.
Jesse Elliott, Asymptotic expansions of the prime counting function, arXiv:1809.06633 [math.NT], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 90.
A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
I. M. Gessel and R. P. Stanley Algebraic Enumeration (See pages 7-8 for generating function.)
R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
P. Hegarty and A. Martinsson, On the existence of accessible paths in various models of fitness landscapes, arXiv preprint arXiv:1210.4798 [math.PR], 2012. - From _N. J. A. Sloane_, Jan 01 2013
V. Jelínek and P. Valtr, Splittings and Ramsey Properties of Permutation Classes, arXiv preprint arXiv:1307.0027 [math.CO], 2013.
B. R. Jones, On tree hook length formulas, Feynman rules and B-series, Master's thesis, Simon Fraser University, 2014.
A. King, Generating indecomposable permutations, Discrete Math., 306 (2006), 508-518.
Y. Koh and S. Ree, Connected permutation graphs, Discrete Math. 307 (2007), 2628-2635.
M. K. Krotter, I. C. Christov, J. M. Ottino and R. M. Lueptow, Cutting and Shuffling a Line Segment: Mixing by Interval Exchange Transformations, arXiv preprint arXiv:1208.2052 [physics.flu-dyn], 2012. - From _N. J. A. Sloane_, Dec 25 2012
Ajay Kumar and Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
Chanchal Kumar and Amit Roy, Integer Sequences and Monomial Ideals, arXiv:2003.10098 [math.CO], 2020.
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 292.
Richard J. Martin and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions (2008); arXiv:0806.3682 [math.CO]. Discrete Math. 310 (2010), no. 24, 3584-3606.
P. Ossona de Mendez and P. Rosenstiehl, Transitivity and connectivity of permutations, Combinatorica, 24 (No. 3, 2004), 487-501.
L. Panaitopol, A formula for pi(x) applied to a result of Koninck-Ivić, Nieuw Arch. Wisk. 5/1 55-56 (2000).
Vincent Pilaud, Brick polytopes, lattice quotients, and Hopf algebras, arXiv:1505.07665 [math.CO], 2015.
S. Poirier and C. Reutenauer, Algèbres Hopf de tableaux, Ann. Sci. Math. Quebec 19 (95), no. 1, 79-90.
N. Reading Noncrossing partitions and the shard intersection order. J. Algebraic Combin. 33 (2011), no. 4. arXiv preprint arXiv:0909.3288, [math.CO], 2009.
Herman P. Robinson, Letter to N. J. A. Sloane, Nov 19 1973.
R. P. Stanley, The Descent Set and Connectivity Set of a Permutation, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.8.
Timothy R. Walsh, Space-efficient generation of nonisomorphic maps and hypermaps, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.3.
Marcel Wienöbst, Max Bannach, and Maciej Liśkiewicz, Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications, arXiv:2205.02654 [cs.LG], 2022.
Jun Yan, Results on pattern avoidance in parking functions, arXiv:2404.07958 [math.CO], 2024. See p. 7.

See A167894 for another version.
Bisections give A272656, A272657.
Row sums of A111184 and A089949.
Leading diagonal of A059438. A diagonal of A263484.
Cf. A051296, A084938, A074664, A113869, A144107.
Cf. A260503, A259472, A261214, A261239, A261253, A261254.
Cf. A090238, A000698, A356291 (reducible permutations).
Column k=0 of A370380 and A370381 (without pair of initial terms and with different offset).

INVERTi([seq(n!,n=1..20)]);
A003319 := proc(n) option remember; n! - add((n-j)!*A003319(j), j=1..n-1) end;
[seq(A003319(n), n=0..50)]; # N. J. A. Sloane, Dec 28 2011
series(2 - 1/hypergeom([1,1], [], x), x=0,50); # Mark van Hoeij, Apr 18 2013

a[n_] := a[n] = n! - Sum[k!*a[n-k], {k, 1, n-1}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Oct 11 2011, after given formula *)
CoefficientList[Assuming[Element[x,Reals],Series[2-E^(1/x)* x/ExpIntegralEi[1/x],{x,0,20}]],x] (* Vaclav Kotesovec, Mar 07 2014 *)
a[ n_] := If[ n < 2, 1, a[n] = (n - 2) a[n - 1] + Sum[ a[k] a[n - k], {k, n - 1}]]; (* Michael Somos, Feb 23 2015 *)
Table[SeriesCoefficient[1 + x/(1 + ContinuedFractionK[-Floor[(k + 2)/2]*x, 1, {k, 1, n}]), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Sep 29 2017 *)

{a(n) = my(A); if( n<1, 1, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (k - 2) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 24 2011 */

{if(n<1,1,a(n)=local(A=x);for(i=1,n,A=x-x*A+A^2+x^2*A' +x*O(x^n));polcoeff(A,n))} /* Paul D. Hanna, Jul 30 2011 */

def A003319_list(len):
    R, C = [1], [1] + [0] * (len - 1)
    for n in range(1, len):
        for k in range(n, 0, -1):
            C[k] = C[k - 1] * k
        C[0] = -sum(C[k] for k in range(1, n + 1))
        R.append(-C[0])
    return R
print(A003319_list(21))  # Peter Luschny, Feb 19 2016

G.f.: 2 - 1/Sum_{k>=0} k!*x^k.
Also a(n) = n! - Sum_{k=1..n-1} k!*a(n-k) [Bowen, 1976].
Also coefficients in the divergent series expansion log Sum_{n>=0} n!*x^n = Sum_{n>=1} a(n+1)*x^n/n [Bowen, 1976].
a(n) = (-1)^(n-1) * det {| 1! 2! ... n! | 1 1! ... (n-1)! | 0 1 1! ... (n-2)! | ... | 0 ... 0 1 1! |}.
INVERTi transform of factorial numbers, A000142 starting from n=1. - Antti Karttunen, May 30 2003
Gives the row sums of the triangle [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] where DELTA is the operator defined in A084938; this triangle A089949. - Philippe Deléham, Dec 30 2003
a(n+1) = Sum_{k=0..n} A089949(n,k). - Philippe Deléham, Oct 16 2006
L.g.f.: Sum_{n>=1} a(n)*x^n/n = log( Sum_{n>=0} n!*x^n ). - Paul D. Hanna, Sep 19 2007
G.f.: 1+x/(1-x/(1-2*x/(1-2*x/(1-3*x/(1-3*x/(1-4*x/(1-4*x/(1-...)))))))) (continued fraction). - Paul Barry, Oct 07 2008
a(n) = -Sum_{i=0..n} (-1)^i*A090238(n, i) for n > 0. - Peter Luschny, Mar 13 2009
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) = upper left term in M^(n-1), M = triangle A128175 as an infinite square production matrix (deleting the first "1"); as follows:
   1,  1,  0,  0,  0,  0, ...
   2,  2,  1,  0,  0,  0, ...
   4,  4,  3,  1,  0,  0, ...
   8,  8,  7,  4,  1,  0, ...
  16, 16, 15, 11,  5,  1, ...
  ... (End)
O.g.f. satisfies: A(x) = x - x*A(x) + A(x)^2 + x^2*A'(x). - Paul D. Hanna, Jul 30 2011
From Sergei N. Gladkovskii, Jun 24 2012: (Start)
Let A(x) be the g.f.; then
A(x) = 1/Q(0), where Q(k) = x + 1 + x*k - (k+2)*x/Q(k+1).
A(x) = (1-1/U(0))/x, when U(k) = 1 + x*(2*k+1)/(1 - 2*x*(k+1)/(2*x*(k+1) + 1/U(k+1))). (End)
From Sergei N. Gladkovskii, Aug 03 2013: (Start)
Continued fractions:
G.f.: 1 - G(0)/2, where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+2) - 1 + x*(2*k+2)/G(k+1))).
G.f.: (x/2)*G(0), where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1/2) + 1/G(k+1))).
G.f.: x*G(0), where G(k) = 1 - x*(k+1)/(x - 1/G(k+1)).
G.f.: 1 - 1/G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+1)/(x*(k+1) - 1/G(k+1)))).
G.f.: x*W(0), where W(k) = 1 - x*(k+1)/(x*(k+1) - 1/(1 - x*(k+2)/(x*(k+2) - 1/W(k+1)))).
(End)
a(n) = A233824(n-1) if n > 0. (Proof. Set b(n) = A233824(n), so that b(n) = n*n! - Sum_{k=1..n-1} k!*b(n-k). To get a(n+1) = b(n) for n >= 0, induct on n, use (n+1)! = n*n! + n!, and replace k with k+1 in the sum.) - Jonathan Sondow, Dec 19 2013
a(n) ~ n! * (1 - 2/n - 1/n^2 - 5/n^3 - 32/n^4 - 253/n^5 - 2381/n^6 - 25912/n^7 - 319339/n^8 - 4388949/n^9 - 66495386/n^10), for coefficients see A260503. - Vaclav Kotesovec, Jul 27 2015
For n>0, a(n) = (A059439(n) - A259472(n))/2. - Vaclav Kotesovec, Aug 03 2015
From Peter Bala, May 23 2017: (Start)
G.f.: 1 + x/(1 + x - 2*x/(1 + 2*x - 3*x/(1 + 3*x - 4*x/(1 + 4*x - ...)))). Cf. A000698.
G.f.: 1/(1 - x/(1 + x - x/(1 - 2*x/(1 - 2*x/(1 - 3*x/(1 - 3*x/(1 - 4*x/(1 - 4*x/(1 - ...))))))))). (End)
Conjecture: a(n) = A370380(n-2, 0) = A370381(n-2, 0) for n > 1 with a(0) = a(1) = 1. - Mikhail Kurkov, Apr 26 2024

More terms from Michael Somos, Jan 26 2000
Additional comments from Marcelo Aguiar (maguiar(AT)math.tamu.edu), Mar 28 2002
Added a(0)=0 (some of the formulas may now need adjusting). - N. J. A. Sloane, Sep 12 2012
Edited and set a(0) = 1 by Peter Luschny, Aug 03 2022

A000699 Number of irreducible chord diagrams with 2n nodes.

Original entry on oeis.org

1, 1, 1, 4, 27, 248, 2830, 38232, 593859, 10401712, 202601898, 4342263000, 101551822350, 2573779506192, 70282204726396, 2057490936366320, 64291032462761955, 2136017303903513184, 75197869250518812754, 2796475872605709079512, 109549714522464120960474, 4509302910783496963256400, 194584224274515194731540740

Offset: 0

N. J. A. Sloane

Perturbation expansion in quantum field theory: spinor case in 4 spacetime dimensions.
a(n)*2^(-n) is the coefficient of the x^(2*n-1) term in the series reversal of the asymptotic expansion of 2*DawsonF(x) = sqrt(Pi)*exp(-x^2)*erfi(x) for x -> inf. - Vladimir Reshetnikov, Apr 23 2016
The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018
A set partition is topologically connected if the graph whose vertices are the blocks and whose edges are crossing pairs of blocks is connected, where two blocks cross each other if they are of the form {{...x...y...},{...z...t...}} for some x < z < y < t or z < x < t < y. Then a(n) is the number of topologically connected 2-uniform set partitions of {1...2n}. See my links for examples. - Gus Wiseman, Feb 23 2019
From Julien Courtiel, Oct 09 2024: (Start)
a(n) is the number of rooted bridgeless combinatorial maps with n edges (genus is not fixed). A map is bridgeless if it has no edge whose removal disconnects the graph. For example, for n=2, there are 4 bridgeless maps with 2 edges: 2 planar maps with 1 vertex (either two consecutive loops, or two nested loops), 1 toric map with 1 vertex, and 1 planar map with 2 vertices connected by a double edge.
Also, a(n) is the number of trees with n edges equipped with a binary tubing. A tube is a connected subgraph. A binary tubing of a tree is a nested set collection S of tubes such that 1. S contains the tube of all vertices 2. Every tube of S is either reduced to one vertex, or it can be can partitioned by 2 tubes of S.
(End)

			a(31)=627625976637472254550352492162870816129760 was computed using Kreimer's Hopf algebra of rooted trees. It subsumes 2.6*10^21 terms in quantum field theory.
G.f.: A(x) = 1 + x + x^2 + 4*x^3 + 27*x^4 + 248*x^5 + 2830*x^6 +...
where d/dx (A(x) - 1)^2/x = 1 + 4*x + 27*x^2 + 248*x^3 + 2830*x^4 +...

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

Alois P. Heinz, Table of n, a(n) for n = 0..404 (terms up to n=100 from T. D. Noe)
Serban T. Belinschi, Marek Bozejko, Franz Lehner, and Roland Speicher, The normal distribution is "boxplus"-infinitely divisible, arXiv:0910.4263 [math.OA], 2009-2010.
Daniel J. Bernstein, S. Engels, T. Lange, R. Niederhagen, et al., Faster elliptic-curve discrete logarithms on FPGAs, Preprint, 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, arXiv preprint arXiv:1603.01236 [math.CO], 2016.
Michael Borinsky, Generating asymptotics for factorially divergent sequences, El. J. Combin. 25 (2018) P4.1, Sect 7.1.
Michael Borinsky, Gerald V. Dunne, and Karen Yeats, Tree-tubings and the combinatorics of resurgent Dyson-Schwinger equations, arXiv:2408.15883 [math-ph], 2024. See p. 9.
David J. Broadhurst and Dirk Kreimer, Combinatoric explosion of renormalization ..., arXiv:hep-th/9912093, 1999, 2000.
David J. Broadhurst and Dirk Kreimer, Combinatoric explosion of renormalization tamed by Hopf algebra: 30-loop Pad-Borel resummation, Phys. Lett. B 475 (2000), 63-70.
Christian Brouder, On the trees of quantum fields, arXiv:hep-th/9906111, 1999, p. 6.
Jonathan Burns, Assembly Graph Words - Single Transverse Component (Counts).
Jonathan Burns, Egor Dolzhenko, Natasa Jonoska, Tilahun Muche and Masahico Saito, Four-Regular Graphs with Rigid Vertices Associated to DNA Recombination, May 23, 2011.
Jonathan Burns and Tilahun Muche, Counting Irreducible Double Occurrence Words, arXiv preprint arXiv:1105.2926 [math.CO], 2011.
Julien Courtiel, Karen Yeats, and Noam Zeilberger, Connected chord diagrams and bridgeless maps, arXiv:1611.04611 [math.CO], 2016.
Serge Dulucq, Etude combinatoire de problèmes d'énumération, d'algorithmique sur les arbres et de codage par des mots, a thesis presented to l'Université de Bordeaux I, 1987. (Annotated scanned copy)
Philippe Flajolet and Marc Noy, Analytic Combinatorics of Chord Diagrams, in: Formal power series and algebraic combinatorics (FPSAC '00) Moscow, 2000, pp. 191-201.
Zhen Huang, Denis Golež, Hugo U. R. Strand, and Jason Kaye, Automated evaluation of imaginary time strong coupling diagrams by sum-of-exponentials hybridization fitting, arXiv:2503.19727 [cond-mat.str-el], 2025. See p. 21.
Martin Klazar, Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings, Advances in Appl. Math., Vol. 30 (2003), pp. 126-136.
Martin Klazar, Counting even and odd partitions, Amer. Math. Monthly, 110 (No. 6, 2003), 527-532.
Florian Kogelbauer and Ilya Karlin, On the Relation of Exact Hydrodynamics to the Chapman-Enskog Series, arXiv:2506.17441 [math-ph], 2025. See pp. 4-5.
Ali Assem Mahmoud, On the Asymptotics of Connected Chord Diagrams, University of Waterloo (Ontario, Canada 2019).
Ali Assem Mahmoud, An Asymptotic Expansion for the Number of 2-Connected Chord Diagrams, arXiv:2009.12688 [math.CO], 2020.
Ali Assem Mahmoud, Chord Diagrams and the Asymptotic Analysis of QED-type Theories, arXiv:2011.04291 [hep-th], 2020.
Ali Assem Mahmoud, An asymptotic expansion for the number of two-connected chord diagrams, J. Math. Phys. (2023) Vol. 64, 122301. See Example 2.1.
Ali Assem Mahmoud and Karen Yeats, Connected Chord Diagrams and the Combinatorics of Asymptotic Expansions, arXiv:2010.06550 [math.CO], 2020.
Nicolas Marie and Karen Yeats, A chord diagram expansion coming from some Dyson-Schwinger equations, arXiv:1210.5457 [math.CO], 2012, Section 4.1.
Albert Nijenhuis and Herbert S. Wilf, The enumeration of connected graphs and linked diagrams, J. Combin. Theory Ser. A 27 (1979), no. 3, 356--359. MR0555804 (82b:05074).
Vincent Pilaud and Juanjo Rué, Analytic combinatorics of chord and hyperchord diagrams with k crossings, arXiv preprint arXiv:1307.6440 [math.CO], 2013.
J. Riordan, Letter, Jul 06 1978
Einar A. Rødland, Pseudoknots in RNA Secondary Structures: Representation, Enumeration, and Prevalence, J. Comput. Biology, Vol 13, No 6 (2006), 1197-1213. (see equation 10)
R. R. Stein, On a class of linked diagrams, I. Enumeration, J. Combin. Theory, A 24 (1978), 357-366.
R. R. Stein and C. J. Everett, On a class of linked diagrams, II. Asymptotics, Discrete Math., 21 (1978), 309-318.
Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25.
Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math., 4 (1952), 2-25. [Annotated, corrected, scanned copy]
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259 (nonseparable integer systems on n pairs). (Give an incorrect a(6)=2720.)
Gus Wiseman, The a(4) = 27 connected chord diagrams.
Gus Wiseman, The a(5) = 248 connected chord diagrams.
Gus Wiseman, Constructive Mathematica program for A000699.
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv:1803.10080 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Rutgers Experimental Math Seminar, Sep 13 2018. Part 2 is vimeo.com/289910554.

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
Cf. A004300, A051862, A212273. Column sums of A232223. First column of A322402.
Cf. A007297, A016098, A099947, A136653, A268815, A306438, A324166, A324172, A324173, A324327.

A000699 := proc(n)
    option remember;
    if n <= 1 then
        1;
    else
        add((2*i-1)*procname(i)*procname(n-i),i=1..n-1) ;
    end if;
end proc:
seq(A000699(n),n=0..30) ; # R. J. Mathar, Jun 12 2018

terms = 22; A[] = 0; Do[A[x] = x + x^2 * D[A[x]^2/x, x] + O[x]^(terms+1) // Normal, terms]; CoefficientList[A[x], x] // Rest (* Jean-François Alcover, Apr 06 2012, after Paul D. Hanna, updated Jan 11 2018 *)
a = ConstantArray[0,20]; a[[1]]=1; Do[a[[n]] = (n-1)*Sum[a[[i]]*a[[n-i]],{i,1,n-1}],{n,2,20}]; a (* Vaclav Kotesovec, Feb 22 2014 *)
Module[{max = 20, s}, s = InverseSeries[ComplexExpand[Re[Series[2 DawsonF[x], {x, Infinity, 2 max + 1}]]]]; Table[SeriesCoefficient[s, 2 n - 1] 2^n, {n, 1, max}]] (* Vladimir Reshetnikov, Apr 23 2016 *)

{a(n)=local(A=1+x*O(x^n)); for(i=1, n, A=1+x+x^2*deriv((A-1)^2/x)+x*O(x^n)); polcoeff(A, n)} \\ Paul D. Hanna, Dec 31 2010 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]

{a(n) = my(A); A = 1+O(x) ; for( i=0, n, A = 1+x + (A-1)*(2*x*A' - A + 1)); polcoeff(A, n)}; /* Michael Somos, May 12 2012 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020] */

seq(N) = {
  my(a = vector(N)); a[1] = 1;
  for (n=2, N, a[n] = sum(k=1, n-1, (2*k-1)*a[k]*a[n-k])); a;
};
seq(22)  \\ Gheorghe Coserea, Jan 22 2017

seq(n)={my(g=serlaplace(1 / sqrt(1 - 2*x + O(x*x^n)))); Vec(sqrt((x/serreverse( x*g^2 ))))} \\ Andrew Howroyd, Nov 21 2024

def A000699_list(n):
    list = [1, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        list[i] = (i - 1) * sum(list[j] * list[i - j] for j in range(1, i))
    return list
print(A000699_list(22)) # M. Eren Kesim, Jun 23 2021

a(n) = (n-1)*Sum_{i=1..n-1} a(i)*a(n-i) for n > 1, with a(1) = a(0) = 1. [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]
A212273(n) = n * a(n). - Michael Somos, May 12 2012
G.f. satisfies: A(x) = 1 + x + x^2*[d/dx (A(x) - 1)^2/x]. - Paul D. Hanna, Dec 31 2010 [Modified to include a(0) = 1. - Paul D. Hanna, Nov 06 2020]
a(n) ~ n^n * 2^(n+1/2) / exp(n+1) * (1 - 31/(24*n) - 2207/(1152*n^2) - 3085547/(414720*n^3) - 1842851707/(39813120*n^4) - ...). - Vaclav Kotesovec, Feb 22 2014, extended Oct 23 2017
G.f. A(x) satisfies: 1 = A(x) - x/(A(x) - 2*x/(A(x) - 3*x/(A(x) - 4*x/(A(x) - 5*x/(A(x) - ...))))), a continued fraction relation. - Paul D. Hanna, Nov 04 2020
G.f. A(x) satisfies: A(x*B(x)^2) = B(x) where B(x) is the g.f. of A001147. - Andrew Howroyd, Nov 21 2024

More terms from David Broadhurst, Dec 14 1999
Inserted "chord" in definition. - N. J. A. Sloane, Jan 19 2017
Added a(0)=1. - N. J. A. Sloane, Nov 05 2020
Modified formulas slightly to include a(0) = 1. - Paul D. Hanna, Nov 06 2020

A000260 Number of rooted simplicial 3-polytopes with n+3 nodes; or rooted 3-connected triangulations with 2n+2 faces; or rooted 3-connected trivalent maps with 2n+2 vertices.

Original entry on oeis.org

1, 1, 3, 13, 68, 399, 2530, 16965, 118668, 857956, 6369883, 48336171, 373537388, 2931682810, 23317105140, 187606350645, 1524813969276, 12504654858828, 103367824774012, 860593023907540, 7211115497448720, 60776550501588855

Offset: 0

N. J. A. Sloane

Number of rooted loopless planar maps with n edges. E.g., there are a(2)=3 loopless planar maps with 2 edges: two rooted paths (.-.-.) and one digon (.=.). - Valery A. Liskovets, Sep 25 2003
Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Tamari lattice (rotation lattice of binary trees) of size n (see Pallo and Chapoton references). - Ralf Stephan, May 08 2007, Jean Pallo (Jean.Pallo(AT)u-bourgogne.fr), Sep 11 2007
Number of rooted triangulations of type [n, 0] (see Brown paper eq (4.8)). - Michel Marcus, Jun 23 2013
Equivalently, number of rooted bridgeless planar maps with n edges. - Noam Zeilberger, Oct 06 2016
The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018
Number of uniquely sorted permutations of [2n+1] that avoid the pattern 231. Also the number of uniquely sorted permutations of [2n+1] that avoid 132. - Colin Defant, Jun 13 2019
The sequence 1,3,13,68,... appears naturally in integral geometry, namely in the algebra of unitarily invariant valuations on complex space forms. - Andreas Bernig, Feb 02 2020

			G.f. = 1 + x + 3*x^2 + 13*x^3 + 68*x^4 + 399*x^5 + 2530*x^6 + 16965*x^7 + ...

C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
Handbook of Combinatorics, North-Holland '95, p. 891.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
W. T. Tutte, The enumerative theory of planar maps, in A Survey of Combinatorial Theory (J. N. Srivastava et al. eds.), pp. 437-448, North-Holland, Amsterdam, 1973.

T. D. Noe, Table of n, a(n) for n = 0..200
E. A. Bender and N. C. Wormald, The number of loopless planar maps, Discr. Math. 54:2 (1985), 235-237.
Andreas Bernig, Unitarily invariant valuations and Tutte's sequence, arXiv:2001.03372 [math.DG], 2020.
Alin Bostan, Frédéric Chyzak, Bérénice Delcroix-Oger, Guillaume Laplante-Anfossi, Vincent Pilaud, and Kurt Stoeckl, Diagonals of permutahedra and associahedra, Sém. Lotharingien Comb., 37th Formal Power Series Alg. Comb. (FPSAC 2025). See pp. 10-11.
Alin Bostan, Frédéric Chyzak, and Vincent Pilaud, Refined product formulas for Tamari intervals, arXiv:2303.10986 [math.CO], 2023.
T. Daniel Brennan, Christian Ferko, and Savdeep Sethi, A Non-Abelian Analogue of DBI from $T \overline{T}$, arXiv:1912.12389 [hep-th], 2019. See also SciPost Phys. (2020) Vol. 8, 052.
Enrica Duchi and Corentin Henriet, A bijection between Tamari intervals and extended fighting fish, arXiv:2206.04375 [math.CO], 2022.
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
Frédéric Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, arXiv:math/0602368 [math.CO], 2006.
Grégory Chatel, Vincent Pilaud, and Viviane Pons, The weak order on integer posets, arXiv:1701.07995 [math.CO], 2017.
Grégory Chatel and Viviane Pons, Counting smaller elements in the Tamari and m-Tamari lattices, arXiv preprint arXiv:1311.3922 [math.CO], 2013.
François David, A model of random surfaces with nontrivial critical behavior, Nuclear Physics B, v. 257 (1985), 543-576.
Colin Defant, Catalan Intervals and Uniquely Sorted Permutations, arXiv:1904.02627 [math.CO], 2019.
C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
Wenjie Fang, Planar triangulations, bridgeless planar maps and Tamari intervals, arXiv:1611.07922 [math.CO], 2016.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
C. Germain and J. Pallo, The number of coverings in four Catalan lattices, Intern. J. Computer Math., Vol. 61 (1996) pp. 19-28. (See p. 27.)
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
Zhaoxiang Li and Yanpei Liu, Chromatic sums of general maps on the sphere and the projective plane, Discr. Math. 307 (2007), 78-87.
Michaël Moortgat, The Tamari order for D^3 and derivability in semi-associative Lambek-Grishin Calculus, 15th Workshop: Computational Logic and Applications (CLA 2020).
K. A. Penson, K. Górska, A. Horzela, and G. H. E. Duchamp, Hausdorff moment problem for combinatorial numbers of Brown and Tutte: exact solution, arXiv:2209.06574 [math.CO], 2022.
Viviane Pons, Combinatorics of the Permutahedra, Associahedra, and Friends, arXiv:2310.12687 [math.CO], 2023. See p. 37.
W. T. Tutte, A census of Hamiltonian polygons, Canad. J. Math., 14 (1962), 402-417.
William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38. See Eq. 5.12.
William T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), no. 2, 105-126. MR0572468 (81j:05073).
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. III: Nonseparable maps, J. Combinatorial Theory Ser. B 18 (1975), 222-259, eq. (6).
Noam Zeilberger, A sequent calculus for the Tamari order, arXiv:1701.02917 [cs.LO], 2017.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030 [math.LO], 2018-2019 (A revised version of a 2017 conference paper).
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Rutgers Experimental Math Seminar, Sep 13 2018. See also Part 2.

Row sums of A342981.
Column 0 of A146305 and A341856; Column 2 of A255918.
Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
Cf. A000256, A006013, A027836, A069271, A263191, A290326.

[Binomial(4*n+1, n+1)-9*Binomial(4*n+1, n-1): n in [0..25]]; // Vincenzo Librandi, Nov 24 2016

A000260 := proc(n)
    2*(4*n+1)!/((n+1)!*(3*n+2)!) ;
end proc:

Table[Binomial[4n+1,n+1]-9*Binomial[4n+1,n-1],{n,0,25}] (* Harvey P. Dale, Aug 23 2011 *)
a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1/2, 3/4, 1, 5/4}, {4/3, 5/3, 2}, 256/27 x], {x, 0, n}]; (* Michael Somos, Dec 23 2014 *)
terms = 22; G[] = 0; Do[G[x] = 1+x*G[x]^4 + O[x]^terms, terms];
CoefficientList[(2-G[x])*G[x]^2, x] (* Jean-François Alcover, Jan 13 2018, after Mark van Hoeij *)

{a(n) = if( n<0, 0, 2 * (4*n + 1)! / ((n + 1)! * (3*n + 2)!))}; /* Michael Somos, Sep 07 2005 */

{a(n) = binomial( 4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2))}; /* Michael Somos, Mar 28 2012 */

def a(n):
    n = ZZ(n)
    return (4*n + 2).binomial(n + 1) // ((2*n + 1) * (3*n + 2))
# F. Chapoton, Aug 06 2015

a(n) = 2*(4*n+1)! / ((n+1)!*(3*n+2)!) = binomial(4*n+1, n+1) - 9*binomial(4*n+1, n-1).
G.f.: (2-g)*g^2 where g = 1 + x*g^4 is the g.f. of A002293. - Mark van Hoeij, Nov 10 2011
G.f.: hypergeom([1,1/2,3/4,5/4],[2,4/3,5/3],256*x/27) = 1 + 120*x/(Q(0)-120*x); Q(k) = 8*x*(2*k+1)*(4*k+3)*(4*k+5) + 3*(k+2)*(3*k+4)*(3*k+5) - 24*x*(k+2)*(2*k+3)*(3*k+4)*(3*k+5)*(4*k+7)*(4*k+9)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 25 2011
a(n) = binomial(4*n + 2, n + 1) / ((2*n + 1) * (3*n + 2)). - Michael Somos, Mar 28 2012
a(n) * (n+1) = A069271(n). - Michael Somos, Mar 28 2012
0 = F(a(n), a(n+1), ..., a(n+8)) for all n in Z where a(-1) = 3/4 and F() is a polynomial of degree 2 with integer coefficients and 29 monomials. - Michael Somos, Dec 23 2014
D-finite with recurrence: 3*(3*n+2)*(3*n+1)*(n+1)*a(n) - 8*(4*n+1)*(2*n-1)*(4*n-1)*a(n-1) = 0. - R. J. Mathar, Oct 21 2015
a(n) = Sum_{k=1..A000108(n)} k * A263191(n,k). - Alois P. Heinz, Nov 16 2015
a(n) ~ 2^(8*n+7/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n+5/2)). - Vaclav Kotesovec, Feb 26 2016
E.g.f.: 3F3(1/2,3/4,5/4; 4/3,5/3,2; 256*x/27). - Ilya Gutkovskiy, Feb 01 2017
From Gheorghe Coserea, Aug 17 2017: (Start)
G.f. y(x) satisfies:
0 = x^3*y^4 + 3*x^2*y^3 + x*(8*x+3)*y^2 - (20*x-1)*y + 16*x-1.
0 = x*(256*x - 27)*deriv(y,x) - 8*x^2*y^3 - 25*x*y^2 + 4*(24*x-11)*y + 44.
(End)
From Karol A. Penson, Apr 06 2022: (Start)
a(n) = Integral_{x=0...256/27} x^n*W(x), where
W(x) = (sqrt(2)/Pi)*(h1(x) - h2(x) + h3(x)) and
h1(x) = 3F2([-6/12,-2/12,  2/12], [ 3/12,  9/12], (27*x)/256)/((x/2)^(1/2));
h2(x) = 3F2([-3/12, 1/12,  5/12], [ 6/12, 15/12], (27*x)/256)/(x^(1/4));
h3(x) = 3F2([ 3/12, 7/12, 11/12], [18/12, 21/12], (27*x)/256)/(x^(-1/4)*32).
This integral representation is unique as the solution of n-th Hausdorff power moment of the function W. Using only the definition of a(n), W(x) can be proven to be positive. W(x) is singular at x = 0 and for x > 0 is monotonically decreasing to zero at x = 256/27. (End)
a(n) = (1/27^n) * Product_{1 <= i <= j <= 3*n} (3*i + j + 3)/(3*i + j - 1). Cf. A006013. - Peter Bala, Feb 21 2023

Edited by F. Chapoton, Feb 03 2011

A000168 a(n) = 23^n(2n)!/(n!(n+2)!).

Original entry on oeis.org

1, 2, 9, 54, 378, 2916, 24057, 208494, 1876446, 17399772, 165297834, 1602117468, 15792300756, 157923007560, 1598970451545, 16365932856990, 169114639522230, 1762352559231660, 18504701871932430, 195621134074714260, 2080697516976506220, 22254416920705240440, 239234981897581334730, 2583737804493878415084

Offset: 0

N. J. A. Sloane

Number of rooted planar maps with n edges. - Don Knuth, Nov 24 2013
Number of rooted 4-regular planar maps with n vertices.
Also, number of doodles with n crossings, irrespective of the number of loops.
From Karol A. Penson, Sep 02 2010: (Start)
Integral representation as n-th moment of a positive function on the (0,12) segment of the x axis. This representation is unique as it is the solution of the Hausdorff moment problem.
a(n) = Integral_{x=0..12} ((x^n*(4/9)*(1 - x/12)^(3/2)) / (Pi*sqrt(x/3))).  (End)
Also, the number of distinct underlying shapes of closed normal linear lambda terms of a given size, where the shape of a lambda term abstracts away from its variable binding. [N. Zeilberger, 2015] - N. J. A. Sloane, Sep 18 2016
The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018
Number of well-labeled trees (Bona, 2015). - N. J. A. Sloane, Dec 25 2018

			G.f. = 1 + 2*x + 9*x^2 + 54*x^3 + 378*x^4 + 2916*x^5 + 24057*x^6 + 208494*x^7 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 319, 353.
E. R. Canfield, Calculating the number of rooted maps on a surface, Congr. Numerantium, 76 (1990), 21-34.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 714.
V. A. Liskovets, A census of nonisomorphic planar maps, in Algebraic Methods in Graph Theory, Vol. II, ed. L. Lovasz and V. T. Sos, North-Holland, 1981.
V. A. Liskovets, Enumeration of nonisomorphic planar maps, Selecta Math. Sovietica, 4 (No. 4, 1985), 303-323.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..925 [Terms 0 to 100 computed by T. D. Noe; terms 101 to 925 by G. C. Greubel, Jan 15 2017]
Marie Albenque and Dominique Poulalhon, A Generic Method for Bijections between Blossoming Trees and Planar Maps, Electron. J. Combin., 22 (2015), #P2.38.
J.-L. Baril, R. Genestier, A. Giorgetti, and A. Petrossian, Rooted planar maps modulo some patterns, Preprint 2016.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
Valentin Bonzom, Guillaume Chapuy, Maciej Dolega, Enumeration of non-oriented maps via integrability, Alg. Combin. 5 (6) (2022) p 1363-1390, A.1.
M. Bousquet-Mélou, Limit laws for embedded trees, arXiv:math/0501266 [math.CO], 2005.
M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, arXiv:math/0504018 [math.CO], 2005.
Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.
R. Cori and B. Vauquelin, Planar maps are well labeled trees, Canad. J. Math., 33 (1981), 1023-1042.
S. R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 516
A. Giorgetti, R. Genestier, and V. Senni, Software Engineering and Enumerative Combinatorics, slides from a talk at MAP 2014.
Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic Expansions for Sub-Critical Lagrangean Forms, LIPIcs Proceedings of Analysis of Algorithms 2018, Vol. 110. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018.
C. Kassel, On combinatorial zeta functions, Slides from a talk, Potsdam, 2015.
Sergey Kitaev, Anna de Mier, and Marc Noy, On the number of self-dual rooted maps, European J. Combin. 35 (2014), 377--387. MR3090510. See Eq. (1). - _N. J. A. Sloane_, May 19 2014
Evgeniy Krasko and Alexander Omelchenko, Enumeration of r-regular maps on the torus. Part I: Rooted maps on the torus, the projective plane and the Klein bottle. Sensed maps on the torus, Discrete Mathematics (2019) Vol. 342, Issue 2, 584-599. Also arXiv:1709.03225 [math.CO].
V. A. Liskovets, Enumeration of nonisomorphic planar maps, Journal of Graph Theory, Volume 5, Issue 1, pages 115-117, Spring 1981.
Valery A. Liskovets, A reductive technique for enumerating non-isomorphic planar maps, Discrete Math. 156 (1996), no. 1-3, 197--217. MR1405018 (97f:05087) - From _N. J. A. Sloane_, Jun 03 2012
R. C. Mullin, On the average activity of a spanning tree of a rooted map, J. Combin. Theory, 3 (1967), 103-121.
R. C. Mullin, On the average activity of a spanning tree of a rooted map, J. Combin. Theory, 3 (1967), 103-121. [Annotated scanned copy]
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, arXiv:0912.0072 [math.NT], 2009; FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
C. Reutenauer and M. Robado, On an algebraicity theorem of Kontsevich, FPSAC 2012, Nagoya, Japan DMTCS proc. AR, 2012, 241-248. - From _N. J. A. Sloane_, Dec 23 2012
G. Schaeffer and P. Zinn-Justin, On the asymptotic number of plane curves and alternating knots, arXiv:math-ph/0304034, 2003-2004.
W. T. Tutte, A Census of Planar Maps, Canad. J. Math. 15 (1963), 249-271.
Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015.
Noam Zeilberger, Towards a mathematical science of programming, Preprint 2015.
Noam Zeilberger, Linear lambda terms as invariants of rooted trivalent maps, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030, March 2018 (A revised version of a 2017 conference paper)
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Part 2, Rutgers Experimental Math Seminar, Sep 13 2018.
Noam Zeilberger and Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.
Jian Zhou, Fat and Thin Emergent Geometries of Hermitian One-Matrix Models, arXiv:1810.03883 [math-ph], 2018.

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
First row of array A101486.
Cf. A005470.
Rooted maps with n edges of genus g for 0 <= g <= 10: this sequence, A006300, A006301, A104742, A215402, A238355, A238356, A238357, A238358, A238359, A238360.

[(2*Catalan(n)*3^n)/(n+2): n in [1..30]]; // Vincenzo Librandi, Sep 04 2014

Maple
```
A000168:=n->2*3^n*(2*n)!/(n!*(n+2)!);
```

Table[(2*3^n*(2n)!)/(n!(n+2)!),{n,0,20}] (* Harvey P. Dale, Jul 25 2011 *)
a[ n_] := If[ n < 0, 0, 2 3^n (2 n)!/(n! (n + 2)!)] (* Michael Somos, Nov 25 2013 *)
a[ n_] := SeriesCoefficient[ Hypergeometric2F1[ 1/2, 1, 3, 12 x], {x, 0, n}] (* Michael Somos, Nov 25 2013 *)

{a(n) = if( n<0, 0, 2 * 3^n * (2*n)! / (n! * (n+2)!))}; /* Michael Somos, Nov 25 2013 */

G.f. A(z) satisfies A(z) = 1 - 16*z + 18*z*A(z) - 27*z^2*A(z)^2.
G.f.: F(1/2,1;3;12x). - Paul Barry, Feb 04 2009
a(n) = 2*3^n*A000108(n)/(n+2). - Paul Barry, Feb 04 2009
D-finite with recurrence: (n + 1) a(n) = (12 n - 18) a(n - 1). - Simon Plouffe, Feb 09 2012
G.f.: 1/54*(-1+18*x+(-(12*x-1)^3)^(1/2))/x^2. - Simon Plouffe, Feb 09 2012
0 = a(n)*(+144*a(n+1) - 42*a(n+2)) + a(n+1)*(+18*a(n+1) + a(n+2)) if n>=0. - Michael Somos, Jan 31 2014
a(n) ~ 2*(12^n)/((n^2+3*n)*sqrt(Pi*n)). - Peter Luschny, Nov 25 2015
E.g.f.: exp(6*x)*(12*x*BesselI(0,6*x) - (1 + 12*x)*BesselI(1,6*x))/(9*x). - Ilya Gutkovskiy, Feb 01 2017
From Amiram Eldar, Jan 08 2023: (Start)
Sum_{n>=0} 1/a(n) = 1887/1331 + 3240*arccosec(2*sqrt(3))/(1331*sqrt(11)).
Sum_{n>=0} (-1)^n/a(n) = 1563/2197 - 3240*arccosech(2*sqrt(3))/(2197*sqrt(13)). (End)

More terms from Joerg Arndt, Feb 26 2014

A005411 Number of non-vanishing Feynman diagrams of order 2n for the electron or the photon propagators in quantum electrodynamics.

Original entry on oeis.org

1, 1, 4, 25, 208, 2146, 26368, 375733, 6092032, 110769550, 2232792064, 49426061818, 1192151302144, 31123028996164, 874428204384256, 26308967412122125, 843984969276915712, 28757604639850111894, 1037239628039528906752, 39481325230750749160462

Offset: 0

N. J. A. Sloane

Cvitanovic et al. paper relates this sequence to A000698 and A005413. - Robert Munafo, Jan 24 2010
(x + 4x^2 + 25x^3 + 208x^4 + ...) = (x + 2x^2 + 7x^3 + 38x^4 + ...) * 1/(1 + x + 2x^2 + 7x^3 + 38x^4 + ...); where A094664 = (1, 1, 2, 7, 38, 286, ...). - Gary W. Adamson, Nov 16 2011.
The Martin and Kearney article has S(2,-4,1) = [1,1,4,25,...] where u_1 = u_2 = 1, u_3 = 4, u_4 =25, etc. This is almost the same as this sequence. - Michael Somos, Feb 27 2014
From Robert Coquereaux, Sep 05 2014: (Start)
Evaluation of quantum electrodynamics functional integrals in dimension 0 become usual Lebesgue integrals, their Taylor expansion around g=0 at order n give the number of Feynman diagrams.
These are graphs with two kinds of edges: a (non-oriented), f (oriented), and only one kind of vertex: aff.
Electron propagator: all the diagrams with two external edges of type f.
Photon propagator: all the diagrams with two external edges of type a.
The exponent n of g^n gives the number of vertices.
Diagrams containing loops of type f with an odd number of vertices are set to 0 (vanishing diagrams).
The coefficients of the series S(g)=Sum a(n) g^(2n) give the number of non-vanishing Feynman diagrams for the electron (or the photon) propagator.
S(g) is obtained as < 1/(1-g^2 a^2) > for the measure (E^(-(a^2/2)))/sqrt[1-g^2 a^2]da, assuming g^2 < 0, hence a formula for S(g) in terms of modified Bessel functions (setting x=g^2 gives the G.f. below).
(End)
Sum over all Dyck paths of semilength n of products over all peaks p of x_p/y_p, where x_p and y_p are the coordinates of peak p. a(3) = 3/3 +2/2*5/1 +1/1*4/2 +2/2*4/2 +1/1*3/1*5/1 = 25. - Alois P. Heinz, May 21 2015
From Sasha Kolpakov, Dec 11 2017: (Start)
Number of free index 2n subgroups in the free product Z_2*Z_2*Z_2.
Number of oriented rooted pavings (after Arques & Koch, Spehner, Lienhardt) with 2n darts.
(End)

			G.f. = 1 + x + 4*x^2 + 25*x^3 + 208*x^4 + 2146*x^5 + 26368*x^6 + 375733*x^7 + ... [Deleted g.f. restored by _N. J. A. Sloane_, Jan 30 2016]

C. Itzykson and J.-B. Zuber, Quantum Field Theory, McGraw-Hill, 1980, pages 466-467.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..400
Michael Borinsky, Renormalized asymptotic enumeration of Feynman diagrams, arXiv:1703.00840 [hep-th], 2017.
Rémi Bottinelli, Laura Ciobanu, and Alexander Kolpakov, Three-dimensional maps and subgroup growth, manuscripta math. (2021).
L. Ciobanu and A. Kolpakov, Three-dimensional maps and subgroup growth, arXiv:1712.01418 [math.GR], 2017.
P. Cvitanovic, B. Lautrup and R. B. Pearson, The number and weights of Feynman diagrams, Phys. Rev. D18, (1978), 1939-1949. DOI:10.1103/PhysRevD.18.1939
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, arXiv:1103.4936 [math.CO], 2011.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. see p. 294.
A. N. Stokes, Continued fraction solutions of the Riccati equation, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.
Wikipedia, Feynman diagram

Cf. A000108, A000698, A005412, A005413, A094664.

Column k=0 of A258219, A258220.

b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, false)*`if`(t, x/y, 1) +
                   b(x-1, y+1, true)  ))
    end:
a:= n-> b(2*n, 0, false):
seq(a(n), n=0..20);  # Alois P. Heinz, May 21 2015

a[n_] := Module[{A}, A[1] = 1; A[k_] := A[k] = (2*k-4)*A[k-1]+Sum[A[j]*A[k-j], {j, 1, k-1}]; A[n]]; Table[a[n], {n, 2, 20}] (* Jean-François Alcover, Feb 27 2014, after Michael Somos *)
a[ n_] := Module[{m = n + 1, u}, If[ n < 2, Boole[n >= 0], u = Range[m]; Do[ u[[k]] = (2 k - 4) u[[k - 1]] + Sum[ u[[j]] u[[k - j]], {j, k - 1}], {k, 2, m}]; u[[m]]]]; (* Michael Somos, Feb 27 2014 *)
a[n_]:=SeriesCoefficient[(1-BesselK[1,-(1/(4 g^2))]/BesselK[0,-(1/(4 g^2))])/(2 g^2),{g,0,2*n}]; (* Robert Coquereaux, Sep 05 2014 *)

{a(n) = my(A); if( n<1, n==0, n++; A = vector(n); A[1] = 1; for( k=2, n, A[k] = (2 * k - 4) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 24 2011 */

From Peter Bala, Mar 07 2011: (Start)
Given the o.g.f. A(x), the function F(x) := A(x^2) satisfies the differential equation F(x) = 1 + x^3*d/dx(F(x)) + x^2*F(x)^2 (equation 3.53, P. Cvitanovic et al.).
Conjectural o.g.f. A(x) as a continued fraction:
1 + x/(1 - 4*x - 3^2*x^2/(1 - 8*x - 5^2*x^2/(1 - 12*x - 7^2*x^2/(1 - 16*x - ...)))).
Asymptotics: a(n) ~ 1/Pi*2^(n+1)*n!*(1 - 1/(2*n) - 3/(8*n^2)). (End)
Given u(1) = 1, u(n) = (2*n - 4) * u(n-1) + Sum_{k=1..n-1} u(k) * u(n-k) when n>1, then a(n) = u(n+1) if n>0. - Michael Somos, Jul 24 2011
G.f.: 1/Q(0) where Q(k) = 1 - x*(2*k+1)/(1 - x*(2*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013
G.f.: 1/x^2 - 1/x - Q(0)/x^2, where Q(k) = 1 - x*(2*k+1)/(1 - x*(2*k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 20 2013
G.f.: 1/x^2 - 1/x - G(0)/(2*x^2), where G(k) = 1 + 1/(1 - 2*x*(2*k+1)/(2*x*(2*k+1) - 1 + 2*x*(2*k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 29 2013
G.f.: W(0)/x - 1/x, where W(k) = 1 - x*(2*k+1)/( x*(2*k+1) - 1/(1 - x*(2*k+3)/( x*(2*k+3) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
G.f.: G(0)/x -1/x, where G(k) = 1 - x*(2*k+1)/(x - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jan 21 2014
G.f.: 1/(2*x) - BesselK(1,-1/(4*x))/(2*x*BesselK(0,-1/(4*x))) where BesselK[p,z] denotes the modified Bessel function of the second kind (order p, argument z). This is a small improvement of a result obtained in 1980 book "Quantum Field Theory". - Robert Coquereaux, Sep 05 2014
Asymptotics: a(n) ~ 2*(2/Pi)^(1/2)*(2/e)^n*n^(n+1/2), cf. Ciobanu and Kolpakov in Links. - Sasha Kolpakov, Dec 11 2017
From Peter Bala, Jun 27 2022: (Start)
O.g.f. as a continued fraction of Stieltjes type: A(x) = 1/(1 - x/(1 - 3*x/(1 - 3*x/(1 - 5*x/(1 - 5*x/(1 - 7*x/(1 - 7*x/(1 - ...)))))))) follows by applying the result of Stokes to the Riccati differential equation 2*x^2*A'(x) = -1 + A(x) - x*A^2(x).
The even part of the continued fraction gives A(x) = 1/(1 - x - 3*x^2/(1 - 6*x - 15*x^2/(1 - 10*x - 35*x^2/(1 - 14*x - 63*x^2/(1 - 18*x - ... - (4*n^2-1)*x^2/(1 - (4*n+2)*x -...)))))), a continued fraction of Jacobi type (a J-fraction). (End)

Name corrected by Charles R Greathouse IV, Jan 24 2014
Name clarified by Robert Coquereaux, Sep 05 2014
a(0)=1 prepended, programs and formulas edited by Alois P. Heinz, Jun 22 2015

A062980 a(0) = 1, a(1) = 5; for n > 1, a(n) = 6na(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1).

Original entry on oeis.org

1, 5, 60, 1105, 27120, 828250, 30220800, 1282031525, 61999046400, 3366961243750, 202903221120000, 13437880555850250, 970217083619328000, 75849500508999712500, 6383483988812390400000, 575440151532675686278125, 55318762960656722780160000

Offset: 0

Michael Praehofer (praehofer(AT)ma.tum.de), Jul 24 2001

Number of rooted unlabeled connected triangular maps on a compact closed oriented surface with 2n faces (and thus 3n edges). [Vidal]
Equivalently, the number of pair of permutations (sigma,tau) up to simultaneous conjugacy on a pointed set of size 6*n with sigma^3=tau^2=1, acting transitively and with no fixed point. [Vidal]
Also, the asymptotic expansion of the Airy function Ai'(x)/Ai(x) = -sqrt(x) - 1/(4x) + Sum_{n>=2} (-1)^n a(n) (4x)^ (1/2-3n/2). [Praehofer]
Maple 6 gives the wrong asymptotics of Ai'(x)=AiryAi(1,x) as x->oo apart from the 3rd term. Therefore asympt(AiryAi(1,x/4)/AiryAi(x/4),x); reproduces only the value a(1)=1 correctly.
Number of closed linear lambda terms (see [Bodini, Gardy, Jacquot, 2013] and [N. Zeilberger, 2015] references). - Pierre Lescanne, Feb 26 2017
Proved (bijection) by O. Bodini, D. Gardy, A. Jacquot (2013). - Olivier Bodini, Mar 30 2018
The September 2018 talk by Noam Zeilberger (see link to video) connects three topics (planar maps, Tamari lattices, lambda calculus) and eight sequences: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827. - N. J. A. Sloane, Sep 17 2018

			1 + 5*x + 60*x^2 + 1105*x^3 + 27120*x^4 + 828250*x^5 + 30220800*x^6 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..100
O. Bodini, D. Gardy, and A. Jacquot, Asymptotics and random sampling for BCI and BCK lambda terms, Theor. Comput. Sci. 502: 227-238 (2013).
Jørgen Ellegaard Andersen, Gaëtan Borot, Leonid O. Chekhov and Nicolas Orantin, The ABCD of topological recursion, arXiv:1703.03307 [math-ph], 2017. [See Appendix A.1]
Laura Ciobanu and Alexander Kolpakov, Free subgroups of free products and combinatorial hypermaps, arXiv:1708.03842 [math.CO], 2017.
P. Cvitanovic, B. Lautrup and R. B. Pearson, The number and weights of Feynman diagrams, Phys. Rev. D18, (1978), 1939-1949, (eq 3.14 and fig 1b). DOI:10.1103/PhysRevD.18.1939
Bertrand Eynard, Topological expansion for the 1-hermitian matrix model correlation functions, Journal of High Energy Physics 11 (2004). [See Eq. (5.12) and Appendix A]
Steven R. Finch, Shapes of binary trees, June 24, 2004. [Cached copy, with permission of the author]
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 2024.
Éric Fusy, Luca Lionni, Adrian Tanasa, Combinatorial study of graphs arising from the Sachdev-Ye-Kitaev model, arXiv:1810.02146 [math.CO], 2018.
Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
Kristian Gustavsson and Bernhard Mehlig, Statistical models for spatial patterns of heavy particles in turbulence, arxiv:1412.4374 [physics.flu-dyn], 2014-2016. [See Figure 14]
M. J. Kearny and R. J. Martin, Normalized functionals of first passage Brownian motion and a curious connection with the maximal relative height of fluctuating interfaces, J. Phys. A, Math. Theor. 49, No. 19, Article ID 195001, 20 p. (2016).
George Kaye, A visualiser for linear lambda-terms as 3-valent rooted maps, University of Birmingham (UK, 2019).
S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (2003) 337-358.
Michael J. Kearney, Satya N. Majumdar and Richard J. Martin, The first-passage area for drifted Brownian motion and the moments of the Airy distribution, arXiv:0706.2038 [cond-mat.stat-mech], 2007. [a(n) = 8^n * K_n from Eq. (3)]
Pierre Lescanne, Quantitative aspects of linear and affine closed lambda terms, arXiv:1702.03085 [cs.DM], 2017. Also in ACM Transactions on Computational Logic (TOCL 2019), Vol. 19, No. 2, Article No. 9.
R. J. Martin and M. J. Kearney, An exactly solvable self-convolutive recurrence, Aequat. Math., 80 (2010), 291-318. See p. 292.
NIST Digital Library of Mathematical Functions, Airy Functions.
A. N. Stokes, Continued fraction solutions of the Riccati equation, Bull. Austral. Math. Soc. Vol. 25 (1982), 207-214.
Paul Tarau and Valeria de Paiva, Deriving Theorems in Implicational Linear Logic, Declaratively, arXiv:2009.10241 [cs.LO], 2020. See also Github, (2020).
Samuel Vidal and Michel Petitot, Counting Rooted and Unrooted Triangular Maps, Journal of Nonlinear Systems and Applications (2009) 151-154.
Eric Weisstein's World of Mathematics, Airy Functions, contains the definitions of Ai(x), Bi(x).
Noam Zeilberger, Counting isomorphism classes of beta-normal linear lambda terms, arXiv:1509.07596 [cs.LO], 2015.
Noam Zeilberger, Linear lambda terms as invariants of rooted trivalent maps, arXiv preprint arXiv:1512.06751 [cs.LO], 2015.
Noam Zeilberger, A theory of linear typings as flows on 3-valent graphs, arXiv:1804.10540 [cs.LO], 2018.
Noam Zeilberger, A Sequent Calculus for a Semi-Associative Law, arXiv preprint 1803.10030 [math.LO], March 2018 (A revised version of a 2017 conference paper).
Noam Zeilberger, A proof-theoretic analysis of the rotation lattice of binary trees, Part 1 (video), Part 2, Rutgers Experimental Math Seminar, Sep 13 2018.
Noam Zeilberger and Alain Giorgetti, A correspondence between rooted planar maps and normal planar lambda terms, arXiv:1408.5028 [cs.LO], 2014-2015; Logical Methods in Computer Science, vol. 11 (3:22), 2015, pp. 1-39.

Sequences mentioned in the Noam Zeilberger 2018 video: A000168, A000260, A000309, A000698, A000699, A002005, A062980, A267827.
With interspersed zeros column 3 of A380622.
Pointed version of A129114.
Connected pointed version of A129115.
Cf. A060506, A060507, A094199, A121350, A121352, A005133, A172455.

a062980 n = a062980_list !! n
a062980_list = 1 : 5 : f 2 [5,1] where
   f u vs'@(v:vs) = w : f (u + 1) (w : vs') where
     w = 6 * u * v + sum (zipWith (*) vs_ $ reverse vs_)
     vs_ = init vs
-- Reinhard Zumkeller, Jun 03 2013

a:= proc(n) option remember; `if`(n<2, 4*n+1,
      6*n*a(n-1) +add(a(k)*a(n-k-1), k=1..n-2))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Mar 31 2017

max = 16; f[y_] := -Sqrt[x] - 1/(4*x) + Sum[(-1)^n*a[n]*(4*x)^(1/2 - 3*(n/2)), {n, 2, max}] /. x -> 1/y^2; s[y_] := Normal[ Series[ AiryAiPrime[x] / AiryAi[x], {x, Infinity, max + 7}]] /. x -> 1/y^2; sol = SolveAlways[ Simplify[ f[y] == s[y], y > 0], y] // First; Join[{1, 5}, Table[a[n], {n, 3, max}] /. sol] (* Jean-François Alcover, Oct 09 2012, from Airy function asymptotics *)
a[0] = 1; a[n_] := a[n] = (6*(n-1)+4)*a[n-1] + Sum[a[i]*a[n-i-1], {i, 0, n-1}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Nov 29 2013, after Vladimir Reshetnikov *)

{a(n) = local(A); n++; if( n<1, 0, A = vector(n); A[1] = 1; for( k=2, n, A[k] = (6*k - 8) * A[k-1] + sum( j=1, k-1, A[j] * A[k-j])); A[n])} /* Michael Somos, Jul 24 2011 */

from sympy.core.cache import cacheit
@cacheit
def a(n): return n*4 + 1 if n<2 else 6*n*a(n - 1) + sum(a(k)*a(n - k - 1) for k in range(1, n - 1))
print([a(n) for n in range(21)]) # Indranil Ghosh, Aug 09 2017

With offset 1, then a(1) = 1 and, for n > 1, a(n) = (6*n-8)*a(n-1) + Sum_{k=1..n-1} a(k)*a(n-k) [Praehofer] [Martin and Kearney].
a(n) = (6/Pi^2)*Integral_{x=0..oo} ((4*x)^(3*n/2)/(Ai(x)^2 + Bi(x)^2)) dt. - Vladimir Reshetnikov, Sep 24 2013
a(n) ~ 3 * 6^n * n! / Pi. - Vaclav Kotesovec, Jan 19 2015
0 = 6*x^2*y' + x*y^2 + (4*x-1)*y + 1, where y(x) = Sum_{n>=0} a(n)*x^n. - Gheorghe Coserea, Apr 02 2017
From Peter Bala, May 21 2017: (Start)
G.f. as an S-fraction: A(x) = 1/(1 - 5*x/(1 - 7*x/(1 - 11*x/(1 - 13*x/(1 - ... - (6*n - 1)*x/(1 - (6*n + 1)*x/(1 - .... See Stokes.
x*A(x) = B(x)/(1 + 2*B(x)), where B(x) = x + 7*x^2 + 84*x^3 + 1463*x^4 + ... is the o.g.f. of A172455.
A(x) = 1/(1 + 2*x - 7*x/(1 - 5*x/(1 - 13*x/(1 - 11*x/(1 - ... - (6*n + 1)*x/(1 - (6*n - 1)*x/(1 - .... (End)

Entry revised by N. J. A. Sloane based on comments from Samuel A. Vidal, Mar 30 2007

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A088221 Coefficient of x^n in g.f.^n is A000698(n+1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A046863 Erroneous version of A000698.

Views

Author

Keywords

Links

A001147 Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Sage

Formula

Extensions

A003319 Number of connected permutations of [1..n] (those not fixing [1..j] for 0 < j < n). Also called indecomposable permutations, or irreducible permutations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A000699 Number of irreducible chord diagrams with 2n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

A001147 Double factorial of odd numbers: a(n) = (2n-1)!! = 135...(2n-1).

A000168 a(n) = 23^n(2n)!/(n!(n+2)!).

A062980 a(0) = 1, a(1) = 5; for n > 1, a(n) = 6na(n-1) + Sum_{k=1..n-2} a(k)*a(n-k-1).