1
$\begingroup$

Let $n\in\mathbb{N}$. For a permutation $\sigma:[n]\rightarrow[n]$, we ue the notation $(\sigma(1)\sigma(2)\cdots\sigma(n))$ to describe the mapping. A pair of integers $(i,j)$ is called an inversion of $\sigma$ if $i<j$ and $\sigma(i)>\sigma(j)$. For example, the permutation $(32415)$ on $[5]$ has 4 inversions: $(1,2),(1,4),(2,4),(3,4)$. Define the weight function $w$ on a permutation $\sigma$ to be the number of inversions in $\sigma$. Let $S_n$ be the set of all permutations of $[n]$.

(a) Determine the generating functions for $S_1$, $S_2$, $S_3$ with respect to the weight function $w$.

(b) Prove that for $n\geq 2$, $\Phi_{S_{n}}(x)=(1+x+\cdots+x^{n-1})\Phi_{S_{n-1}}(x) $. You may use the following non-standard notation: if $\sigma$ is a permutation of $[n]$, then $\sigma '$ is the permutation of $[n-1]$ obtained from $\sigma$ by removing the element $n$.

(c) Prove that the number of permutations of $[n]$ with $k$ inversions is

$$[x^{k}]\frac{\prod_{i=1}^{n}(1-x^{i})}{(1-x)^{n}}$$

(a) is doable by brute-forcing. (b) seems to be doable by the product lemma if only the weight function was something more tractable, since I need to prove that the weight is equal to adding the weights of some product. (c) is completely over my head since I can't get any general formula for the number of inversions in a permutation.

$\endgroup$
  • $\begingroup$ There is some material here that you may want to consult. This post could be relevant. $\endgroup$ – Marko Riedel May 30 '13 at 20:46
2
$\begingroup$

If you have (a) and (b), you have (c):

$$\begin{align*} \frac1{(1-x)^n}\prod_{i=1}^n(1-x^i)&=\prod_{i=1}^n\frac{1-x^i}{1-x}\\\\ &=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;, \end{align*}$$

so you need only verify that $\Phi_{S_1}(x)=1$.

One way to prove that

$$\Phi_{S_n}(x)=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)$$

is by induction on $n$: let $$c_n(k)=[x^k]\Phi_{S_n}(x)\;,$$ the number of $n$-permutations with $k$ inversions, and $$a_n(k)=[x^k]\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;,$$ and show that

$$c_n(k)=\sum_{i=\max\{0,k-n+1\}}^kc_{n-1}(i)\tag{1}$$

and

$$a_n(k)=\sum_{i=\max\{0,k-n+1\}}^ka_{n-1}(i)\;.\tag{2}$$

$(2)$ is pretty straightforward. For $(1)$, think about starting with a permutation of $[n-1]$ with $i$ inversions and inserting $n$ so that it precedes the last $k-i$ elements of the permutation; how many inversions does that add to the permutation? (The non-standard notation mentioned in (b) appears to be designed to let you talk easily about the inverse of this operation.)

$\endgroup$
  • $\begingroup$ Just to clarify - I don't have (b). $\endgroup$ – ithisa May 30 '13 at 20:48
  • $\begingroup$ @Eric: I realize that. The first part of the answer is just pointing out that (c) won’t be a problem once you do have (b). The part starting One way to prove ... is really about proving (b), though I didn’t phrase it quite that way: (a) and (b) together are equivalent to $$\Phi_{S_n}(x)=\prod_{i=1}^n\left(1+x+x^2+\ldots+x^{i-1}\right)\;.$$ $\endgroup$ – Brian M. Scott May 30 '13 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.