1,2

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

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.

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.

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.

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

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

J. Ser, Les Calculs Formels des S\'{e}ries de Factorielles. Gauthier-Villars, Paris, 1933, p. 83.

O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19.

I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24 (1978), 24-33.

E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.

I. Gessel and R. P. Stanley, Stirling polynomials, J. Comb. Theory, A, 24, 24-33 (see Table 1, p. 28).

T. D. Noe, Table of n, a(n) for n=1..100

R. P. Stanley, A survey of the Bruhat order of the symmetric group

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.yu), Sep 15 2003

With alternating signs: Ramanujan polynomials psi_2(n, x) evaluated at -1. - Ralf Stephan, Apr 16 2004

a(n)=(n+2)*a(n-1) + n*n!, n>=1, a(0):=0.

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

Second diagonal of A008517, and second column of A112007.

Cf. A121579.

Sequence in context: A126529 A039759 A047867 this_sequence A112424 A032365 A074423

Adjacent sequences: A002535 A002536 A002537 this_sequence A002539 A002540 A002541

nonn,nice

njas, Simon Plouffe, Mira Bernstein, Robert G. Wilson v (rgwv(AT)rgwv.com)