A Distinct parts/Odd parts identity for standard Young tableaux - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:46:56Z http://mathoverflow.net/feeds/question/43638 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43638/a-distinct-parts-odd-parts-identity-for-standard-young-tableaux A Distinct parts/Odd parts identity for standard Young tableaux Vasu vineet 2010-10-26T06:43:37Z 2010-10-30T01:16:10Z <p>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}$$</p> <p>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}$$</p> <p>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}$.</p> <p>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).</p> <p>Thanks!</p> <p>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$.</p> <p>Edit(10/27):</p> <p>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}$. </p> http://mathoverflow.net/questions/43638/a-distinct-parts-odd-parts-identity-for-standard-young-tableaux/43837#43837 Answer by Peter Tingley for A Distinct parts/Odd parts identity for standard Young tableaux Peter Tingley 2010-10-27T17:15:28Z 2010-10-27T17:15:28Z <p>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 href="http://docs.google.com/viewer?a=v&amp;q=cache:0jVPrNaVJKcJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.46.4811%26rep%3Drep1%26type%3Dpdf+%22distinct+parts%22+%22odd+parts%22+partition&amp;hl=en&amp;gl=us&amp;pid=bl&amp;srcid=ADGEESjCkRyxeXcrIDJZ4y-W_cG1fFc5l5wB5mPXZWlj0laoA7HGVUNB4X_U966FtdZ8U7b5WvbvckOZbfWD0S7VYWapNu5fL5LOQQTelBhEA6-SCoPh4fV7HFTV5SJoFCi9t7GNCyzL&amp;sig=AHIEtbSk5WDMQfdsle3LxjqBvsVrUOplbg" rel="nofollow"> A Note on Partitions into Distinct Parts and Odd Parts</a>. There are also some refinements of this statement out there. </p> http://mathoverflow.net/questions/43638/a-distinct-parts-odd-parts-identity-for-standard-young-tableaux/44204#44204 Answer by JBL for A Distinct parts/Odd parts identity for standard Young tableaux JBL 2010-10-30T01:16:10Z 2010-10-30T01:16:10Z <p>"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$." </p> <p>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.</p> <p>(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.)</p>