2,1

A big descent in a permutation (x_1,x_2,...,x_n) is a position i such that x_i - x_(i+1) >= 2. T(n,k) is the number of permutations on [n] with k big descents. The mean number of big descents in permutations on [n] is (n-1)(n-2)/(2n). For S(n,k):=number of permutations on [n] with k small descents, that is, indices i such that x_i - x_(i+1) = 1, the gf Sum_{n>=0,k>=0}S(n+1,k) x^n/n! y^k is 1/(E^(x(1 - y))*(1 - x)^2).

T(n,k) is also the number of recursive trees with n+1 vertices and k+2 leaves. (A recursive tree on n vertices is a rooted tree with the vertices labeled 1, 2, ... n, such that the root is labeled 1 and every path starting at the root is increasing with respect to the labels.) - Taral Guldahl Seierstad (seiersta(AT)informatik.hu-berlin.de), Oct 12 2006

In the comment by T. G. Seierstad, the term "leaf" means "vertex incident with exactly one edge." Thus if the root has only one child, the root is a leaf. T(n,k) is the number of trees rooted at 0 on vertex set {0,1,2,...,n} that contain k+1 leaves (here a leaf is a vertex with no children) and such that, for i = 0,1,...,n-1, there is exactly one vertex larger than i incident with i. For example, T(3,0) = 4 counts {0->1->2->3}, {0->1->3->2}, {0->2->3->1}, {0->3->2->1} and T(3,1) = 2 counts {0->2->1,2->3}, {0->3->1,3->2} (the arrows indicate edges directed away from the root). - David Callan (callan(AT)stat.wisc.edu), Feb 01 2007

Contribution from Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008: (Start)

If we divide the entries of this array by 2 and then read the rows in reverse order we obtain the array of 2-restricted Eulerian numbers A144696.

Two equivalent interpretations of this array are:

A) Define a permutation p in the symmetric group S_n to have an r-excedance at position i, 1 <= i <= n-1, if p(i) >= i+r. This array gives the number of permutations in the symmetric group S_n having k 2-excedances (see the last chapter of [Riordan]). For example, in the symmetric group S_3, the two permutations (3,1,2) and (3,2,1) have a single 2-excedance, while the remaining four permutations have no 2-excedances. Hence T(3,0) = 4 and T(3,1) = 2. The triangle of Eulerian numbers A008292 enumerates permutations by 1-excedances (with an offset of 1 in the column indexing).

B) T(n,k) gives the number of permutations in the group S_(n+1) starting with a 2 and having k+1 descents [Conger]. For example, in the symmetric group S_4, the permutations (2,1,4,3) and (2,4,3,1) start with a 2 and have two descents so T(3,1) = 2, while the four permutations (2,1,3,4), (2,3,1,4), (2,3,4,1) and (2,4,1,3) start with a 2 and have a single descent giving T(3,0) = 4.

(End)

J. Riordan, An introduction to combinatorial analysis, J.Wiley, 1958. [From Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008]

Mark Conger. - A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n. [From Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008]

D. Foata, M. Schutzenberger. - Theorie Geometrique des Polynomes Euleriens, Lecture Notes in Math., no.138, Springer Verlag 1970. [From Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008]

T(n,k) = Sum_{j,0,k}(-1)^j (k+1-j) bin[n+1,j] (k+2-j)^(n-1). The generating function F(x,y):=Sum_{n>=0,k>=0}T(n+2,k) x^n/n! y^k is given by F(x,y) = 2E^(2x(1-y)) G(x,y)^3 where G(x,y):=(1 - y)/(1 - E^(x(1 - y)) y) is 1 + Sum_{n>=1,k>=1}a(n,k) x^n/n!*y^k and a(n,k) are the Eulerian numbers A008292. Note the offsets S(n+1) and T(n+2) in the definition of their gf's. A recurrence is given in the Mathematica code below.

Contribution from Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008: (Start)

The e.g.f. has the form (A(x,t))^2 = 1 + 2*t + (4 + 2*x)*t^2/2! + (8 + 14*x + 2*x^2)*t^3/3! + ..., where A(x,t) = (1 - x)/(exp(t*x - t) - x) = 1 + t + (1 + x)*t^2/2! + (1 + 4x + x^2)*t^3/3! + ... is the e.g.f. for the Eulerian numbers A008292.

Define the row polynomials R(n,x) := sum {k = 0..n-2} T(n,k)*x^k. Then x^2*R(n,x) = A(n,x) + (x-1)*A(n-1,x), where the A(n,x) are the Eulerian polynomials. For example, when n = 4, R(4,x) = 1/x^2*{(x + 11*x^2 + 11*x^3 + x^4) +(x-1)(x + 4*x^2 + x^3)} = 8 + 14*x + 2*x^2.

The row polynomials are also related to the Eulerian polynomials via differentiation. For example, d/dx[(1 + 4*x + x^2)/(1-x)^4] = (8 + 14*x + 2*x^2)/(1-x)^5 and d/dx[(1 + 11*x + 11*x^2 + x^3)/(1-x)^5] = (16 + 66*x + 36*x^2 + 2*x^3)/(1-x)^6.

Let p be a permutation in the symmetric group S_n. Let cyc(p) denote the number of cycles of p. Let exc(p) denote the number of excedances of p. Then R(n+1,x) = sum {p in S_n} 2^cyc(p)*x^exc(p) ([Foata & Schutzenberger p.40]. For example, for n = 2, the identity permutation (1,2) has 2 cycles and no excedances and so contributes 4 to the sum, while the transposition (2,1) has a single cycle and one excedance and contributes 2*x to the sum; hence R(3,x) = 4 + 2*x. Also R(n+1,x) = sum {k = 1..n} (k+1)!*Stirling2(n,k)*(x-1)^(n-k) for n = 1,2,... (see [Riordan p.214]).

Worpitzky type identities:

sum {k = 0..n-2} T(n,k)*binomial(x+k,n) = x*(x-1)^(n-1);

sum {k = 0..n-2} T(n,n-2-k)*binomial(x+k,n) = (x-1)*x^(n-1).

(End)

Table begins

\ k..0.....1.....2.....3.....4.....5

n

2 |..2

3 |..4.....2

4 |..8....14.....2

5 |.16....66....36.....2

6 |.32...262...342....82.....2

7 |.64...946..2416..1436...176.....2

The permutation (5,1,4,2,3) has big descents at i=1 and i=3. T(3,1)=2 counts (3,1,2) and (2,3,1).

a[0, 0] = 1; a[1, 0] = 1; a[n_, k_]/; n<=1 && k>=1 := 0 a[n_, k_]/; k>=n-1>=1 || k<0 := 0 a[n_, k_]/; 0<=k<=n-2 := a[n, k] = (k+1)Sum[a[i, k], {i, 0, n-1}] + Sum[(i-k)a[i, k-1], {i, n-1}] Table[a[n, k], {n, 0, 10}, {k, 0, Max[0, n-2]}]

Column k=1 is twice A066810. See A010027 for small descents.

Sequence in context: A114593 A114655 A051288 this_sequence A008303 A058942 A072866

Adjacent sequences: A120431 A120432 A120433 this_sequence A120435 A120436 A120437

nonn,tabl

David Callan (callan(AT)stat.wisc.edu), Jul 14 2006, Sep 25 2006