A180389 Number of permutations of 1..n with number of rises (p(i+1)>p(i)) the same as number of rises in the inverse permutation.

1, 1, 2, 6, 22, 96, 492, 2952, 20588, 164990, 1497740, 15187692, 169974040, 2078905752, 27567259896, 393759207372, 6025346314756, 98317949671110, 1703879074519500, 31251488731748108, 604748393942784976, 12312387380060084768, 263079571362773145632

Offset

0,3

Comments

Also equals sum of squares of the coefficients of the (numerators of) the G.F. for the count of monomials in the Schur polynomials of degree n (all partitions of weight n), in function of the number of variables v. - Wouter Meeussen, Dec 27 2010

Studied by Carlitz, Roselle, and Scoville in 'Permutations and Sequences with Repetitions by Number of Increases'. They refer to a rise/ascent as a 'jump', and consider the first entry of a permutation to always be a jump, so #jumps=#rises+1. Similarly, the number of rises in the inverse permutation/number of inverse descents corresponds to what they call the 'number of readings', and follow a convention so that #rises in inverse permutation+1=#readings. Formula can be attained by R_m(k,r), setting t=k, and summing k from 1 to m+1. - Kevin Dilks, Jun 09 2015

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..200

L. Carlitz et al., Permutations and sequences with repetitions by number of increases, J. Combin. Theory, 1 (1966), 350-374.

Wouter Meeussen, Schur Polynomials

Wouter Meeussen, Some notes on the link between A180389 and Schur polynomials

Formula

a(n) = Sum_{m=0..n+1} Sum_{i=0..m} Sum_{j=0..m} (-1)^{i+j} binomial(n+1,i) binomial(n+1,j) binomial((m-i)*(m-j)+n-1,n). - Kevin Dilks, Jun 09 2015

a(n) ~ sqrt(3) * n! / sqrt(Pi*n). - Vaclav Kotesovec, Jun 10 2015

Example

For n=4, a(4)=22 are all permutations of length 4 except for 3142 (which has only one ascent, and two inverse ascents) and 2413 (which has two ascents, and only one inverse ascent). - Kevin Dilks, Jun 09 2015

Maple

seq(add(add(add((-1)^(i+j)*binomial(n+1, i)*binomial(n+1, j)*binomial((m-i)*(m-j)+n-1, n), i=0..m), j=0..m), m=0..n+1), n=0..30); # Kevin Dilks, Jun 09 2015

Mathematica

Table[Sum[Sum[Sum[(-1)^(i+j)*Binomial[n+1, i]*Binomial[n+1, j]*Binomial[(m-i)*(m-j)+n-1, n], {i, 0, m}], {j, 0, m}], {m, 0, n+1}], {n, 0, 10}] (* Kevin Dilks, Jun 09 2015 *)

Crossrefs

A180388(n) + a(n) = n! = A000142(n).

Sequence in context: A248836 A351919 A328500 * A177389 A130907 A054096

Adjacent sequences: A180386 A180387 A180388 * A180390 A180391 A180392

Keyword

nonn

Author

Leroy Quet, D. S. McNeil and R. H. Hardin in the Sequence Fans Mailing List Sep 01 2010

Extensions

a(15)-a(20) from Wouter Meeussen, Dec 27 2010

a(0)=1 prepended by Alois P. Heinz, Jun 10 2015

Status

approved