En mathématiques, un système de numération bijectif est un système de numération qui établit une bijection entre l'ensemble des entiers naturels et l'ensemble des chaînes finies de « chiffres », pris parmi un ensemble fini. En particulier, la numération bijective en base k représente un entier par une chaîne de chiffres de l'ensemble {1, 2..., k} (k ≥ 1), codant le développement de l'entier en puissances de k La numération ordinaire en base k ne répond pas à cette définition. Par exemple, en base décimale ordinaire, toutes les suites de longueur supérieure ou égale 2 sont l'image d'un nombre entier : ainsi le nombre 1957 a pour image la suite (1,9,5,7). Comme un système de numération est injectif, la suite (1,9,5,7) n'est l'image que du nombre "1957". Mais, par conséquent, les suites (0,x), ou plus généralement toute suite de longueur supérieure à 1 commençant par "0", ne peut être l'image d'aucun entier.. La numération bijective en base k est aussi appelée notation k-adique, à ne pas confondre avec le système des nombres p-adiques. En base 1, on parle de système unaire.

Définition Le système de numération k-adique utilise l'ensemble des chiffres {1, 2, ..., k} (k ≥ 1) pour représenter chaque entier de manière unique, selon les règles suivantes : L'entier zéro est représenté par la chaîne vide. La chaîne de chiffres non vide aa ... aa représente, en numération k-adique, l'entier qui vaut :

Tout entier naturel possède une représentation unique en numération bijective de base k (k ≥ 1) comme démontré par Smullyan pour le cas k = 2, Böhm (1964) pour tous les k ≥ 1Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P"., Knuth pour k = 10, ou encore Salomaa pour k ≥ 2. Une démonstration simple est donnée ci-dessous.

Certains historiens des mathématiques estiment que d'anciens systèmes de numération auraient pu être bijectifs, donc sans utilisation du zéro.

Propriétés des nombres écrits en système bijectif

Notation bijective ou usuelle des nombres en base k Les tableaux ci-dessous donnent quelques exemples de différences de notation de nombres pour différentes bases k entre systèmes usuel et bijectifPour les numérations bijectives de bases k comprises entre 10 et 35, il est d'usage courant d'utiliser les lettres successives de l'alphabet pour désigner les chiffres suivant 9. Par exemple, un système hexadécimal bijectif utilise les seize chiffres {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}. Un système hexadécimal non bijectif utilise les seize chiffres {0,1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}.. +Base10Décimal usuel129101120213099100101110111200100010 bijectif129A111A212A999AA1AA11119A99A +Base5Décimal usuel124569101115202530315 usuel124101114202130401001101115 bijectif12451114152125354555111 +Base3Décimal usuel12348910121318303 usuel121011221001011101112003103 bijectif1231122233133111123233 +Base2Décimal usuel123456789111516Binaire usuel110111001011101111000100110111111100002 bijectif121112212211111212121111111112 On remarque :

qu'un nombre qui s'écrit sans utiliser de zéro en système usuel s'écrit de façon identique en système bijectif, mais qu'il s'écrit différemment dans le cas contraire ; que la longueur d'un nombre en notation bijective est inférieure ou égale à celle qu'il a en notation usuelle.

D'autres exemples sont donnés ci-dessous : (34152) = 3 × 5 + 4 × 5 + 1 × 5 + 5 × 5 + 2 × 5 = (34152) = (2427).

(119A) = 1 × 10 + 1 × 10 + 9 × 10 + 10 × 10 = (1200).

Propriétés Pour un k donné ≥ 1, il y a exactement k nombres k-adiques de longueur n ≥ 0. si k > 1, le nombre de chiffres du nombre k-adique représentant un entier non négatif n est E(log(n+1)), contrairement à E(log(n)+1) (n > 0) pour la numération ordinaire en base k ; si k = 1 (donc en numération unaire), alors le nombre de chiffres est n ; une liste de nombres k-adiques, classée dans l'ordre naturel des entiers représentés, est classée par ordre de longueur, puis, pour chaque longueur donnée, par ordre lexicographique.

Système décimal sans zéro Le système bijectif en base dix est aussi connu sous le nom de système décimal sans zéro . Il utilise généralement les chiffres de 1 à 9 et un chiffre supplémentaire, "A", pour représenter dix.

L'addition et la multiplication en système décimal sans zéro utilisent essentiellement les mêmes règles que dans le système usuel, si ce n'est que les retenues se produisent quand un résultat dépasse dix, au lieu de neuf. Ainsi, pour calculer 643 + 759, il y a douze unités (on écrit 2 à droite et on retient 1), dix (9+1) dizaines (on pose A et on ne retient rien), treize centaines (on pose 3 et on retient 1), et un millier, d'où le résultat 13A2, différent de la notation usuelle 1402.

Système bijectif en base 26 Le système bijectif en base 26 est aussi connu sous le nom de base 26 sans zéro. Plutôt que d'utiliser les chiffres de 1 à 9 complétés des 17 premières lettres de l'alphabet, il est d'usage d'utiliser comme « chiffres » les 26 lettres de l'alphabet (de "A" à "Z") pour représenter les nombres de 1 à 26.

La suite des nombres est donc A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ..., ZY, ZZ, AAA, AAB, AAC, ... C'est de cette manière que beaucoup de tableurs tels que Microsoft Excel identifient les colonnes de leurs feuilles de calcul. Par exemple, dans Excel 2013, il est possible d'utiliser jusqu'à 16384 colonnes, nommées de A à XFD.

Chaque position de chiffre représente une puissance de vingt-six ; ainsi, par exemple, ABC est "une fois 26^2, plus deux fois 26^1, plus trois unités (26^0)" puisque "A" vaut un, "B" vaut deux, et "C" vaut trois.

Dans cette représentation, le nombre WIKIPEDIA est : 23 × 26 + 9 × 26 + 11 × 26 + 9 × 26 + 16 × 26 + 5 × 26 + 4 × 26 + 9 × 26 + 1 × 26 = 4878821185187

Une variante de ce système est partiellement utilisée pour nommer les étoiles variables.

Plus généralement, le système bijectif à base 26 peut être utilisé chaque fois qu'on désire une nomenclature systématique n'utilisant que des lettres avec les chaînes de caractères les plus courtes possible.

Notes et références

Sources Böhm, C. "On a family of Turing machines and the related programming language", ICC Bulletin 3, p. 191, July 1964.

Bibliographie

,

Catégorie:Numération