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, and so on. 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.

PGRIT: Calculating the number of genetically related individuals

In our theoretical calculation of the number of all genetically related individuals up to a past generation n we we start with idealized assumptions: 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 (generation level 0) do not (yet) have any children. We call such a tree PGRIT (Perfect Genetically Related Individuals Tree).

Let's consider an 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 central person 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 central person and the direct ancestors there are also 2 siblings, 4 uncles and/or aunts and 12 cousins, resulting in a total of 25 genetically related individuals.

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

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

Classifying PGRITs

Perfect genetically related individuals trees (no loss of ancestors and every couple has the same number of children) are defined by the number of generations and the number of children. So a tree with n generations where each couple has k children would be classified as (n,k)‑PGRIT.

Perspective view of PGRITs

A planar graph is defined as a graph that can be drawn in the plane such that its edges do not intersect. Trees are a special subclass of planar graphs. They are defined as a connected graph without cycles (no closed paths), i.e. every perfect genetically related individuals tree is automatically planar and since it contains no cycles it can therefore always be drawn without intersections.

If you want to draw a perfect genetically related individuals tree with more than 3 generations where each generation is on the same level, intersections can not be avoided as the following illustration with a (3,2)‑PGRIT shows (note that the generation count always starts at 0).

If you choose a perspective view it should be possible to draw perfect genetically related individuals trees without intersection. Another possibility to present such trees without intersection are 3D-views.

Numbering Systems for ancestors and descendants

In genealogy the Kekulé system, as well as the Aboville, Saragossa, Henry or Pence system (and others) often use a number/letter code to list the ancestors or descendants of a specific individual.

The Kekulé numbering system is used to number direct ancestors in an ancestral chart: the starting individual is assigned the number 1, their father the number 2, and their mother the number 3. A parent's number is determined by doubling the child's number for the father or doubling it and adding one for the mother. Siblings share the ancestor's number, supplemented by a lowercase letter suffix, e.g. 2a for the father's brother.

Aboville is a method for numbering descendants. The system uses an alphanumeric code in which the first character is a letter indicating the generation. Children are numbered sequentially using Arabic numerals. Each child inherits the parent's code and appends their own number, e.g. C1.1.3.

Saragossa is similar to Aboville but often uses a modified or extended numerical format. It typically numbers children sequentially and appends the number to the parent's identifier, sometimes distinguishing spouses with letters or using a specific index for the starting individual.

The Henry system is another system for numbering descendants. It assigns a digit to each successive generation, starting from an arbitrary ancestor. For example, the progenitor might be the number 1, his children 2.i, 2.ii, and his grandchildren 2.i.1, 2.i.2 and so on. If a generation comprises more than nine children, the system uses letters or continues the numbering with multi-digit numbers to maintain clarity.

The Pence system is a modification of the Henry system. It is distinguished by the fact that no letters are used for children after the 10th position, and generations are separated by periods. An example of this numbering is 1.3.10.1, which represents the first child of the 10th child of the third child of the most recent ancestor 1.

The Generation-Sibling-System (GS-System)
An innovative numbering method for genetically related individuals

The newly introduced numbering method assigns a unique code to each genetically related individual. The code consistently uses numbers (no letters) and two separators (. and _) only, does not favor any particular parent like a progenitor, and is based on generations and siblings mainly. The system is suitable for numbering a wide variety of representations of genetically related individuals, such as family trees, ancestor galleries, pedigree charts, etc.

The logical structure of the system is built on numbering generations and individuals within a generation, identifying siblings, and arranging descendants of siblings in a sequential numerical order. The advantage of the GS-System is that the generation and ranking of individuals can be grasped at a glance, allowing users to easily trace paths and quickly identify kinship relationships.

As shown in the figure below, the code for the central person (dark gray) and all ancestors (blue) consists of two numbers: the first number indicates the generation, the second number designates the person within that generation. The central person and the ancestors pass their code to their siblings (green). Separated by an underscore, an additional number - determined by birth order - is appended to each sibling. The designation for the descendants of these siblings (red) is extended by a period and another number, which is also based on birth order. Further descendants are numbered according to the same scheme by adding periods and numbers (1.1_1 ⇨ 1.1_1.1 ⇨ 1.1_1.1.1 ⇨ 1.1_1.1.1.1 etc.).

Children of the central person, half-siblings and several partner

If the system is to be expanded so that the central person's children are also numbered, it must be ensured that the code remains unique. If only an underscore is used for separation, the code for the central person's first child (0.1 ⇨ 0.1_1) would be identical to the code for the central person's first sibling (0.1_1). To avoid this conflict, the central person is considered the second sibling, and the code is unique again (0.1_2 ⇨ 0.1_2.1).

If half-siblings exist and need to be distinguished from other siblings, the separator could be doubled, e.g. 0.1__1, 1.1__2, etc. In this case the first sibling of the central person and the second sibling of the central person's father would be half-siblings.

If a person has been married more than once or has had several partners, this can be indicated by double periods e.g., 1.1..1, 1.1..2, and so on. In this case, the father of the central person had children with two different partners.