cp's OEIS Frontend

Compare to the o.g.f. of row n, E2(x,n), in the second-order Eulerian triangle A008517:

E2(x,n) = (1-x)^(2*n+1) * Sum_{k>=0} k^n * k^k * exp(-k*x) * x^k/k!.

See A004301 for the doubled sequence.

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

The indexing used here follows that given in the classic books by Riordan and Comtet. For two other versions see A173018 and A123125. - N. J. A. Sloane, Nov 21 2010

Coefficients of Eulerian polynomials. Number of permutations of n objects with k-1 rises. Number of increasing rooted trees with n+1 nodes and k leaves.

T(n,k) = number of permutations of [n] with k runs. T(n,k) = number of permutations of [n] requiring k readings (see the Knuth reference). T(n,k) = number of permutations of [n] having k distinct entries in its inversion table. - Emeric Deutsch, Jun 09 2004

T(n,k) = number of ways to write the Coxeter element s_{e1}s_{e1-e2}s_{e2-e3}s_{e3-e4}...s_{e_{n-1}-e_n} of the reflection group of type B_n, using s_{e_k} and as few reflections of the form s_{e_i+e_j}, where i = 1, 2, ..., n and j is not equal to i, as possible. - Pramook Khungurn (pramook(AT)mit.edu), Jul 07 2004

Subtriangle for k>=1 and n>=1 of triangle A123125. - Philippe Deléham, Oct 22 2006

T(n,k)/n! also represents the n-dimensional volume of the portion of the n-dimensional hypercube cut by the (n-1)-dimensional hyperplanes x_1 + x_2 + ... x_n = k, x_1 + x_2 + ... x_n = k-1; or, equivalently, it represents the probability that the sum of n independent random variables with uniform distribution between 0 and 1 is between k-1 and k. - Stefano Zunino, Oct 25 2006

[E(.,t)/(1-t)]^n = n!*Lag[n,-P(.,t)/(1-t)] and [-P(.,t)/(1-t)]^n = n!*Lag[n, E(.,t)/(1-t)] umbrally comprise a combinatorial Laguerre transform pair, where E(n,t) are the Eulerian polynomials and P(n,t) are the polynomials in A131758. - Tom Copeland, Sep 30 2007

From Tom Copeland, Oct 07 2008: (Start)

G(x,t) = 1/(1 + (1-exp(x*t))/t) = 1 + 1*x + (2+t)*x^2/2! + (6+6*t+t^2)*x^3/3! + ... gives row polynomials for A090582, the reverse f-polynomials for the permutohedra (see A019538).

G(x,t-1) = 1 + 1*x + (1+t)*x^2/2! + (1+4*t+t^2)*x^3/3! + ... gives row polynomials for A008292, the h-polynomials for permutohedra (Postnikov et al.).

G((t+1)*x, -1/(t+1)) = 1 + (1+t)*x + (1+3*t+2*t^2)*x^2/2! + ... gives row polynomials for A028246.

(End)

A subexceedant function f on [n] is a map f:[n] -> [n] such that 1 <= f(i) <= i for all i, 1 <= i <= n. T(n,k) equals the number of subexceedant functions f of [n] such that the image of f has cardinality k [Mantaci & Rakotondrajao]. Example T(3,2) = 4: if we identify a subexceedant function f with the word f(1)f(2)...f(n) then the subexceedant functions on [3] are 111, 112, 113, 121, 122 and 123 and four of these functions have an image set of cardinality 2. - Peter Bala, Oct 21 2008

Further to the comments of Tom Copeland above, the n-th row of this triangle is the h-vector of the simplicial complex dual to a permutohedron of type A_(n-1). The corresponding f-vectors are the rows of A019538. For example, 1 + 4*x + x^2 = y^2 + 6*y + 6 and 1 + 11*x + 11*x^2 + x^3 = y^3 + 14*y^2 + 36*y + 24, where x = y + 1, give [1,6,6] and [1,14,36,24] as the third and fourth rows of A019538. The Hilbert transform of this triangle (see A145905 for the definition) is A047969. See A060187 for the triangle of Eulerian numbers of type B (the h-vectors of the simplicial complexes dual to permutohedra of type B). See A066094 for the array of h-vectors of type D. For tables of restricted Eulerian numbers see A144696 - A144699. - Peter Bala, Oct 26 2008

For a natural refinement of A008292 with connections to compositional inversion and iterated derivatives, see A145271. - Tom Copeland, Nov 06 2008

The polynomials E(z,n) = numerator(Sum_{k>=1} (-1)^(n+1)*k^n*z^(k-1)) for n >=1 lead directly to the triangle of Eulerian numbers. - Johannes W. Meijer, May 24 2009

From Walther Janous (walther.janous(AT)tirol.com), Nov 01 2009: (Start)

The (Eulerian) polynomials e(n,x) = Sum_{k=0..n-1} T(n,k+1)*x^k turn out to be also the numerators of the closed-form expressions of the infinite sums:

S(p,x) = Sum_{j>=0} (j+1)^p*x^j, that is

S(p,x) = e(p,x)/(1-x)^(p+1), whenever |x| < 1 and p is a positive integer.

(Note the inconsistent use of T(n,k) in the section listing the formula section. I adhere tacitly to the first one.) (End)

If n is an odd prime, then all numbers of the (n-2)-th and (n-1)-th rows are in the progression k*n+1. - Vladimir Shevelev, Jul 01 2011

The Eulerian triangle is an element of the formula for the r-th successive summation of Sum_{k=1..n} k^j which appears to be Sum_{k=1..n} T(j,k-1) * binomial(j-k+n+r, j+r). - Gary Detlefs, Nov 11 2011

Li and Wong show that T(n,k) counts the combinatorially inequivalent star polygons with n+1 vertices and sum of angles (2*k-n-1)*Pi. An equivalent formulation is: define the total sign change S(p) of a permutation p in the symmetric group S_n to be equal to Sum_{i=1..n} sign(p(i)-p(i+1)), where we take p(n+1) = p(1). T(n,k) gives the number of permutations q in S_(n+1) with q(1) = 1 and S(q) = 2*k-n-1. For example, T(3,2) = 4 since in S_4 the permutations (1243), (1324), (1342) and (1423) have total sign change 0. - Peter Bala, Dec 27 2011

Xiong, Hall and Tsao refer to Riordan and mention that a traditional Eulerian number A(n,k) is the number of permutations of (1,2...n) with k weak exceedances. - Susanne Wienand, Aug 25 2014

Connections to algebraic geometry/topology and characteristic classes are discussed in the Buchstaber and Bunkova, the Copeland, the Hirzebruch, the Lenart and Zainoulline, the Losev and Manin, and the Sheppeard links; to the Grassmannian, in the Copeland, the Farber and Postnikov, the Sheppeard, and the Williams links; and to compositional inversion and differential operators, in the Copeland and the Parker links. - Tom Copeland, Oct 20 2015

The bivariate e.g.f. noted in the formulas is related to multiplying edges in certain graphs discussed in the Aluffi-Marcolli link. See p. 42. - Tom Copeland, Dec 18 2016

Distribution of left children in treeshelves is given by a shift of the Eulerian numbers. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link. See A278677, A278678 or A278679 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016

The row polynomial P(n, x) = Sum_{k=1..n} T(n, k)*x^k appears in the numerator of the o.g.f. G(n, x) = Sum_{m>=0} S(n, m)*x^m with S(n, m) = Sum_{j=0..m} j^n for n >= 1 as G(n, x) = Sum_{k=1..n} P(n, x)/(1 - x)^(n+2) for n >= 0 (with 0^0=1). See also triangle A131689 with a Mar 31 2017 comment for a rewritten form. For the e.g.f see A028246 with a Mar 13 2017 comment. - Wolfdieter Lang, Mar 31 2017

For relations to Ehrhart polynomials, volumes of polytopes, polylogarithms, the Todd operator, and other special functions, polynomials, and sequences, see A131758 and the references therein. - Tom Copeland, Jun 20 2017

For relations to values of the Riemann zeta function at integral arguments, see A131758 and the Dupont reference. - Tom Copeland, Mar 19 2018

Normalized volumes of the hypersimplices, attributed to Laplace. (Cf. the De Loera et al. reference, p. 327.) - Tom Copeland, Jun 25 2018