Accueil » Publications » Le Bulletin Vert » Dans nos classes » Compter nos ancêtres en base 2
  APMEP   Compter nos ancêtres en base 2

Article du bulletin 487

Adhérer ou faire un don

Legrand Pierre

De nos jours, quiconque entend parler de numération binaire pense aussitôt à l’informatique. Et pourtant, depuis plusieurs siècles, les généalogistes professionnels et amateurs ont adopté un codage qui est implicitement binaire.

L’idée remonte à l’allemand Michael Eytzinger (1590) ; elle a été reprise en 1676 par Jeronimo de Sosa, franciscain espagnol, dans sa Noticia de la gran casa de los marqueses de Villafranca et popularisée par Stefan Kekule von Stradonitz dans son Ahnentafelatlas [1] (Atlas des arbres généalogiques) de 1898. L’histoire est ingrate. Oubliant Eytzinger, les généalogistes actuels parlent de numérotation de Sosa- Stradonitz ou, plus brièvement, de numéro Sosa d’un ancêtre.

1. Le principe

1.1. Le numéro Sosa

On part d’un individu $D$, traditionnellement appelé le de cujus [2], qui reçoit le numéro 1. Puis on numérote ses ascendants selon la règle suivante : le père et la mère de l’individu numéro n reçoivent respectivement les numéros $2n$ et $2n + 1$.

Ainsi le $n^{o}4$ est le grand-père paternel de $D$, le $n^{o}5$ la grand-mère paternelle, le $n^{o}11$ la mère de celle-ci et ainsi de suite, comme dans le tableau suivant (où les chiffres entre parenthèses représentent l’écriture binaire du numéro Sosa).

1.2. Lien entre le sexe d’un individu et son numéro Sosa

En dehors du $n^{o}1$, les numéros pairs sont masculins, les impairs sont féminins, ce qui en écriture binaire se traduit par un numéro finissant par 0 pour les hommes et par 1 pour les femmes.

Exercice 1 (facile, tiré du Rallye d’Auvergne 2003) : En utilisant uniquement les mots est, le, la, père, mère, du, de, préciser le lien entre le de cujus $D$ et son ascendant $A$ portant le $n^{o}37$.

1.3. Le numéro de génération

On numérote aussi les générations : si un individu appartient à la génération $k$, son père et sa mère appartiennent à la génération $k + 1$. Nous suivrons l’usage le plus courant, qui donne le numéro 1 à la génération du de cujus : ses parents constituent la génération 2, ses grands-parents la génération 3, etc.
À tout ascendant $A$ de $D$, on associera donc un « numéro Sosa » que nous noterons $S(A)$ et un numéro de génération $G(A)$.

1.4. Lien avec la numération binaire

On voit aussitôt que, si on écrit le numéro $n$ de $A$ en base 2, celui de son père $(2n)$ et celui de sa mère $(2n + 1)$ s’obtiennent dans la même base en ajoutant à droite de cette écriture respectivement 0 et 1.

1.5. Implexes

JPEG - 13 ko

Si $D$ descend de $A$ par deux voies différentes, on dit qu’il y a implexe. $A$ (comme bien sûr tous ses ascendants) reçoit deux numéros Sosa. Si en outre ces deux voies sont de longueur différente, il reçoit aussi deux numéros de génération différents.

Exercice 2 (moyen) : Dans le schéma ci-contre, le rond le plus bas représente le de cujus $D$ ; les autres ronds sont gris pour les hommes, blancs pour les femmes ; les flèches vont du fils ou de la fille au père ou à la mère. Quelle propriété particulière possède le personnage marqué $B$ ? Quels sont les numéros Sosa du personnage marqué $A$ ?

Exercice 3 (difficile) : Sachant que la loi française autorise le mariage entre cousins germains, mais interdit [3] le mariage entre frère et sœur, entre oncle et nièce, entre tante et neveu, supposant en outre qu’il n’y a pas de naissance hors mariage dans la famille étudiée, trouver toutes les situations où une ascendante du de cujus a deux numéros différents, inférieurs l’un et l’autre à 16.

2. Quelques questions élémentaires

2.1. Caractérisation des individus appartenant à la génération $g$

Il résulte du § 1, par une récurrence triviale, que les membres de la génération $g$ sont ceux dont le numéro Sosa comporte $g$ chiffres en écriture binaire. Ce sont donc les entiers de $[ 2^{g-1} , ~2^{g}[$. Il y en a $2^{g-1}$, avec cette réserve que certains individus peuvent être comptés plusieurs fois.

Pour trouver la génération $g$ d’un individu de numéro Sosa , il suffit de compter les chiffres de son écriture binaire. Si l’on préfère, on peut observer que l’individu de numéro $s$ appartient à la génération $g$ si et seulement si $2^{g-1} \le s < 2^{g}$ ; il en résulte [4] l’égalité $ g = [log_{2}(s)]+1$.

2.2. Lignée allant de D à un ascendant A de numéro Sosa $a$

On procède dans le sens de $A$ vers $D$ : le descendant immédiat de $A$ dans le tableau porte le numéro $[a/2]$, le descendant immédiat de celui-ci le numéro $[[a/2]/2]$, puis $[[[a/2]/2]/2]$, etc. Ainsi, si $a = 23$, la lignée est $23 \to 11 \to 5 \to 2 \to 1$. Autrement dit le $n^{o}23$ est la mère de la mère de la mère du père de $D$.

Si l’écriture binaire de $S(A)$ est $\overline{1\alpha_{1}\alpha_2\ldots\alpha_{g-1}}$, les descendants successifs de $A$ ont pour numéro $S_{1}(A)=\overline{1\alpha_{1}\alpha_2\ldots\alpha_{g-2}}$, $S_{2}(A)=\overline{1\alpha_{1}\alpha_2\ldots\alpha_{g-3}}$, etc. On a donc l’ensemble des intermédiaires entre le de cujus et un individu de l’arbre en tronquant sur la droite l’écriture binaire du numéro Sosa de ce dernier, d’un chiffre à chaque fois.
Reprenons l’exemple de $S(A) = 23$. En binaire, $23$ s’écrit $\overline{10111}$ ; la lignée est donc $\overline{10111},~\overline{1011},~\overline{101},~\overline{10},~\overline{1}$.

3. Sous- arbres

3.1. Ascendants d’un individu de l’arbre

Soit $A$ un ascendant du de cujus $D$. L’arbre des ascendants de $A$ est formé de tous les $B$ tels que l’écriture binaire de $S(B)$ soit un prolongement de celle de $A$ : si $S(A)$ s’écrit $\overline{1\alpha_{1}\alpha_2\ldots\alpha_{g-1}}$, et si $B$ est un ascendant de $A$, alors l’écriture de $S(B)$ est de la forme $\overline{1\alpha_{1}\alpha_2\ldots\alpha_{g-1}\alpha_{g}\ldots\alpha_{g+m-1}}$.

Autrement dit, ce sont tous les $B$ vérifiant une double inégalité du type

$$2^{m}S(A) \le S(B) < 2^{m}(S(A) + 1)$$

où $m$ est un entier strictement positif, qui indique le nombre de générations nécessaire pour remonter de $A$ à $B$.

Exemple : Si $A$ est la grand-mère paternelle de $D$ (donc $S(A) = 5$), les générations successives de ses ascendants sont les personnes dont le numéro est situé dans $[10, 12[,~ [20, 24[,~ [40, 48[,~ [80, 96[,~ [160, 192[$.

3.2. Un problème de changement d’origine

Si $A$ est un ascendant du de cujus $D$, de numéro Sosa $S(A)$ et si $B$ est un ascendant de $A$ de numéro Sosa $S_{A}(B)$ par rapport à $A$, quel est son numéro Sosa par rapport à $D$ ?

En écriture binaire, on voit immédiatement qu’il suffit pour avoir la réponse de mettre à droite de $S(A)$ le numéro $S_{A}(B)$ privé de son $1$ initial. Par exemple, si $S(A) = 6$ et $S_{A}(B) = 25$, cela donne en écriture binaire $S(A) = \overline{110}$ et $S_{A}(B) = \overline{11001}$, donc $S(B) = \overline{1101001}$, c’est-à-dire $S(B) = 64 + 32 + 8 + 1 = 105$.

Trouver une formule générale non liée au système de numération demande un petit effort. On commence d’abord par chercher le nombre de générations nécessaires pour remonter de $A$ à $B$, qui est $ G_{A}(B) = \left [ log_{2} \frac{S(B)}{S(A)} \right ] $. On établit ensuite la formule :

$$ S(B) = 2^{G_{A}(B)}(S(A)-1) + S_{A}(B) $$

qui règle la question et dont nous laisserons traîtreusement la justification au lecteur.

Conclusion

Ce thème des arbres généalogiques est, comme nous avons essayé de le montrer, source d’exercices à différents niveaux allant de la sixième à la terminale. Il peut constituer une introduction plaisante aux arbres que l’on rencontre dans les problèmes de dénombrement ou de probabilités.

Qui d’entre nous, en outre, n’a déjà rencontré au moins un généalogiste amateur ? Il y en aurait une centaine de milliers en France et des millions dans le monde … ne seraient-ce que les Mormons [5].

Annexe : solution des exercices

Exercice 1 : Le $37$ est la mère du $18$, qui est le père du $9$, qui est la mère du $4$, qui est le père du $2$, qui est le père du $1$.

Exercice 2 : Le personnage B est le père à la fois du grand-père paternel et de la grand-mère maternelle de $D$, mais il les a eus de deux femmes différentes. Le personnage $A$ a six numéros Sosa différents : $138, 140, 154, 234, 236, 244.$ Il suffit pour le voir de remonter depuis $D$ en suivant le sens des flèches, de génération en génération.

Exercice 3 : L’ascendante « double » $A$ ne peut être par deux voies différentes une grand-mère du de cujus $D$, car alors les parents de $D$ seraient frère et soeur. C’est donc au moins par une des deux voies une arrière-grand-mère, puisque ses numéros sont inférieurs à $16$.

Premier cas : $A$ est par deux voies une arrière-grand-mère de $D$. De ces deux voies, l’une passe par le père $P$ de $D$, l’autre par sa mère $M$. En effet, si par exemple les deux passaient par $P$, ce dernier descendrait de sa grand-mère par deux voies différentes ; on vient de voir que c’est impossible. $A$ est donc à la fois la grand-mère de $P$ et celle de $M$, ce qui donne les quatre schémas possibles ci-dessous :

Le schéma de gauche, par exemple, se traduit ainsi : $A$ a eu deux fils $F$ et $G$ ; un fils de $F$ a épousé une fille de $G$ et de cette union de cousins germains est né $D$.

Second cas : $A$ est par une voie arrière-grand-mère de $D$ et par l’autre grand-mère de $D$. Supposons par exemple que la voie courte passe par la mère $M$ de $D$. $M$ a épousé $P$, qui est le petit-fils du père $A$ de $M$, autrement dit le fils d’un frère ou d’une sœur de $M$. $M$ a ainsi épousé son neveu, ce qui est exclu par la loi. Ce second cas aboutit à une impossibilité.

JPEG - 5 ko

Mais, selon l’article 164 du code civil, l’interdiction d’épouser un neveu ou une nièce peut être levée « pour des causes graves » par le Président de la République.

La configuration ci-contre est donc exceptionnelle sans être véritablement impossible. On vérifie qu’elle donne pour $A$ les couples de numéros $(9,7)$ et $(11,7)$, la configuration obtenue en permutant $M$ et $P$ sur le schéma donnant $(13,5)$ et $(15,5)$.

(Article mis en ligne par Didier Trotoux)

[1] Ahnen, ancêtres ; tafel, tableau

[2] Forme abrégée du latin Is de cujus successione agitur (celui de la succession duquel il est question), expression venue du monde des notaires, où elle est encore en usage.

[3] Articles 161 à 163 du code civil.

[4] Dans tout ce qui suit [x] désigne la partie entière de x.

[5] Selon eux, un individu est sauvé s’il est enregistré, de son vivant ou à titre posthume, dans un de leurs temples. Pour un Mormon, connaître sa lignée et la faire inscrire est un impérieux devoir.


 Accueil   Plan du site   Haut de la page   Page précédente