login
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.
3
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
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
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