A120434 Triangle read by rows: counts permutations by number of big descents.

2, 4, 2, 8, 14, 2, 16, 66, 36, 2, 32, 262, 342, 82, 2, 64, 946, 2416, 1436, 176, 2, 128, 3222, 14394, 16844, 5364, 366, 2, 256, 10562, 76908, 156190, 99560, 18654, 748, 2, 512, 33734, 381566, 1242398, 1378310, 528818, 61946, 1514, 2

Offset: 2

Author

David Callan, Jul 14 2006, Sep 25 2006

Keywords

• nonn
• tabl

Comments

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, Feb 01 2007

From Peter Bala, 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-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)

Appears to be mirror image of A199335. - Dale Gerdemann, Apr 18 2015

T(n,k) gives the number of permutations in the group S_n with k+1 special descents, where a special descent is defined as either a normal descent or if the permutation starts with 1. For example, in the symmetric group S_3, the permutations (1,3,2) and (3,2,1) have 2 special descents so T(3,1)=2, while the permutations (1,2,3), (2,1,3), (2,3,1), and (3,1,2) have one special descent, giving T(3,0)=4. - Tanya Khovanova and Rich Wang, Jan 31 2023

Examples

			Table begins
  n\ k|  0     1     2     3     4     5
  ----+---------------------------------
    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).
		

References

• J. Riordan, An introduction to combinatorial analysis, J. Wiley, 1958.

Links

• J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.
• Mark Conger, - A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n, arXiv:math/0508112 [math.CO], 2005.
• D. Foata and M. Schutzenberger, Théorie Géometrique des Polynômes Eulériens, Lecture Notes in Math., no.138, Springer Verlag 1970; arXiv:math/0508232 [math.CO], 2005.
• Tanya Khovanova and Rich Wang, Ending States of a Special Variant of the Chip-Firing Algorithm, arXiv:2302.11067 [math.CO], 2023.

Crossrefs

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

Cf. A008292, A173018, A199335, A144696.

Programs

Maple

U := proc(n,k) option remember: if k < 0 or k > n then 0 elif n = 0 then 1 else (k+2)*U(n-1, k) + (n-k)*U(n-1, k-1) fi end: T_row := n -> seq(U(n-1,k), k = 0..n-2): for n from 2 to 7 do T_row(n) od; # Peter Luschny, Oct 15 2017

Mathematica

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]}]

Formula

T(n,k) = Sum_{j=0..k} (-1)^j*(k + 1 - j)*binomial(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 g.f.s. A recurrence is given in the Mathematica code below.

From Peter Bala, 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.

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)

If enumerated like the Eulerian numbers by Knuth (A173018) with 1 prepended, i.e., as 1; 2, 0; 4, 2, 0; 8, 14, 2, 0; ... with 0 <= k <= n the numbers have the recurrence (k+2)*U(n-1, k) + (n-k)*U(n-1, k-1). - Peter Luschny, Oct 15 2017