|
| |
|
|
A002538
|
|
Second-order Eulerian numbers <<n+1,n-1>>.
(Formerly M4548 N1932)
|
|
16
|
|
|
|
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>=1} k*A121579(n+2,k). - Emeric Deutsch, Aug 16 2006
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
|
|
|
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
|
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.
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} k * |Stirling1(n+2, k+2)|.
E.g.f.: (x+2*log(1-x))/(x-1)^3. (End)
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_{k=1..n} 1/k. - 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
a(n) = (-1)*((2*n + 3)*(n + 1)! - abs(Stirling1(n + 3, 2))). - Detlef Meya, Apr 09 2024
|
|
|
MAPLE
|
egf:= (x+2*log(1-x))/(x-1)^3:
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
# Alternative:
a := n -> (n + 1)! * ((n + 2)*harmonic(n + 2) - 2*n - 3);
|
|
|
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 *)
a[n_]:=(-1)*((2*n+3)*(n+1)!-Abs[StirlingS1[n+3, 2]]); Flatten[Table[a[n], {n, 1, 21}]] (* Detlef Meya, Apr 09 2024 *)
|
|
|
PROG
|
(PARI) N=66; x='x+O('x^66); Vec(serlaplace((x+2*log(1-x))/(x-1)^3)) \\ Joerg Arndt, Apr 09 2016
(Magma) [n le 1 select n else (n+2)*Self(n-1) + n*Factorial(n): n in [1..30]]; // Vincenzo Librandi, Aug 11 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
