%I A002538 M4548 N1932
%S A002538 1,8,58,444,3708,33984,341136,3733920,44339040,568356480,7827719040,
%T A002538 115336085760,1810992556800,30196376985600,532953524275200,
%U A002538 9927928075161600
%N A002538 Number of permutations by descents.
%C A002538 a(n) = number of edges in the Hasse diagram for the Bruhat order on permutations 
               of [n+1]. - David Callan (callan(AT)stat.wisc.edu), Sep 03 2005
%C A002538 Proof. As explained on page 1 of the Stanley link, edges in the Hasse 
               diagram of the (strong) Bruhat order on S_n are associated with pairs 
               (pi,(i,j)) with pi in S_n and 1 <= i < j <= n, such that pi_i < pi_j 
               and each entry of pi lying between pi_i and pi_j in POSITION does 
               not lie between pi_i and pi_j in VALUE.
%C A002538 For example, pi = (3, 5, 1, 2, 4) gives edges for the (i,j) pairs (1,
               2), (1,5), (3,4), (4,5) but not, e.g., for (i,j) = (3,5) because 
               2 lies between pi_3=1 and pi_5=4 both in position and in value.
%C A002538 Let us count edges for a given pair (i,j). Consider the j-i+1 entries 
               pi_i, pi_(i+1),...,pi_j. There are (j-i+1)! possible orderings for 
               their values and (i,j) contributes an edge <=> the values of pi_i, 
               pi_j are adjacent in this ordering with pi_i < pi_j.
%C A002538 There are (j-i)! such orderings (just coalesce the items pi_i, pi_j into 
               a single item). The net result is that (i,j) contributes an edge 
               1/(j-i+1) of the time. So the total number of edges in the Hasse 
               diagram is Sum_{1 <= i < j <= n} n!/(j-i+1) = (n+1)!(H_(n+1) - 2) 
               + n! where H_n = 1+1/2+1/3+ ... +1/n is the harmonic sum. QED - David 
               Callan (callan(AT)stat.wisc.edu), Mar 07 2006
%C A002538 Number of reentrant corners along the lower contours of all deco polyominoes 
               of height n+2. A deco polyomino is a directed column-convex polyomino 
               in which the height, measured along the diagonal, is attained only 
               in the last column. a(n)=Sum(k*A121579(n+2,k), k>0). - Emeric Deutsch 
               (deutsch(AT)duke.poly.edu), Aug 16 2006
%D A002538 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002538 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002538 J. Ser, Les Calculs Formels des S\'{e}ries de Factorielles. Gauthier-Villars, 
               Paris, 1933, p. 83.
%D A002538 O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk 
               Matematisk Tidskrift, 7 (1959), 5-19.
%D A002538 I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, 
               A 24 (1978), 24-33.
%D A002538 E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations 
               and random generation, Theoretical Computer Science, 159, 1996, 29-42.
%D A002538 I. Gessel and R. P. Stanley, Stirling polynomials, J. Comb. Theory, A, 
               24, 24-33 (see Table 1, p. 28).
%H A002538 T. D. Noe, <a href="b002538.txt">Table of n, a(n) for n=1..100</a>
%H A002538 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/trans.html">A 
               survey of the Bruhat order of the symmetric group </a>
%F A002538 Sum_{k=1..n} k*|Stirling1(n+2, k+2)|. E.g.f.: (x+2*ln(1-x))/(x-1)^3. 
               - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 15 2003
%F A002538 With alternating signs: Ramanujan polynomials psi_2(n, x) evaluated at 
               -1. - Ralf Stephan, Apr 16 2004
%F A002538 a(n)=(n+2)*a(n-1) + n*n!, n>=1, a(0):=0.
%F A002538 a(n)=(n+2)!HarmonicSum[n+2]+(n+1)!-2(n+2)! where HarmonicSum[n]=1+1/2+1/
               3+...+1/n. - David Callan (callan(AT)stat.wisc.edu), Mar 07 2006
%t A002538 Table[(-1)^(n + 1)* Sum[(-1)^(n - k) k (-1)^(n - k) StirlingS1[n + 3, 
               k + 3], {k, 0, n}], {n, 1, 16}] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 
               Jul 08 2009]
%Y A002538 Second diagonal of A008517 and second column of A112007.
%Y A002538 Cf. A121579.
%Y A002538 Sequence in context: A126529 A039759 A047867 this_sequence A112424 A032365 
               A074423
%Y A002538 Adjacent sequences: A002535 A002536 A002537 this_sequence A002539 A002540 
               A002541
%K A002538 nonn,nice
%O A002538 1,2
%A A002538 N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe, Mira Bernstein, 
               Robert G. Wilson v (rgwv(AT)rgwv.com)