Problem for week six

(Due to my ~~business~~ laziness, this week is a little long, longer than a month.)

Problem 6: Denote the transpositions in the symmetric group $S_n$ as $(i,i+1)$ . Define the length of a permutation $\pi$ as the least number of transpositions that formulate the permutation: $\pi$ . Show that the length of a permutation $\pi$ is the number of “inversions”: the number of pairs $latx i<j$ for which $\pi(i)>\pi(j)$ .

Solution to last problem:

Define the rank of a partition $\lambda$ to be $r(\lambda)=a(\lambda)-\ell(\lambda)$ , which would be the difference of the length of the first part of $\lambda$ and the number of parts of $\lambda$ . Then the following finishes the proof.

$\sum_{n=1}^\infty q^{n(3n-1)/2}(1-q^n)$

$=\sum_{n=1}^\infty (\sum_{ \lambda\in \mathcal {D}_n \atop \lambda \text{ has odd number of parts}}(-1)^{r(\lambda)}$

$- \sum_{ \lambda\in \mathcal {D}_n\atop \lambda \text{ has even number of parts}}(-1)^{r(\lambda)} )q^n$

$=\sum_{n=1}^\infty (\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has odd number of parts}\atop \text { the largest part is odd}}1$

$-\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has odd number of parts}\atop \text{the largest part is odd}}1)q^n$

$-(\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has even number of parts}\atop \text{the largest part is even}}1$

$- \sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has even number of parts}\atop \text{ the largest part is odd}}1)q^n$

$=\sum_{n=1}^\infty (\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has odd number of parts}\atop\text { the largest part is odd}}1$

$+ \sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has even number of parts}\atop \text{ the largest part is odd}}1 )q^n$

$-(\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has even number of parts}\atop \text{the largest part is even}}1$

$+\sum_{ \lambda\in \mathcal {D}_n; \lambda \text{ has odd number of parts}\atop \text{the largest part is odd}}1 )q^n$

$=\sum_{n=1}^\infty(\sum_{\lambda\in \mathcal {D}_n \atop \text{the largest part is odd}}1$

$-\sum_{\lambda\in \mathcal {D}_n\atop \text{the largest part is even}}1)q^n$

$=\sum_{n=1}^\infty(P_o(\mathcal {D}_n)-P_e(\mathcal {D}_n))q^n$

Like this:

Be the first to like this post.

Explore posts in the same categories: combinatorics, One Problem A Week

This entry was posted on 2010/11/14 at 2:47 pm and is filed under combinatorics, One Problem A Week. You can subscribe via RSS 2.0 feed to this post's comments. You can comment below, or link to this permanent URL from your own site.

Xiaochuan Liu's Weblog

Problem for week six

Like this:

Leave a Reply Cancel reply

Follow “Xiaochuan Liu's Weblog”