

A002538


Secondorder Eulerian numbers <<n+1,n1>>.
(Formerly M4548 N1932)


12



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

Secondorder 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 ji+1 entries pi_i, pi_(i+1),...,pi_j. There are (ji+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 (ji)! 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/(ji+1) of the time. So the total number of edges in the Hasse diagram is Sum_{1 <= i < j <= n} n!/(ji+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 columnconvex polyomino in which the height, measured along the diagonal, is attained only in the last column. a(n)= Sum_{k>=1} k*A121579(n+2,k).  Emeric Deutsch, Aug 16 2006


REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. AddisonWesley, Reading, MA, 1994, p. 270.
J. Ser, Les Calculs Formels des Séries de Factorielles. GauthierVillars, 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, 2942.
L. Carlitz, Some numbers related to the Stirling numbers of the first and second kind, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544576 (1976): 4955. [Annotated scanned copy. The triangle is A008517.]
Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, Interval parking functions, arXiv:2006.09321 [math.CO], 2020.
I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24 (1978), 2433. (See Table 1.)
O. J. Munch, Om potensproduktsummer [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 519. [Annotated scanned copy]
O. J. Munch, Om potensproduktsummer [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 519. There are errors in the last two rows of his table.
JeanChristophe Novelli and JeanYves 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

From Vladeta Jovovic, Sep 15 2003: (Start)
a(n) = Sum_{k=1..n} k * Stirling1(n+2, k+2).
E.g.f.: (x+2*log(1x))/(x1)^3. (End)
With alternating signs: Ramanujan polynomials psi_2(n, x) evaluated at 1.  Ralf Stephan, Apr 16 2004
a(n) = (n+2)*a(n1) + 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*n3) where h(n) = Sum_{k=1..n} 1/k.  Gary Detlefs, Mar 25 2011
Conjecture: a(n) + 2*(n2)*a(n1) + (n^2+4*n+1)*a(n2)  n*(n1)*a(n3) = 0.  R. J. Mathar, Oct 27 2014


MAPLE

egf:= (x+2*log(1x))/(x1)^3:
a:= n> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=1..21); # Peter Luschny, Feb 12 2021


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(1x))/(x1)^3)) \\ Joerg Arndt, Apr 09 2016
(MAGMA) [n le 1 select n else (n+2)*Self(n1) + n*Factorial(n): n in [1..30]]; // Vincenzo Librandi, Aug 11 2018


CROSSREFS

Second diagonal of A008517 and second column of A112007.
Cf. A121579.
Sequence in context: A039759 A244939 A047867 * A263503 A343089 A112424
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



