Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\lambda$ denote a partition of size $n$. Let $$d_{\lambda}= \text{number of distinct parts of } \lambda $$ $$o_{\lambda}= \text{number of odd parts of } \lambda $$ $$f_{\lambda}= \text{number of standard Young tableau of shape } \lambda $$ Given an involution $\pi \in S_{n}$, whose insertion tableau has shape $\lambda$, it is well known (via the Robinson-Schensted correspondence, and neatly outlined in Sagan's book on the Symmetric Group) that : $$ o_{\lambda^{t}}= \text{number of fixed points in the involution } \pi $$ $$ \sum_{\lambda \vdash n} f_{\lambda}= \text{number of involutions in } S_{n} $$

In the aforementioned formulae, $\lambda^{t}$ refers to the conjugate of the partition $\lambda$. Now, some computations I have carried out for Kronecker products of two irreducible characters of $S_{n}$ revealed the following identity in a special case: $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n}o_{\lambda}f_{\lambda}$$

Note that the right hand side actually counts the total number of fixed points in all involutions in $S_{n}$. I did manage to prove the above result in general, but I am hoping someone could guide me to a proof which is bijective, i.e say uses the RS correspondence to establish the left hand side equals the the total number of fixed points in all involutions in $S_{n}$.

Also, I'd like it if I could be directed to where this and/or similar sums appeared.(as an exercise in a book, or in some paper).

Thanks!

Edit: I had a look at Sagan, which I did not have handy last night and made a minor change in saying the number of fixed points in an involution $\pi \in S_{n}$ is the number of odd columns in the insertion tableau of $\pi$.

Edit(10/27):

I thought I should put down the idea that I had. But since I am not sure if this should count as an answer, I am putting it in the body of the question. Note that $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n+1}f_{\lambda}-\sum_{\lambda \vdash n}f_{\lambda}$$ So all that remains to be shown is the nice fact that the total number of fixed points in all the involutions of $S_{n}$ is the difference between the number of involutions in $S_{n+1}$ and the number of involutions in $S_{n}$.

share|improve this question
    
ah sorry! $o_{\lambda}$ for number of odd parts. Edited. Thanks –  Vasu vineet Oct 26 '10 at 7:04
4  
    
Neat. I should go through the report. Thanks a lot, for the pointer! –  Vasu vineet Oct 26 '10 at 19:07
add comment

2 Answers

up vote 2 down vote accepted

"all that remains to be shown is the nice fact that the total number of fixed points in all the involutions of $S_n$ is the difference between the number of involutions in $S_{n+1}$ and the number of involutions in $S_n$."

And this is straightforward: every involution in $S_n$ can be extended to an involution in $S_{n + 1}$ either by replacing a fixed point $i$ with a cycle $(i, n + 1)$ or by adding $n + 1$ as a new fixed point.

(It is unclear to me whether you had already seen that this fact has such a simple bijective proof; it's also not clear to me whether this satisfies your desire for a completely bijective proof.)

share|improve this answer
    
When I made the post, I did not have the above mentioned proof. When I made the edit dated 10/27, that was when I struck upon the idea you completed above. I did not know if I could answer my own question, hence I just edited the original post. I was also interested in similar identities and the link Prof. Stanley mentioned has lots of them. So for the moment, this thread should be closed. Thanks a lot nvertheless! –  Vasu vineet Oct 30 '10 at 2:29
    
Yes, you absolutely can answer your own question -- indeed, in this case it seems like a nice thing to do would be to sketch out the argument, then accept your own answer. –  JBL Oct 30 '10 at 3:06
add comment

A possibly related result says that the number of partitions on n into distinct parts is equal to the number of partitions of n into odd parts. There is a bijective proof, I think due to Sylvester. I think a simpler version of the original bijection can be found in Kim and Yee's paper A Note on Partitions into Distinct Parts and Odd Parts. There are also some refinements of this statement out there.

share|improve this answer
    
Thanks, I'll take a look. The whole thing I like about the identity I mentioned in the original post is the odd part\distinct part thing which is so popular as far as partition identities go. –  Vasu vineet Oct 28 '10 at 1:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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