How to calculate rooted bifurcatingtree shapes

(Uniduni Te) #1

Hi friends!

I’m studying about phylogenetic tree shapes. Most precisely about calculate all possible rooted bifurcatingtree shapes (not labeled). A book of Felsenstein named “Inferring Phylogenies” gives an algorithm to calculate that, but I don’t understand how to.

The book provides a calculation as follows:

But my calculations does not match with following values table showed on the book.

can anybody help me with a step by step example??

(Randy) #2

I can’t, but maybe @pevaquark, @glipsnort, @jammycakes , @T_aquaticus ? I defer to greater studiers in this area. Thanks

PS I think @swamidass at Peaceful Science ( loves that stuff too.

(Mervin Bitikofer) #3

Yes I can. With the formulas you supply and given that S1 = 1, the first half dozen results followed the expected list you gave above, which is as far as I went. Was there a particular result where your discrepancies started?

One thing to keep in mind is that in the early results (such as S2 or S3) you only have one term to consider - and that is the final term given. (In other words, don’t use S1 twice.)

Added edit to provide actual process, showing actual sequences:
odd : s1 = 1
even: s2 = s1*(s1 + 1)/2 = 1
odd : s3 = s1 * s2 = 1
even: s4 = s1 * s3 + s2*(s2 + 1)/2 = 2
odd : s5 = s1 * s4 + s2 * s3 = 3
even: s6 = s1 * s5 + s2 * s4 + s3*(s3 + 1)/2 = 6
odd : s7 = s1 * s6 + s2 * s5 + s3 * s4 = 11

Do you see the pattern emerging in the process?

(Uniduni Te) #4

very thanks!

(Randy) #5

Wow, terrific! Thanks @Mervin_Bitikofer

(Uniduni Te) #6


Very thanks my friend!
Your explanation was very clear!

The discrepancy occurs on s3. In this case, shouldn’t I use s1*s(3-1) term followed the last term as in the figure below?

For s3, it didn’t have to use two terms on the somatory sequence, as we seen in the double factorial?
The organization and distribution of terms of this sequence isn’t based on the double factorial?
1!! = 1
2!! = 2
3!! = 1 * 3
4!! = 2 * 4
5!! = 1 * 3 * 5
6!! = 2 * 4 * 6
7!! = 1 * 3 * 5 * 7

(Mervin Bitikofer) #7

The last term (for both even and odd cases) is by definition the end of the sequence. So if your first term’s subscripts match the last terms defined values, then your first term and last term are one and the same - which is the case for both s2 and s3.

So in short, no. For your s3 term it should only be one occurrence of the term: s1 * s2 (which is both the first and last term of that series.)

I can’t speak to how double factorials or somatory sequences relate to this as those are beyond my regular domain of mathematical experience. I’m simply and strictly applying the summation formulas you provided at first.

(Uniduni Te) #8

I understand.
Anyway your answer was perfect and saved my life.
I say again: Very thanks!!!


It seems that the question has been answered, but there is a handy calculator over at Talkorigins if anyone is interested:

The calculator uses the following formula:

NR = (2n-3)!! = (2n-3)!/(2n-2(n-2)!)

(Uniduni Te) #10

Very thanks my friend!
But this calculation presented by you is for rooted, bifurcating, labeled trees.
My question is about rooted, bifurcating unlabeled trees.

Thanks anyway!!