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

A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).

exp(x*(1-y+y^2)*D_y)*f(y)|_{y=0} = f(1-E(-x)) for any function f with a Taylor series. D_y means differentiation with respect to y and E(x) is the e.g.f. given below. For a proof of exp(x*g(y)*D_y)*f(y) = f(F^{-1}(x+F(y))) with the compositional inverse F^{-1} of F(y)=int(1/g(y),y) with F(0)=0 see, e.g., the Datolli et al. reference.

Number of increasing ordered trees on vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2. - David Callan, Mar 30 2007

Number of increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2. - Wenjin Woan, May 21 2011

Define a sequence of polynomials P(n,x) by means of the recurrence relation

(1)... P(n+1,x) = x*{P(n,x-1)-P(n,x)+P(n,x+1)}

with starting value P(0,x) = 1. The first few polynomials are

P(1,x) = x

P(2,x) = x^2

P(3,x) = x*(x^2+2),

P(4,x) = x^2*(x^2+8),

P(5,x) = x*(x^4+20*x^2+18).

This triangle lists the coefficients of these polynomials in ascending powers of x. The triangle has links with A080635, which gives the number of ordered increasing 0-1-2 trees on n nodes (plane unary-binary trees in the notation of [BERGERON et al.]). The number of forests of k such trees on n nodes is given by the formula

... 1/k!*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).

See A185422.

We also have A080635(n) = P(n,1), which can be used to calculate the terms of A080635 - see A185416.

For similarly defined polynomial sequences for other families of trees see A147309 and A185419. See also A185417.

Exponential Riordan array [(3/2)*(1-sqrt(3)*tan((Pi+3*sqrt(3)*x)/6))/(-1+2*sin((Pi-6*sqrt(3)*x)/6)), log((1/2)*(1+sqrt(3)*tan(sqrt(3)*x/2+Pi/6)))]. Production matrix is the exponential Riordan array [2*cosh(x)-1,x] beheaded. A185422*A008277^{-1}.

An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing.

A080635 enumerates increasing plane (ordered) unary-binary trees with n nodes labeled from the set {1,2,...n}. The entry T(n,k) of the present table counts forests of k increasing plane unary-binary trees having n nodes in total. See below for an example.

The Stirling number of the second kind Stirling2(n,k) counts the partitions of the set [n] set into k blocks. Arranging the elements in each block in ascending numerical order provides an alternative combinatorial interpretation for Stirling2(n,k) as counting forests of k increasing unary trees on n nodes. Thus we may view the present array as generalized Stirling numbers of the second kind (associated with A080635 or with the polynomials P(n,x) of A185415 - see formulas (1) and (2) below).

For a table of ordered forests of increasing plane unary-binary trees see A185423. For the enumeration of forests and ordered forests in the non-plane case see A147315 and A185421.

The Bell transform of A080635(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing. A000111(n) for n >= 0 enumerates increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2 (plane unary binary trees in the notation of [Bergeron et al.]).

The entry T(n,k) of the present table counts ordered forests of k such trees having n nodes in total. See below for an example. For unordered forests see A147315. For a table of ordered forests of increasing ordered trees in which all outdegrees are <=2 see A185423.