4
$\begingroup$

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the Young diagram of a permutation and enclose it in a right isosceles triangle so that the hypotenuse of the triangle just touches the 'jagged' edge of the diagram, then collapse the negative space in the triangle along the hypotenuse. Negative 'corners' in the Young diagram correspond to leaves in the tree, and their depths correspond to the distance from the hypotenuse.

For example -

    0
   / \
  0   0
 / \
0   0

corresponds to

   []
   []
 [][]

I've also noticed that adding a block to the Young diagram, which necessarily takes place at a negative corner, is equivalent to taking a tree's leaf and moving it one step closer to the root:

              0
  []         /|\
[][]        0 0 0
[][]       /
          0

Thus, given a set of trees with the same number of vertices at each depth, it is necessarily the case that their corresponding Young diagrams have the same number of boxes in them - which is to say, their corresponding partitions are of the same integer. However, it is not the case that all partitions of a particular integer correspond to trees with the same number of vertices at each depth, or even trees with the same number of vertices overall, and likewise trees with the same total number of vertices can correspond to partitions of different integers.

This observation lead me to the question: Is there any way to tell, given a partition, how many vertices there are in the corresponding tree without doing something equivalent to finding the tree itself? And, is this bijection significant of a deeper underlying connection between partitions and trees, or just a coincidence?

EDIT: to hopefully clarify my explanation above, here's the slightly longer version with pictures:ShortTreeProof

$\endgroup$
  • $\begingroup$ What, then, is the partition corresponding to: 0newline / | \newline 0 0 0newline /\newline 00 ? $\endgroup$ – Alex Mar 3 '16 at 22:41
  • $\begingroup$ I can't tell which because comments aren't formatted. If the 00 on the last line are meant to connect to the first 0 on the second one, then it's 3 + 2 + 2 + 1, if you meant to the center 0 then it's 4 + 2 + 1 + 1, and if you meant to the last 0 then it's 4 + 3 + 1. Mirror image graphs give conjugate partitions. $\endgroup$ – P... Mar 4 '16 at 0:16
  • $\begingroup$ I'm afraid I still don't understand correspondence well enough. What would correspond to 0 / 0 / 0? What about 0 /\ 0 0? What tree corresponds to 1 + 1 + 1? Or maybe you can provide a reference to the proof? $\endgroup$ – Alex Mar 4 '16 at 1:37
  • $\begingroup$ I'll quick make one up and add it into my post. Give me a few minutes... $\endgroup$ – P... Mar 4 '16 at 2:09
  • $\begingroup$ Done. Hopefully that is clear enough? $\endgroup$ – P... Mar 4 '16 at 2:52
1
$\begingroup$

Wow, thanks for such clear explanation. I think finding the answer was much faster than the time you took to draw up such a nice diagram. Also, the diagram examples were incomplete; your answer to my comment really made an important difference in the correctness of my algorithm.

So, the vertices of the graph are split into: 1) Root node. This is included by default.

2) Leaf nodes. These correspond to the number of inside-pointing right angles in your diagram.

3) Non-leaf nodes. These correspond to straight angles in your diagram.

Important caveat: when counting non-leaf nodes, you count them once when you go down, and once more when you go back up. So you must divide the number of straight angles you get by 2 to get the actual number of non-leaf nodes. This is analogous to counting only the inside-pointing right angles on your diagram.

Similarly, to make sure you get the correct number, you must count the edge nodes twice. This corresponds to counting the number of straight angles within your entire triangle, not only on the Young Diagram.

Your example [r denotes inside right angle; , denotes straight angle]:

|,
|,
|r                   
|[]r  ,  ,
|[] [] [] []r
|[] [] [] [] [],
|[] [] [] [] [],
|[] [] [] [] []r  ,  ,
|__ __ __ __ __ __ __ __

Thus, 4 right angles and 8 straight angles = 4 leaves, 8/2 = 4 non-leaves, and always 1 root.

$\endgroup$
  • $\begingroup$ Oh wow, I can't believe I didn't notice that. I was overthinking it rather badly. Thank you. $\endgroup$ – P... Mar 4 '16 at 3:35
  • $\begingroup$ Any time you have a problem dealing with these, let me know. Since I've already taken the time to get familiar with how these work, I might be able to help with less effort than someone who hasn't. $\endgroup$ – Alex Mar 4 '16 at 3:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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