*there is virtually no chance that anyone of European ancestry
is not directly descended from Charlemagne.*

Here's my reasoning. Charlemagne was approximately 40 generations back
from the present day. Each person has 2 parents, 2^{2} = 4 grandparents,
2^{3} = 8 great-grandparents, ... and 2^{40}, or approximately
1,000,000,000,000 (one trillion), 40th-generation ancestors, which means
half a trillion male ancestors. Of course, since the entire male population
of Europe at the time of Charlemagne was only about 15 million, these
half trillion ancestors cannot all have been different men -- obviously
there has been a lot of cross-breeding, and many of our ancestral lines
cross and re-cross, eventually ending up at the same person. Let's assume
that each of my 40th-generation male ancestors is a randomly-chosen man
from eighth-century Europe (this is not really valid, but more on that
below). Choosing any one such ancestor, say my father's father's ... father's
father, the probability that that particular person is Charlemagne is one
in 15 million. Pretty small. To put it another way, the probability that
any particular ancestor was *not* Charlemagne is 1 - 1/15,000,000,
or approximately 0.999999933

But now consider the probability that *none* of my 40th-generation
ancestors is Charlemagne. For that to happen, *every one* of my half
trillion male ancestors has to not be Charlemagne, which would be an amazing
coincidence. To see how amazing, let's compute the probability. Assuming
all of these various not-being-Charlemagne occurrences are independent
of each other (more on this below), the laws of probability state that
the probability of all these events occurring simultaneously is obtained
by multiplying together their individual probabilities:

(0.999999933)·(0.999999933)·...·(0.999999933) =
(0.999999933)^{500,000,000,000}.

This turns out to be an incredibly small number: about one chance in
10^{15,000}. That's a one with 15,000 zeroes after it, a number
that's too big even to display in a browser window. This is way more than
the number of atoms in the universe (which is estimated to be about 10^{80}).
Therefore, if this analysis is even remotely close to correct, it's virtually
impossible that Charlemagne is not among my direct ancestors.

Of course, there are a few sources of errors in this analysis, so there are various corrections one could make that might yield a more accurate estimate. Most obviously, one's ancestors are not in fact randomly chosen people from eighth-century Europe. For example, anyone who had no children, or no grandchildren, cannot be an ancestor of someone living now. (Charlemagne has well-documented descendants down to the present day.) More generally, wealthy people survived at a far higher rate than the rest of the population, and so were much more likely to produce descendants - thus one's ancestors are more likely to be found among the relatively small population of royalty and nobility, including Charlemagne. You might think of other, smaller, corrections, such as the fact that the probabilities of different ancestors being Charlemagne are not really independent: for example, if my father's ... father's father was Charlemagne's brother, then the probability that my father's ... mother's father was Charlemagne himself is very small. And, of course, some of my ancestors came from outside of Europe. But I believe these effects cannot change the fact that the probability we're talking about is so tiny as to be zero for all practical purposes.

--Jack Lee