login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002538 Second-order Eulerian numbers <<n+1,n-1>>
(Formerly M4548 N1932)
8
1, 8, 58, 444, 3708, 33984, 341136, 3733920, 44339040, 568356480, 7827719040, 115336085760, 1810992556800, 30196376985600, 532953524275200, 9927928075161600, 194677319705702400, 4008789120817152000, 86495828444928000000, 1951566265951948800000, 45958933902500720640000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Second-order eulerian numbers <<n,k>> count permutations of the multiset {1,1,2,2,...,n,n} with k ascents and the restriction that for any m <= n, all numbers between the two copies of m are less than m.

a(n) = number of edges in the Hasse diagram for the Bruhat order on permutations of [n+1]. - David Callan, 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, 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, Aug 16 2006

REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.

J. Ser, Les Calculs Formels des Séries de Factorielles. Gauthier-Villars, Paris, 1933, p. 83.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

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

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

L. Carlitz, Some numbers related to the Stirling numbers of the first and second kind, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544-576 (1976): 49-55. [Annotated scanned copy. The triangle is A008517.]

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

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

O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. There are errors in the last two rows of his table.

Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

J. Ser, Les Calculs Formels des Séries de Factorielles (Annotated scans of some selected pages)

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

Albert Tarn, Approximations to certain square roots and the series of numbers connected therewith [Annotated scanned copy]

FORMULA

a(n) = Sum_{k=1..n} k*|Stirling1(n+2, k+2)|. E.g.f.: (x+2*log(1-x))/(x-1)^3. - Vladeta Jovovic, 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, Mar 07 2006

a(n) = (n+1)!*((n+2)*h(n+2)-2*n-3) where h(n) = sum(1/k,k=1..n). [Gary Detlefs, Mar 25 2011]

Conjecture: a(n) +2*(-n-2)*a(n-1) +(n^2+4*n+1)*a(n-2) -n*(n-1)*a(n-3)=0. - R. J. Mathar, Oct 27 2014

MATHEMATICA

Table[(-1)^(n + 1)* Sum[(-1)^(n - k) k (-1)^(n - k) StirlingS1[n + 3, k + 3], {k, 0, n}], {n, 1, 16}] (* Zerinvary Lajos, Jul 08 2009 *)

PROG

(PARI) N=66; x='x+O('x^66); Vec(serlaplace((x+2*log(1-x))/(x-1)^3)) \\ Joerg Arndt, Apr 09 2016

CROSSREFS

Second diagonal of A008517 and second column of A112007.

Cf. A121579.

Sequence in context: A039759 A244939 A047867 * A263503 A112424 A190977

Adjacent sequences:  A002535 A002536 A002537 * A002539 A002540 A002541

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane, Simon Plouffe, Mira Bernstein, Robert G. Wilson v

EXTENSIONS

More terms from Joerg Arndt, Apr 09 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 29 06:34 EDT 2017. Contains 284250 sequences.