# 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.

## Calculating the number of genetic relative people

In our theoretical calculation of the number of all genetic relative 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.

**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 as shown in this genealogical table. With
a generation depth of n=2 (generation 0,1 and 2) this results in a total of 25 genetically related persons.

## 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)

## Interesting

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

## 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

See also

OEIS Serie A000079

OEIS Serie A002279