login
The OEIS is supported by the many generous donors 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)
16

%I M4548 N1932 #108 Dec 27 2023 19:11:54

%S 1,8,58,444,3708,33984,341136,3733920,44339040,568356480,7827719040,

%T 115336085760,1810992556800,30196376985600,532953524275200,

%U 9927928075161600,194677319705702400,4008789120817152000,86495828444928000000,1951566265951948800000,45958933902500720640000

%N Second-order Eulerian numbers <<n+1,n-1>>.

%C 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.

%C a(n) = number of edges in the Hasse diagram for the Bruhat order on permutations of [n+1]. - _David Callan_, Sep 03 2005

%C 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 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 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 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

%C 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>=1} k*A121579(n+2,k). - _Emeric Deutsch_, Aug 16 2006

%C a(n) is the total sum of the cycle maxima minus the cycle minima over all permutations of [n+1]. a(2) = 8 = 2+2+1+2+1+0: (123), (132), (12)(3), (13)(2), (1)(23), (1)(2)(3). - _Alois P. Heinz_, Dec 22 2023

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

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

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

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

%H Alois P. Heinz, <a href="/A002538/b002538.txt">Table of n, a(n) for n = 1..447</a> (first 100 terms from T. D. Noe)

%H E. Barcucci, A. Del Lungo and R. Pinzani, <a href="http://dx.doi.org/10.1016/0304-3975(95)00199-9">"Deco" polyominoes, permutations and random generation</a>, Theoretical Computer Science, 159, 1996, 29-42.

%H L. Carlitz, <a href="/A002538/a002538.pdf">Some numbers related to the Stirling numbers of the first and second kind</a>, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz., Numbers 544-576 (1976): 49-55. [Annotated scanned copy. The triangle is A008517.]

%H Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin, <a href="https://arxiv.org/abs/2006.09321">Interval parking functions</a>, arXiv:2006.09321 [math.CO], 2020.

%H I. Gessel and R. P. Stanley, <a href="https://doi.org/10.1016/0097-3165(78)90042-0">Stirling polynomials</a>, J. Combin. Theory, A 24 (1978), 24-33. (See Table 1.)

%H O. J. Munch, <a href="/A000460/a000460.pdf">Om potensproduktsummer</a> [Norwegian, English summary], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. [Annotated scanned copy]

%H O. J. Munch, <a href="http://www.jstor.org/stable/24524919">Om potensproduktsummer</a> [ Norwegian, English summary ], Nordisk Matematisk Tidskrift, 7 (1959), 5-19. There are errors in the last two rows of his table.

%H Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/1209.5959">Duplicial algebras and Lagrange inversion</a>, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

%H J. Ser, <a href="/A002720/a002720_4.pdf">Les Calculs Formels des Séries de Factorielles</a>, Gauthier-Villars, Paris, 1933 [Local copy].

%H J. Ser, <a href="/A002720/a002720.pdf">Les Calculs Formels des Séries de Factorielles</a> (Annotated scans of some selected pages)

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/trans.html">A survey of the Bruhat order of the symmetric group </a>

%H Albert Tarn, <a href="/A001333/a001333_1.pdf">Approximations to certain square roots and the series of numbers connected therewith</a> [Annotated scanned copy]

%F From _Vladeta Jovovic_, Sep 15 2003: (Start)

%F a(n) = Sum_{k=1..n} k * |Stirling1(n+2, k+2)|.

%F E.g.f.: (x+2*log(1-x))/(x-1)^3. (End)

%F With alternating signs: Ramanujan polynomials psi_2(n, x) evaluated at -1. - _Ralf Stephan_, Apr 16 2004

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

%F 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

%F a(n) = (n+1)!*((n+2)*h(n+2)-2*n-3) where h(n) = Sum_{k=1..n} 1/k. - _Gary Detlefs_, Mar 25 2011

%F 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

%p egf:= (x+2*log(1-x))/(x-1)^3:

%p a:= n-> n!*coeff(series(egf, x, n+1), x, n):

%p seq(a(n), n=1..21); # _Peter Luschny_, Feb 12 2021

%t 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 *)

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

%o (Magma) [n le 1 select n else (n+2)*Self(n-1) + n*Factorial(n): n in [1..30]]; // _Vincenzo Librandi_, Aug 11 2018

%Y Second diagonal of A008517 and second column of A112007.

%Y Cf. A121579.

%K nonn,nice

%O 1,2

%A _N. J. A. Sloane_, _Simon Plouffe_, _Mira Bernstein_, _Robert G. Wilson v_

%E More terms from _Joerg Arndt_, Apr 09 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)