The 280th day of the year is upon us, and as I always post an arithmetic or mathematical piece of trivia about the day of the year, I used the same quote from Wikipedia that I had used last year (and yes it's still there this year, on Wikipedia and my blog, while I figure out if I really just don't understand, or if it is wrong... hence this blog)
So here is what it (Wikipedia) and I (my blog) said: "There are 280 plane trees with ten nodes. As a consequence of this, 18 people around a round table can shake hands with each other in non-crossing ways, in 280 different ways (this includes rotations)."
Ok, so I see a three-fold task, 1) is there a relation between the number of plane trees with n nodes and (apparently) the number of ways that 2(n-1) people around a table can shake hands without crossing arms, 2) independent of the relationship between the two ideas, can I figure out how many plane trees there are with ten nodes, and 3) the same about the number of handshakes by 18 people around a table without crossing hands.
In the interest of drawing better mathematical talent to give me assistance, I will expose my attempts to reason through these questions by exposing my limited understanding in this blog... Corrections and contributions are welcomed.
So for part 1 and 2, I used Wikipedia's definition that "An ordered tree or plane tree is a rooted tree for which an ordering is specified for the children of each vertex." I found a nice article from Australia that uses the rooted tree with the root down, but otherwise counts the number of, "rooted planer trees" and the numbers for planer trees with 3, 4, and 5 nodes had respectively, 2, 5 and 14 different trees.... Holy Molley Captain Marvel, those I recognize as Catalan numbers...could it be??? yep, the number of trees with 6 nodes was 42. So All I had to do was check the number of possible handshakes for 2(3-1), 2(4-1) etc and see if they too were Catalan numbers. Maybe these were both one of the myriad of combinatorial objects counted by the Catalan sequence.
It took me a short while to decide how to attack the handshakes, but I settled on an even number of dots equally spaced around a circle. To avoid having any two chords (handshakes) intersect, it seemed that when points a and b were connected, there must be an even number of handshakes on each side of the circle divided by the chord. If not, they could not all shake hands. So I could divide the n points and repeat the problem on a smaller n on each side of the dividing chord. This seemed to require a recursive process so I reduced the problem down to 2 points. For n=2 there could only be 1 handshake, For n= 4 points, I could visually see that there would only be 2 possible ways,
To divide the graph with six points, I could either have no points on the left of the division, and four on the right, OR two on the left and two on the right, OR four on the left and none on the right. If I added the number of cases with 4 on the right to the number of cases with two on the left times the number with two on the right, plus the number with 4 on the left, I would know the number for six... I needed some notation here so I called the H(n) for the number of handshakes, with H(2)=1, H(4) = 2... so the expression for H(6) would be H(4) + H(2)*H(2)+ H(4) = 2+1+2 = 5... Eureka, a Catalan Number. Drawing the graph of H(6) convinced me that I was on the right track.
The upper two images show Point I connecting to a neighbor on his anti-clockwise side leaving the two divisions of the remaining four. The third and fourth show the clockwise neighbor choice leaving H(4)=2 choices again, and the fifth shows the connection with the opposite side, giving only H(2)*H(2) = 1 choice for a total of five.
It seemed the two ideas were related after all so I look at the OEIS web page to see what they had about Catalan numbers . They give, under the Catalan sequence "a(n) is the number of ordered rooted trees with n nodes, not including the root." So Catalan(4) would give the number of trees for a ordered rooted tree with 5 nodes, 14. See the Conway-Guy reference where these rooted ordered trees are called plane bushes." So Catalan(4) would give the number of trees for a ordered rooted tree with 5 nodes, 14.
Farther down there was a note that a(n) is the number of ways of joining 2n points on a circle to form n non-intersecting chords. So H(8) would be a(4)= 14 (Hey that was my approach, I was feeling a little more clever now, and sorry that I ever doubted good ol' Wikipedia).
But then.....
For parts 2) and 3) of the question, it seemed that the number of handshakes with 18 people would be H(18) = Catalan(9) and the OEIS lists Catalan(9) as 4862, which my rough arithmetic background told me might be way more than 280????
And the number of ordered planted trees with 10 nodes would also be Catalan(9) which is still 4862 and still TOOO big to be 280..
SOOOO now I need someone out there who understands this to confirm that what I have above is correct or how I am misinterpreting the Wikipedia article. It didn't give a reference, so I'm not sure who to verify their numbers against.
Ummm HELP!
3 comments:
http://oeis.org/A002995 ought to help convince you that 280 is correct, and you are counting a different thing with your Catalans.
The non-rootedness is the key, I think: we're talking handshake PATTERNS, where things that are equivalent under rotation are considered the same handshake pattern. So for 4 people there's only 1, for 6 your picture shows 2 (three adjacent pairs, or three parallels), and so on.
http://theory.cs.uvic.ca/inf/tree/PlaneFreeTree.html might help a little bit to clarify how we're counting the trees, or it might not.
Josh, Thanks, and maybe they meant this is "Without" rotations, It said including rotations. I'll try to work it out without rotations and reflections
Aha, so they are the same both for rooted (and all handshakes) and for non-rooted trees and non-rotated handshakes.
Much obliged.
Post a Comment