In genealogy, a pedigree chart, which shows one's direct ancestors (parents, grandparents, etc. but not siblings, cousins, etc.) is often replaced by the equivalent but space-saving Ahnentafel table.

An Ahnentafel table is simply a numbered list of each ancestor, usually on separate lines. The "root" person goes on line 1. Then, for any person on line n, his father goes on line 2n and his mother goes on line 2n+1. Every ancestor gets a unique line, and every line gets a unique ancestor* (mathematically, at least -- in real life Ahnentafels, because a person may not know all of his ancestors some lines may be blank, and in the case where cousins married, their common ancestors may show up in several places in their children's Ahnentafels).

Question 1: Your great-great-grandfather(2nd-great-grandfather) was the first of his name (surname) (which you inherited) to come to America. What is his Ahnentafel number? What is the Ahnentafel number of your nth-great-grandfather of the same name?(Assume the the Western tradition where a child inherits his father's surname)

Question 2: Your Mitochondrial DNA is passed on only from your mother, who got it from her mother,etc. What is the Ahnentafel number of the great-grandmother from whom it "originally" came? Of the nth-great-grandmother?

[Hint: for the general case (nth-great-grandfather in question 1, nth-great-grandmother in question 2) it might be easier to work with m=n+2; m is the number of generations between the ancestor and your children. For n=1 (your great-grandfather), m=3 -- three generations in between: your grandfather, your father, and you.]

*This statement (that there is a one-to-one correspondence between Ahnentafel numbers and the set of all natural numbers) is fairly easy to prove. And, in fact, the proof is part of a later puzzle in this series. For this puzzle, it can simply be assumed.

(In reply to re(2): Thanks heaps! by Federico Kereki)

<If you want to be picky, a pedigree chart ISN'T a binary tree, because an ancestor might appear in more than one place. In a tree (binary or otherwise) there should be one and only one way to get from the root to any node.>

I really don't want to be picky but since you brought this up, it seems to me you are confusing a node and its data. According to "The Bible" (Knuth vol 1, that is): "More formally, let us define a binary tree as a finite set of nodes which either is empty, or consists of a root and two disjoint binary trees called the left and right subtrees of the root." (From page 309, and see also Fig. 19 of the previous page.) This seems to me to cover a person's family tree even if papa=grandpa.

Posted by Richard on 2004-04-13 13:38:54