# The Charlemagne Riddle and Pedigree Collapse

Robert Krulwich recounts a story/riddle about a guy who discovered he was related to Charlemagne the Great. But was he? He went to class one day, where the teacher had a lesson on genealogy:

The teacher says if you count your direct ancestors backward through time, the further back you go, obviously, the more ancestors you have. But when you do the numbers, something queer happens.

Go back to A.D. 800, he said, and the number of direct ancestors is, well, puzzling. You start with two grandparents, then four great-grandparents, then on to eight, 16, etc., and by the time you get to A.D. 800, the number averages to about 562,949,953,421,321. That’s a lot of people. In fact, that’s more people than have ever lived.

So if you go far back enough in history, everyone is related to Charlemagne. This answer is justified with the so-called pedigree collapse:

Without pedigree collapse, a person’s ancestor tree is a binary tree, formed by the person, the parents (2), the grandparents (4), great-grandparents (8), and so on. However, the number of individuals in such a tree grows exponentially and will eventually become impossibly high. For example, a single individual alive today would, over 30 generations going back to the High Middle Ages, have 230 or roughly a billion ancestors, more than the total world population at the time.

This apparent paradox is explained by shared ancestors. Instead of consisting of all unique individuals, a single individual may occupy multiple places in the tree. This typically happens when the parents of an ancestor are cousins (sometimes unbeknownst to themselves). For example, the offspring of two first cousins has at most only six great-grandparents instead of the normal eight. This reduction in the number of ancestors is pedigree collapse. It collapses the ancestor tree into a directed acyclic graph.

In some cultures, cousins were encouraged or required to marry to keep kin bonds, wealth and property within a family (endogamy). Among royalty, the frequent requirement to only marry other royals resulted in a reduced gene pool in which most individuals were the result of extensive pedigree collapse

So next time someone says they’re a direct descendant of someone, say, who was born before 1600, be highly, highly skeptical.