Return to Question

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $$G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t),$$

and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

$$I_{n}^{\sigma(y)=x}(k)=\sum_{i=0}^{n-1-y}I_{n-1}^{\sigma(y)=x}(k-i)+\sum_{i=n-y+1}^nI^{\sigma(y-1)=x}_{n-1}(k-i)$$

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $$G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t),$$

and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

$$I_{n}^{\sigma(y)=x}(k)=\sum_{i=0}^{n-1-y}I_{n-1}^{\sigma(y)=x}(k-i)+\sum_{i=n-y+1}^nI^{\sigma(y-1)=x}_{n-1}(k-i)$$

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t)$, and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

\begin{align*} I_n^{\sigma(y)=x}(k)&= I_{n-1}^{\sigma(y)=x}(k)+I_{n-1}^{\sigma(y)=x}(k-1)+\ldots+I_{n-1}^{\sigma(y)=x}(n-y)\\ &+ I_{n-1}^{\sigma(y-1)=x}(k-y+2)+I_{n-1}^{\sigma(y-1)=x}(k-y+1)+\ldots+I_{n-1}^{\sigma(y-1)=x}(0) \end{align*}

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $$G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t),$$

and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

$$I_{n}^{\sigma(y)=x}(k)=\sum_{i=0}^{n-1-y}I_{n-1}^{\sigma(y)=x}(k-i)+\sum_{i=n-y+1}^nI^{\sigma(y-1)=x}_{n-1}(k-i)$$

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t)$, and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

\begin{eqnarray*} I_n^{\sigma(y)=x}(k)&=&\ \ \ \ I_{n-1}^{\sigma(y)=x}(k)+I_{n-1}^{\sigma(y)=x}(k-1)+\ldots+I_{n-1}^{\sigma(y)=x}(n-y)\\ &&+I_{n-1}^{\sigma(y-1)=x}(k-y+2)+I_{n-1}^{\sigma(y-1)=x}(k-y+1)+\ldots+I_{n-1}^{\sigma(y-1)=x}(0) \end{eqnarray*}

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

This question is cross-posted from math.stackexchange because it might be too technical.

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i< j$ with $\sigma(i) > \sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t)$, and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

\begin{align*} I_n^{\sigma(y)=x}(k)&= I_{n-1}^{\sigma(y)=x}(k)+I_{n-1}^{\sigma(y)=x}(k-1)+\ldots+I_{n-1}^{\sigma(y)=x}(n-y)\\ &+ I_{n-1}^{\sigma(y-1)=x}(k-y+2)+I_{n-1}^{\sigma(y-1)=x}(k-y+1)+\ldots+I_{n-1}^{\sigma(y-1)=x}(0) \end{align*}

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?