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, 22 = 4 grandparents, 23 = 8 great-grandparents, ... and 240, 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 1015,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 1080). 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.