cp's OEIS Frontend

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

Consider the set of n-1 odd numbers from 3 to 2n-1, i.e., {3, 5, ..., 2n-1}. There are 2^(n-1) subsets from {} to {3, 5, 7, ..., 2n-1}; a(n) = the sum of the products of terms of all the subsets. (Product for empty set = 1.) a(4) = 1 + 3 + 5 + 7 + 3*5 + 3*7 + 5*7 + 3*5*7 = 192. - Amarnath Murthy, Sep 06 2002

Also, a(n-1) is the number of ways to lace a shoe that has n pairs of eyelets such that there is a straight (horizontal) connection between all adjacent eyelet pairs. - Hugo Pfoertner, Jan 27 2003

This is also the denominator of the integral of ((1-x^2)^(n-1/2))/(Pi/4) where x ranges from 0 to 1. The numerator is (2*x)!/(x!*2^x). In both cases n starts at 1. E.g., the denominator when n=3 is 24 and the numerator is 15. - Al Hakanson (hawkuu(AT)excite.com), Oct 17 2003

Number of ways to use the elements of {1,...,n} once each to form a sequence of nonempty lists. - Bob Proctor, Apr 18 2005

Row sums of A131222. - Paul Barry, Jun 18 2007

Number of rotational symmetries of an n-cube. The number of all symmetries of an n-cube is A000165. See Egan for signed cycle notation, other notes, tables and animation. - Jonathan Vos Post, Nov 28 2007

1, 4, 24, 192, 1920, ... is the exponential (or binomial) convolution of 1, 1, 3, 15, 105, ... and 1, 3, 15, 105, 945 (A001147). - David Callan, Jul 25 2008

The n-th term of this sequence is the number of regions into which n-dimensional space is partitioned by the 2n hyperplanes of the form x_i=x_j and x_i=-x_j (for 1 <= i < j <= n). - Edward Scheinerman (ers(AT)jhu.edu), May 04 2008

a(n) is the number of ways to seat n churchgoers into pews and then linearly order the nonempty pews. - Geoffrey Critzer, Mar 16 2009

Equals the row sums of A156992. - Geoffrey Critzer, Mar 05 2010

From Gary W. Adamson, May 17 2010: (Start)

Next term in the series = (1, 3, 5, 7, ...) dot (1, 1, 4, 24, ...);

e.g., a(5) = 1920 = (1, 3, 5, 7, 9) dot (1, 1, 4, 24, 192) = (1 + 3 + 20 + 168 + 1728). (End)

a(n) is the number of ways to represent the permutations of {1,2,...,n} in cycle notation, taking into account that we can permute the order of all cycles and also have k ways to write a length-k cycle.

For positive n, a(n) equals the permanent of the n X n matrix with consecutive integers 1 to n along the main diagonal, consecutive integers 2 to n along the subdiagonal, and 1's everywhere else. - John M. Campbell, Jul 10 2011

From Dennis P. Walsh, Nov 26 2011: (Start)

Number of ways to arrange n books on consecutive bookshelves.

To derive a(n) = n!2^(n-1), we note that there are n! ways to arrange the books in a row. Then there are 2^(n-1) ways to place the arranged books on consecutive shelves since there are 2^(n-1) ordered partitions of n. Hence a(n) = n!2^(n-1).

Also, a(n) is the number of ways to stack n different alphabet blocks in contiguous stacks.

Furthermore, a(n) is the number of labeled, rooted forests that have (i) each root labeled larger than any nonroot, (ii) each root having exactly one child node, (iii) n non-root nodes, and (iv) each node in the forest with at most one child node.

Example: a(3)=24 since there are 24 arrangements of books b1, b2, and b3 on consecutive shelves, namely, |b1 b2 b3|, |b1 b3 b2|, |b2 b1 b3|, |b2 b3 b1|, |b3 b1 b2|, |b3 b2 b1|, |b1 b2||b3|, |b2 b1| |b3|, |b1 b3||b2|, |b3 b1||b2|, |b2 b3||b1|, |b3 b2||b1|, |b1||b2 b3|,|b1||b3 b2|, |b2||b1 b3|, |b2||b3 b1|, |b3||b1 b2|, |b3||b2 b1|, |b1||b2||b3|, |b1||b3||b2|, |b2||b1||b3|, |b2||b3||b1|, |b3||b1||b2|, and |b3||b2||b1|.

(End)

For n > 3, a(n) is the order of the Coxeter group (also called Weyl group) of type D_n. - Tom Edgar, Nov 05 2013

To derive a(n), we note that there are n! ways to arrange n books in a row and there are binomial(n-1,2) ways to place the n arranged books on 3 consecutive shelves (since binomial(n-1,2) is the number of compositions of n with 3 summands). Hence a(n) = n!*binomial(n-1,2) for n >= 3.

The number of ways to arrange n books on two nonempty bookshelves is given by A062119(n).

To derive a(n) = n!*binomial(n-1,3), we note that there are n! ways to arrange the books in a row.

Then there are binomial(n-1,3) ways to place the arranged books on 4 consecutive shelves since there are binomial(n-1,3) compositions of n with 4 summands. Hence a(n) = n!*binomial(n-1,4).

We note that a(n) is the fourth column of triangle A156992, the number of ways to arrange n books on k consecutice bookshelves, leaving no shelves empty.