# A Distinct parts/Odd parts identity for standard Young tableaux

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}$.

-
ah sorry! $o_{\lambda}$ for number of odd parts. Edited. Thanks – Vasu vineet Oct 26 '10 at 7:04
– Richard Stanley Oct 26 '10 at 17:08
Neat. I should go through the report. Thanks a lot, for the pointer! – Vasu vineet Oct 26 '10 at 19:07

"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.)

-
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

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.

-
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