%I A120434
%S A120434 2,4,2,8,14,2,16,66,36,2,32,262,342,82,2,64,946,2416,1436,176,2,128,
%T A120434 3222,14394,16844,5364,366,2,256,10562,76908,156190,99560,18654,748,2,
%U A120434 512,33734,381566,1242398,1378310,528818,61946,1514,2
%N A120434 Triangle read by rows: counts permutations by number of big descents.
%C A120434 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 A120434 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 A120434 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
%C A120434 Contribution from Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008: 
               (Start)
%C A120434 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.
%C A120434 Two equivalent interpretations of this array are:
%C A120434 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 A120434 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.
%C A120434 (End)
%D A120434 J. Riordan, An introduction to combinatorial analysis, J.Wiley, 1958. 
               [From Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008]
%H A120434 Mark Conger. <a href="http://arXiv.org/abs/math.CO/0508112">- A refinement 
               of the Eulerian polynomials and the joint distribution of pi(1) and 
               Des(pi) in S_n.</a> [From Peter Bala (pbala(AT)toucansurf.com), Sep 
               19 2008]
%H A120434 D. Foata, M. Schutzenberger. <a href="http://www.arXiv.org/abs/math.CO/
               0508232">- Theorie Geometrique des Polynomes Euleriens</a>, Lecture 
               Notes in Math., no.138, Springer Verlag 1970. [From Peter Bala (pbala(AT)toucansurf.com), 
               Sep 19 2008]
%F A120434 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.
%F A120434 Contribution from Peter Bala (pbala(AT)toucansurf.com), Sep 19 2008: 
               (Start)
%F A120434 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 A120434 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 A120434 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 A120434 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]).
%F A120434 Worpitzky type identities:
%F A120434 sum {k = 0..n-2} T(n,k)*binomial(x+k,n) = x*(x-1)^(n-1);
%F A120434 sum {k = 0..n-2} T(n,n-2-k)*binomial(x+k,n) = (x-1)*x^(n-1).
%F A120434 (End)
%e A120434 Table begins
%e A120434 \ k..0.....1.....2.....3.....4.....5
%e A120434 n
%e A120434 2 |..2
%e A120434 3 |..4.....2
%e A120434 4 |..8....14.....2
%e A120434 5 |.16....66....36.....2
%e A120434 6 |.32...262...342....82.....2
%e A120434 7 |.64...946..2416..1436...176.....2
%e A120434 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).
%t A120434 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 A120434 Column k=1 is twice A066810. See A010027 for small descents.
%Y A120434 Sequence in context: A114593 A114655 A051288 this_sequence A008303 A058942 
               A072866
%Y A120434 Adjacent sequences: A120431 A120432 A120433 this_sequence A120435 A120436 
               A120437
%K A120434 nonn,tabl
%O A120434 2,1
%A A120434 David Callan (callan(AT)stat.wisc.edu), Jul 14 2006, Sep 25 2006