Number of Relatives

19.09.2022

Anyone who is involved in genealogy may have asked themselves how many ancestors there are or how many people you are related to. If one assumes that every human being has two physical parents (meanwhile, there are children who have 3 parents, but this case is not considered here) then the calculation of the direct ancestors is quite simple. Each person has 2 parents, 4 grandparents, 8 great-grandparents, etc. That means there are 2^n ancestors in the n-th generation.

Charlemagne was born around the year 748 - that is 1274 years ago. Genealogists put an average of 30 years on a generation, so he lived more than 42 generations ago. If one looks back until this time each of us would have 2^42 ancestors - an unimaginably large number, which goes into trillions. However, in Central Europe lived at this time no more than 50 million people. How can that be?

The reason therefore is called Pedigree collapse. This typically happens if relatives have children together. The descendants have then less ancestors than the maximum possible number.

Genetically related individuals

Genetically related individuals are defined as all individuals who are related to each other through common biological ancestors. This includes direct ancestors (parents, grandparents, great-grandparents, etc.) and direct descendants (children, grandchildren, great-grandchildren, etc.). as well as siblings, half-siblings, uncles and aunts, nieces and nephews, cousins, and other distant relatives.

Calculating the number of genetic related people

In our theoretical calculation of the number of all genetic related people up to a past generation n we assume idealized conceptions: On the one hand, we ignore the loss of ancestors, on the other hand we assume that each pair of parents has exactly k children. In addition, we require that the individual in question and other relatives of the same generation do not (yet) have any children.

Let's consider the example with k=2

Generation 0: Person themself = 1 relative
Generation 1: 2 parents (G1) + 2 children (G0) = 4 relatives
Generation 2: 4 grandparents (G2) + 4 children (G1) + 6 children (G0) = 14 relatives
Generation 3: 8 great-grandparents (G3) + 8 children (G2) + 12 children (G1) + 22 children (G0) = 50 relatives
Generation 10: As you can see, the numbers are growing rapidly. After 10 generations there would be 1024 (2^10) ancestors over which one would be genetic related to 700074 people.

Another example with k=3

The person themself as well as the direct ancestors are shown in black, the persons with which one is also genetically related in red. If each couple has 3 children, then in addition to the direct ancestors there are also 2 siblings, 4 uncles and/or aunts and 12 cousins, resulting in a total of 25 (7 + 18) genetically related people.

Mathematical formula

Without regarding the formula in more detail, the number of all relatives for n generations and k children (k >= 2) can be calculated by the following sum formula:
R(n,k) = Sum[i=0..n]2^n + Sum[i=1..n]2^(i-1)*((k^i)-1)
This sum can also be calculated directly using the following formula:
R(n,k) = 2^n+(k*(2*k)^n-k)/(2*k-1)

Number series

For different numbers of children k, the following series of numbers result for generations 0 to 10:

k=1: 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047 (The person themself plus the number of direct ancestors)
k=2: 1, 4, 14, 50, 186, 714, 2794, 11050, 43946, 175274, 700074
k=3: 1, 5, 25, 137, 793, 4697, 28057, 168089, 1008025, 6047129, 36280729
k=4: 1, 6, 40, 300, 2356, 18756, 149860, 1198500, 9587236, 76696356, 613567780
k=5: 1, 7, 59, 563, 5571, 55587, 555619, 5555683, 55555811, 555556067, 5555556579
k=6: 1, 8, 82, 950, 11326, 135758, 1628782, 19544750, 234535726, 2814426158, 33773108782
k=7: 1, 9, 109, 1485, 20701, 289629, 4054429, 56761245, 794655901, 11125179549, 155752507549

Explicit formulas

k=1: a(n) = 2^n + 1*( 2^n - 1)/ 1
k=2: a(n) = 2^n + 2*( 4^n - 1)/ 3
k=3: a(n) = 2^n + 3*( 6^n - 1)/ 5
k=4: a(n) = 2^n + 4*( 8^n - 1)/ 7
k=5: a(n) = 2^n + 5*(10^n - 1)/ 9
k=6: a(n) = 2^n + 6*(12^n - 1)/11
k=7: a(n) = 2^n + 7*(14^n - 1)/13

Program in Python to generate the number series

for k in range(1,8):
  l=[];
  for n in range(0,11):
    v = 2**n+(k*(2*k)**n-k)//(2*k-1)
    l.append(int(v))
  print(l)

References

k=1: OEIS Serie A000225
k=2: OEIS Serie A076024
k=3: OEIS Serie A358504
k=4: OEIS Serie A358598
k=5: OEIS Serie A358599
k=6: OEIS Serie A358600
k=7: OEIS Serie A358601

Interesting

Reagarding the case k=5 minus the number of ancestors of the n-th generation (n >= 1), we get the number series 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555, ... (OEIS Serie A002279)