When you draw a tree of your ancestors, things quickly get out of hand. There are twice as many nodes each time you go back a generation, and so the size of paper you need grows exponentially. Things also get messy because typically you know much more about some lines than others. If you know much about your ancestry, one big tree isn’t going to work.
There’s a simple solution to this problem, one commonly used in genealogy: assign everyone in the tree a number, starting with yourself as 1. Then follow two simple rules:
- The father of person n has number 2n.
- The mother of person n has number 2n + 1.
You can tell where someone fits into the tree easily from their number. Men have even numbers, women odd numbers. The number of someone’s child is half their number (rounding down if you get a fraction). For example, person 75 on your tree must be a woman. Her husband would be 74, her child 37, her father 150, etc.
Taking the logarithm base 2 tells you how many generations back someone is. That is, person n is ⌊ log2n ⌋ generations back. Going back to our example of 75, this person would be 6 generations back because log2 75 = 6.2288. (Here ⌊ x ⌋ is the “floor” of x, the largest integer less than x. Using the same notation, the child of n is ⌊ n/2 ⌋.)
Said another way, the people m generations back have numbers 2m through 2m+1 – 1. Your paternal line has numbers equal to powers of 2, and your maternal line has numbers one less than powers of 2.
If you write out a person’s number in binary, you stick a 0 on the end to find their father and a 1 on the end to find their mother. So your paternal grandmother, for example, would have number 101 in binary. Start with your number: 1. Then tack on a zero for your father: 10. Then tack on a 1 for his mother: 101.
In our example of 75 above, this number is 1001011 in binary. Leave off the one on the left, then read from left to right saying “father” every time you see a 0 and “mother” every time you see a 1. So person 75 is your father’s father’s mother’s father’s mother’s mother.
This numbering system goes back to at least 1590. In that year Michaël Eytzinger published the chart in the image above, giving the genealogy of Henry III of France.
For some designated value of “father” and “mother”. Same sex couples, adoptions, polygamy all make this scheme useful but not complete.
This is biological ancestry. There’s no ambiguity. Everyone has one father and one mother.
The only complication is that eventually you’ll run into someone with two numbers: eventually 2^n is larger than the world population, so there has to be some repetition. Even so, if a person has two numbers, each describes how that person functions in a particular part of the tree.
Even ignoring the relationships mentioned by Matt Doar, how does this handle siblings? What is your niece’s or nephew’s number?
This scheme only handles ancestors. There are other numbering schemes for handling descendants, but I’m not familiar with them.
My question is the same as Michael P’s. Every serious genealogist I know enjoys tracing collateral lines to find modern day cousins. How to accommodate that?
I think the point of the post was how to number trees, not genealogy as such.
In reality this scheme falls apart fairly quickly for various reasons. You typically only have to go back a few generations for the tree to recross itself for instance; and in practice you want to track step-parents, half-siblings and the like as well.
What about cycles? http://stackoverflow.com/questions/6163683/cycles-in-family-tree-software
You can’t really have cycles, but you can have repetition. And as I mentioned above, repetition is inevitable if you go back far enough. Ideally the repetitions aren’t too close together.
This is just the standard representation of complete binary trees via arrays. For exampe, the usual implementations of most heap algorithms work with such data structure.
You can have cycles if you aren’t an eucaryote. And I don’t know if not some branches within that kingdom can’t have it as well.
But for genealogy the societal connections – marriages and so on – are as important as the narrow biological lineage. And even without that, the biological structure is clearly a DAG rather than a tree. And even if we ignore that, we still carry two separate lineages with different heritability mechanisms.
Repetitions or re-used numbers for the same person is better known as Pedigree Collapse – https://en.wikipedia.org/wiki/Pedigree_collapse
As Omer mentioned, this is a fairly well-known scheme for storing a binary tree in a linear array.
https://en.wikipedia.org/wiki/Binary_tree#Arrays
Curious, how can I count number of generations from Gov. WIlliam Bradford (b 1590, d 1657) to present (2016)? My father (b 1935) says he is a 9th direct descendant, but that doesn’t seem to have enough generations. Is there a helpful genealogy site that isn’t a monthly subscription to access?