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

%I #53 Sep 14 2024 06:50:56

%S 2,4,2,8,14,2,16,66,36,2,32,262,342,82,2,64,946,2416,1436,176,2,128,

%T 3222,14394,16844,5364,366,2,256,10562,76908,156190,99560,18654,748,2,

%U 512,33734,381566,1242398,1378310,528818,61946,1514,2

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

%C 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).

%C 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

%C 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

%C From _Peter Bala_, Sep 19 2008: (Start)

%C 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.

%C Two equivalent interpretations of this array are:

%C 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).

%C 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)

%C Appears to be mirror image of A199335. - _Dale Gerdemann_, Apr 18 2015

%C 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

%D J. Riordan, An introduction to combinatorial analysis, J. Wiley, 1958.

%H J. F. Barbero G., J. Salas and E. J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.5624">Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications</a>, arXiv preprint arXiv:1307.5624 [math.CO], 2013-2015.

%H Mark Conger, <a href="https://arxiv.org/abs/math/0508112">- A refinement of the Eulerian polynomials and the joint distribution of pi(1) and Des(pi) in S_n</a>, arXiv:math/0508112 [math.CO], 2005.

%H D. Foata and M. Schutzenberger, <a href="https://arxiv.org/abs/math/0508232">Théorie Géometrique des Polynômes Eulériens</a>, Lecture Notes in Math., no.138, Springer Verlag 1970; arXiv:math/0508232 [math.CO], 2005.

%H Tanya Khovanova and Rich Wang, <a href="https://arxiv.org/abs/2302.11067">Ending States of a Special Variant of the Chip-Firing Algorithm</a>, arXiv:2302.11067 [math.CO], 2023.

%F 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.

%F From _Peter Bala_, Sep 19 2008: (Start)

%F 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.

%F 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.

%F 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.

%F 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.

%F 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]).

%F Worpitzky type identities:

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

%F Sum_{k = 0..n-2} T(n,n-2-k)*binomial(x+k,n) = (x-1)*x^(n-1). (End)

%F 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

%e Table begins

%e n\ k| 0 1 2 3 4 5

%e ----+---------------------------------

%e 2 | 2

%e 3 | 4 2

%e 4 | 8 14 2

%e 5 | 16 66 36 2

%e 6 | 32 262 342 82 2

%e 7 | 64 946 2416 1436 176 2

%e 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).

%p 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

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

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

%Y Cf. A008292, A173018, A199335, A144696.

%K nonn,tabl

%O 2,1

%A _David Callan_, Jul 14 2006, Sep 25 2006