9
$\begingroup$

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

$\endgroup$
3

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$ Oct 30, 2010 at 2:29
  • $\begingroup$ 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. $\endgroup$
    – JBL
    Oct 30, 2010 at 3:06
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 28, 2010 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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