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

Author

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

Keywords

• nonn

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

Examples

			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
		

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

Crossrefs

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

Programs

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

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

Extensions

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

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