Voir la source de Système de numération bijectif

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 [[entier naturel|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'' <ref>La [[Notation positionnelle|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.</ref>. La numération bijective en base ''k'' est aussi appelée '''notation ''k''-adique''', à ne pas confondre avec le [[nombre p-adique|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 ''a''{{ind|''n''}}''a''{{ind|''n''−1}} ... ''a''{{ind|1}}''a''{{ind|0}} représente, en numération k-adique, l'entier qui vaut : 
{{Centrer|''a''{{ind|''n''}} ''k''{{exp|''n''}} + ''a''{{ind|''n''−1}} ''k''{{exp|''n''−1}} + ... + ''a''{{ind|1}} ''k''{{exp|1}} + ''a''{{ind|0}}}}

Tout entier naturel possède une représentation unique en numération bijective de base ''k'' (''k'' ≥ 1) comme démontré par [[Raymond Smullyan|Smullyan]] pour le cas ''k'' = 2{{Sfn|Raymond Smullyan|1961}},  [[Corrado Böhm|Böhm]] (1964) pour tous les ''k'' ≥ 1<ref>Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P".</ref>, [[Donald Knuth|Knuth]]  pour ''k'' = 10{{Sfn|Donald Knuth|2007}}, ou encore [[Arto Salomaa|Salomaa]] pour  ''k'' ≥ 2{{Sfn|Arto Salomaa|1973}}. Une démonstration simple est donnée ci-dessous.
{{Démonstration|contenu=En nous inspirant de la construction d'un nombre  en [[Base (arithmétique)|base <math>k</math>]] usuelle<ref>{{Lien web |titre=Représentation des réels |url=https://www.alloschool.com/assets/documents/course-283/representation-des-reels.pdf |format=pdf |site=Alloschool |consulté le=15 mars 2023}}</ref>, démontrons que quel que soit l'entier naturel non nul <math>k</math>, tout entier naturel <math>n</math> non nul a une, et une seule, décomposition de la forme : <math>n= a_0+a_1\times k+a_2\times k^2+...+a_p\times k^p</math> où les <math>a_j</math> sont des entiers naturels non nuls inférieurs ou égaux à <math>k</math>.

Démontrons d'abord que si <math>n</math> a une telle décomposition, elle est unique. Raisonnons par récurrence: si <math>n</math> a deux décompositions notons les <math>(a_p,...a_1,a_0)</math> et <math>(b_q,...b_1,b_0)</math>, et démontrons que <math>b_0=a_0</math>.

Si <math>n</math> n'est pas divisible par <math>k</math>, le reste de sa division par <math>k</math> est <math>a_0</math> mais aussi <math>b_0</math>. Donc :  <math>b_0=a_0</math>. Si <math>n</math> est divisible par <math>k</math>, alors <math>a_0=b_0=k</math> (car aucun <math>a_j</math> ou <math>b_j</math> ne peut être nul). Donc, dans tous les cas : <math>a_0=b_0</math>. Si <math>n=a_0=b_0</math>, alors <math>n</math> ne peut avoir que la représentation (<math>a_0</math>), car <math>n</math> est strictement inférieur à tout nombre représenté par un chaine de longueur supérieure se terminant par <math>a_0</math><ref>C'est ici la grande différence entre la base k-adique et la base k usuelle : en base k usuelle, on peut avoir un zéro positionnel en <math>a_1</math>. En conséquence, par exemple, "01"="1" : donc deux chaines de longueur différente peuvent représenter le même entier.</ref>.

Si <math>n>a_0</math>, intéressons nous au nombre entier <math>(n-a_0)/k</math> : il vaut <math>a_1+a_2\times k+...+a_p\times k^{{p-1}}</math>, mais aussi <math>b_1+b_2\times k+...+b_p\times k^{{p-1}}</math>. Il a donc deux décompositions. Donc, comme démontré ci-dessus, <math>b_1=a_1</math>. Et par récurrence, on démontre que, pour tout <math>i</math>, <math>b_i=a_i</math>, donc <math>n</math> n'a qu'une seule décomposition.

Démontrons maintenant que tout entier naturel <math>n</math> a une décomposition de type <math>(a_0,a_1,...,a_p)</math>. Pour cela, il suffit d'en construire une, et on peut le faire par récurrence comme suit : si <math>n</math> n'est pas divisible par <math>k</math>, on choisit le reste de sa division par <math>k</math> comme valeur de <math>a_0</math>, et si est divisible par <math>k</math>, on pose <math>a_0=k</math>.  Si <math>n=a_0</math>, on a trouvé une décomposition valable.

Si <math>n>a_0</math>, alors <math>n_1=n-a_0</math> est, par construction, un entier non nul qui est divisible par <math>k</math>.  Appliquons à <math>n_1/k</math> la méthode appliquée précédemment pour définir <math>a_1</math>.  Si <math>n=a_1\times k+a_0</math>, on a trouvé une décomposition valable. Sinon, posons :  <math>n_2=n-a_1\times k-a_0</math>. <math>n_2</math> est, par construction, divisible par <math>k^2</math>. En appliquant la même méthode à <math>n_2/k^2</math> on définit <math>a_2</math> puis, par récurrence, tous les <math>a_i</math>, et on a ainsi construit une décomposition valable de <math>n</math>. 

On a donc bien démontré que tout entier naturel non nul <math>n</math> a une décomposition du type recherché, et qu'elle est unique.}}

Certains historiens des mathématiques estiment que d'anciens systèmes de numération auraient pu être bijectifs, donc sans utilisation du zéro<ref>{{Article|prénom1=Berenice|nom1=Rojo-Garibaldi|prénom2=Costanza|nom2=Rangoni|prénom3=Diego L.|nom3=González|prénom4=Julyan H. E.|nom4=Cartwright|titre=Non-power positional number representation systems, bijective numeration, and the Mesoamerican discovery of zero|périodique=Heliyon|volume=7|numéro=3|date=2021-03|issn=2405-8440|pmid=33851058|pmcid=8022160|doi=10.1016/j.heliyon.2021.e06580|lire en ligne=https://pubmed.ncbi.nlm.nih.gov/33851058/|consulté le=2023-03-16|pages=e06580}}</ref>.

== 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 bijectif<ref>Pour 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}.</ref>.
{| class="wikitable"
|+
!Base
!10
!
!
!
!
!
!
!
!
!
!
!
!
!
!
|-
|Décimal usuel
|1
|2
|9
|10
|11
|20
|21
|30
|99
|100
|101
|110
|111
|200
|1000
|-
|10 bijectif
|1
|2
|9
|A
|11
|1A
|21
|2A
|99
|9A
|A1
|AA
|111
|19A
|99A
|}
{| class="wikitable"
|+
!Base
!5
!
!
!
!
!
!
!
!
!
!
!
!
|-
|Décimal usuel
|1
|2
|4
|5
|6
|9
|10
|11
|15
|20
|25
|30
|31
|-
|5 usuel
|1
|2
|4
|10
|11
|14
|20
|21
|30
|40
|100
|110
|111
|-
|5 bijectif
|1
|1
|4
|5
|11
|14
|15
|21
|25
|35
|45
|55
|111
|}
{| class="wikitable"
|+
!Base
!3
!
!
!
!
!
!
!
!
!
!
|-
|Décimal usuel
|1
|2
|3
|4
|8
|9
|10
|12
|13
|18
|30
|-
|3 usuel
|1
|2
|10
|11
|22
|100
|101
|110
|111
|200
|310
|-
|3 bijectif
|1
|2
|3
|11
|22
|23
|31
|33
|111
|123
|233
|}
{| class="wikitable"
|+
!Base
!2
!
!
!
!
!
!
!
!
!
!
!
|-
|Décimal usuel
|1
|2
|3
|4
|5
|6
|7
|8
|9
|11
|15
|16
|-
|Binaire usuel
|1
|10
|11
|100
|101
|110
|111
|1000
|1001
|1011
|1111
|10000
|-
|2 bijectif
|1
|2
|11
|12
|21
|22
|111
|112
|121
|211
|1111
|1112
|}
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){{ind|cinq-adique}} = 3 × 5{{exp|4}} + 4 × 5{{exp|3}} + 1 × 5{{exp|2}} + 5 × 5{{exp|1}} + 2 × 5{{exp|0}} = (34152){{ind|cinq}} = (2427){{ind|décimal}}.

:(119A){{ind|dix-adique}} = 1 × 10{{exp|3}} + 1 × 10{{exp|2}} + 9 × 10{{exp|1}} + 10 × 10{{exp|0}} = (1200){{ind|décimal}}.

=== Propriétés ===
Pour un ''k'' donné ≥ 1,
* il y a exactement ''k''{{exp|''n''}} 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 [[Partie entière et partie fractionnaire|E]]([[Logarithme|log]]{{ind|''k''}}(''n''+1)), contrairement à [[Partie entière et partie fractionnaire|E]]([[Logarithme|log]]{{ind|''k''}}(''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'''{{Référence souhaitée|date=15 mars 2023}} . 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'''{{Référence souhaitée|date=15 mars 2023}}. 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 [[tableur]]s 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{{exp|8}} + 9 × 26{{exp|7}} + 11 × 26{{exp|6}} + 9 × 26{{exp|5}} + 16 × 26{{exp|4}} + 5 × 26{{exp|3}} + 4 × 26{{exp|2}} + 9 × 26{{exp|1}} + 1 × 26{{exp|0}} = 4878821185187

Une variante de ce système est partiellement utilisée pour nommer les [[Désignation des étoiles variables|étoiles variables]]<ref>{{Lien web |titre=International Astronomical Union {{!}} IAU |url=https://www.iau.org/public/themes/naming_stars/#n2 |site=www.iau.org |consulté le=2023-03-15}}</ref>.

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îne de caractères|chaînes de caractères]] les plus courtes possible.

== Notes et références ==
{{Traduction/Référence|en|Bijective numeration|378376372 }}
{{Références}}

=== Sources ===
* [[Corrado Böhm|Böhm, C.]] "On a family of Turing machines and the related programming language", ''ICC Bulletin 3'', p. 191, July 1964.

== Bibliographie ==
* {{Ouvrage|langue=en|auteur1=Raymond Smullyan|titre=Theory of formal systems|lieu=Princeton, New Jersey|éditeur=Princeton University Press|date=1961|réimpression=1968|pages totales=149|lire en ligne=https://archive.org/details/theoryofformalsy0000smul/mode/1up|consulté le=13 mars 2023}}
* {{Ouvrage|langue=en|auteur1=Arto Salomaa|titre=Formal Languages|lieu=New York|éditeur=Academic Press|date=1973|pages totales=344|lire en ligne=https://archive.org/details/formallanguages0000salo/mode/2up?view=theater|consulté le=14 mars 2023}}
* {{Ouvrage|langue=en|auteur1=Donald Knuth|titre=The Art of Computer Programming Vol 2 Seminumerical Algorithms|lieu=USA|éditeur=Addison-Wesley|date=2007|année première édition=1998|pages totales=792|isbn=0-201-89684-2|lire en ligne=https://archive.org/details/artofcomputerpro0002knut_u2o0/mode/2up?view=theater|consulté le=14 mars 2023}}, 

{{Palette|Numération|Base de numération positionnelle}}
{{Portail|mathématiques}}

{{DEFAULTSORT:Systeme de numeration bijectif}}
[[Catégorie:Numération]]