|
| |
|
|
A120434
|
|
Triangle read by rows: counts permutations by number of big descents.
|
|
7
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,1
|
|
|
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
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)
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
|
|
|
REFERENCES
|
J. Riordan, An introduction to combinatorial analysis, J. Wiley, 1958.
|
|
|
LINKS
|
|
|
|
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.
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
|
|
|
EXAMPLE
|
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).
|
|
|
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]}]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
