Numérotation des entiers de NxN

Bonjour,

En TD d'info un exercice était le suivant :

Citation:

---

On peut numéroter les coupes d'entier >= 0 (de N x N) de la manière illustrée ci-dessous, dite de Cantor, (même si ce n'est pas forcément lui qui l'a inventé).

Code:

---

1 2 3 4

9 5 8 2 4 7 0 1 3 6

---

Écrire les instructions qui étnt donné un couple (i, j) de N x N, donnent son numéro dans cette numérotation.

---

Sur la feuille il y avait des lignes pour indiquer qu'on compte en diagonale.
L'important n'est pas trop cet exercice car la prof à donné la formule générale peu avant que je la retrouve moi-même.
La formule est donc : ((i+j)^2+i+3j)/2
Ce que je voudrais savoir c'est comment s'appel cette méthode de comptage ?
Comment peut-on la généraliser sur n dimensions ?

Et surtout, comment retrouver i et j quand on a ce fameux nombre. On sait parfaitement que cette fonction est bijective car elle a été créé pour ça ; Mais j'ai du mal à voir comment à partir d'un telle formule retrouver le couple antécédent.

Merci d'avance. :)

Tu peux remarquer la suite des chiffres sur la ligne du bas

0 1 3 6 10 15 21 ...

C'est ce qu'on appelle les puissances triangulaires de respectivement 0 1 2 3 4.
Puisqu'il y a puissance triangulaire, on a réciproquement la racine triangulaire, que l'on peut calculer par la formule donnée ici:
http://www.recreomath.qc.ca/defis_68.htm

Donc pour n, on obtient le numéro de sa diagonale k.
On sait alors que le nombre est sur la ligne i = n - k(k+1)/2 et la colonne est donnée par j = k - i (j'ai peut-être inversé lignes et colonnes).

Exemple pour 7:
La racine triangulaire est k=3 ( 3(3+1)/2 <= 7 < 4(4+1)/2 )
On a i = 7 - 3(3+1)/2 = 1 et j = 3 - i = 2

dans la formule,c'est une division entière?
pour le couple (1,1) je trouve 3.5 donc 3,c'est juste?
(intuitivement,j'aurai pensé que (1,1) correspond à 4!)
si c'est juste,je ne vois pas trop la logique dans la disposition des nombres en diagonale!!

afrikha oui désolé il manquait un terme dans la fonction. Je l'avais écrite de tête sans vérifier.
La logique dans la disposition des nombres en diagonale est simple : imagine un axe orthonormé avec le sens positif des abscices vers la droite et le sens positif des ordonnées en haut. On place le 0 à l'origine, puis on écrit les chiffres dans l'ordre en décrivant des diagonales en remontant vers la gauche.
Grâce à cela on peut adresser tout le plan décrit avec NxN avec seulement un entier appartenant à N.
D'ailleur ceci prouve que N et NxN sont équipotents. ^^


FrancisSourd J'avais bien remarqué la suite sur la ligne du bas, c'est d'ailleur grâce à ça que j'ai reconsititué la formule.
Pour la racine triangulaire je comprend très bien, mais après pour remonter jusqu'a la ligne / colone j'ai du mal à comprendre (l'heure joue peut-être aussi :)).

Sinon, est-il possible de généraliser ça à un espace en n dimensions ?
Est-il envisageable d'indexer un tous les éléments de l'emsemble QxQ avec un unique nombre apparenant a Q grâce à une méthode similaire.
(je n'ose pas parler de l'emsemble R à cause des limites des ordinateurs).

[quote]

Citation:

---

Envoyé par Celelibi

afrikha oui désolé il manquait un terme dans la fonction. Je l'avais écrite de tête sans vérifier.

---

:furieux: :P

Citation:

---

La logique dans la disposition des nombres en diagonale est simple : imagine un axe orthonormé avec le sens positif des abscices vers la droite et le sens positif des ordonnées en haut. On place le 0 à l'origine, puis on écrit les chiffres dans l'ordre en décrivant des diagonales en remontant vers la gauche.
Grâce à cela on peut adresser tout le plan décrit avec NxN avec seulement un entier appartenant à N.

---

ben oui ça j'avvais compris quand mème.

Citation:

---

D'ailleur ceci prouve que N et NxN sont équipotents. ^^
FrancisSourd J'avais bien remarqué la suite sur la ligne du bas, c'est d'ailleur grâce à ça que j'ai reconsititué la formule.
Pour la racine triangulaire je comprend très bien, mais après pour remonter jusqu'a la ligne / colone j'ai du mal à comprendre (l'heure joue peut-être aussi :)).

Sinon, est-il possible de généraliser ça à un espace en n dimensions ?
Est-il envisageable d'indexer un tous les éléments de l'emsemble QxQ avec un unique nombre apparenant a Q grâce à une méthode similaire.
(je n'ose pas parler de l'emsemble R à cause des limites des ordinateurs).

---

on dit qu'un ensemble E est dénombrable s'il existe une bijection entre E et N.
on peut facilement prouver que NxN et Q sont equipotents,il suffit en effet de considerer la bijection F: Q->NxN
p/q->(p,q)
donc Q et N sont equipotents.
(on peut aussi dire que Q est dénombrable.)
soit G la bijection que tu as donné entre NxN et N.
on a alors FoG:Q->N est une bijection.
considerons maintenant la fonction suivante:
QxQ->NxN
(p/q,r/s)->(FoG(p/q),FoG(r/s))
c'est bien une bijection,car la composée de deux bijections est une bijection.
On en deduit alors que la fonction
QxQ->N
(p/q,r/s)->G(FoG(p/q),FoG(r/s))
est une bijection.

Pour R ce n'est pas possible car R n'est pas dénombrable,ça a été démontré en exploitant l'idée dite de la....."diagonale de Cantor".

[Humour]
Cantor en vietnamien veut dire grosse femme. :frenchy:
[/Humour].

Citation:

---

Envoyé par Celelibi

Pour la racine triangulaire je comprend très bien, mais après pour remonter jusqu'a la ligne / colone j'ai du mal à comprendre (l'heure joue peut-être aussi :)).

---

En fait k(k+1)/2 est le premier numéro de la diagonale. Donc delta=n-k(k+1)/2 est l'écart entre n et le premier numéro de la diagonale. Comme la position de k(k+1)/2 est (0,k), la position de n est (0+delta,k-delta).

Citation:

---

Envoyé par Celelibi

Sinon, est-il possible de généraliser ça à un espace en n dimensions ?

---

On peut découper Q^n selon des tranches q1+q2+...qn=constante, en incrémentant la constante (0,1,2,...) A chaque fois, on a des ensembles finis, donc faciles à numéroter.

Pour n=3, on a des nombres pyramidaux qui apparaissent (somme de nombres triangulaires). Je pense qu'il devient vite difficile d'avoir des formules explicites pour la bijection mais cela se calcule relativement facilement par un algorithme.

Citation:

---

Envoyé par afrikha

on peut facilement prouver que NxN et Q sont equipotents,il suffit en effet de considerer la bijection F: Q->NxN
p/q->(p,q)
donc Q et N sont equipotents.

---

Ton application n'a de sens que si tu supposes la fraction irréductible. Donc ce n'est pas surjectif, puisque seuls les paires (p,q) telles que p soit premier à q sont atteintes.

Par ailleurs, il faut remplacer NxN par ZxN*, car dans Q il y a aussi des nombres négatifs, et les dénominateurs ne sont pas nuls.

Le résultat est qu'on construit en fait une bijection entre Q et une partie de ZxN*. Bien entendu, cette partie est en bijection avec N, mais là il y a encore un peu de travail à faire.

Citation:

---

Envoyé par DrTopos

Citation:

---

Envoyé par afrikha

on peut facilement prouver que NxN et Q sont equipotents,il suffit en effet de considerer la bijection F: Q->NxN
p/q->(p,q)
donc Q et N sont equipotents.

---

Ton application n'a de sens que si tu supposes la fraction irréductible. Donc ce n'est pas surjectif, puisque seuls les paires (p,q) telles que p soit premier à q sont atteintes.

Par ailleurs, il faut remplacer NxN par ZxN*, car dans Q il y a aussi des nombres négatifs, et les dénominateurs ne sont pas nuls.

Le résultat est qu'on construit en fait une bijection entre Q et une partie de ZxN*. Bien entendu, cette partie est en bijection avec N, mais là il y a encore un peu de travail à faire.

---

Alala,j'ai honte,j'ai HONTE :oops:
comment j'ai pu faire une erreur pareille :boulet:
je suis sincerement désolé d'avoir ecrit de telles betises.

En fait ce que je voulais dire en demandant si il est possible d'étendre cette relation à l'ensemble QxQ c'était juste pour savoir si il était possible d'avoir deux paramètres non entiers comme entré de la fonction.
Mais de toutes façon si c'est possible je crains que ça ne rende l'opération inverse extrêment compliqué car basé sur une division entière (lors du calcul de la racine triangulaire).


Juste pour le fun j'ai cherché la formule pour 3 dimensions, et je l'ai trouvé, c'est : (2(x+y+z)^3 + 6(x+y+z)^2 + 3(x+y+z) + (x+y+z))/12 + z(2x+2y+z+3)/2 + y
Et voici un petit bout de l'espace numéroté (les blocs successifs font censés être des "tranches" qui s'empilent) :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

24 13 23 6 12 22 2 5 11 21 0 1 4 10 20   28 16 27 8 15 26 3 7 14 25   31 18 30 9 17 29   33 19 32   34

---

Si y'en a qui veulent plus d'explication à propos de la formule je pourrais en donner mais je ne crois pas que ça interresse quelqu'un. :)

Je laisse le soin à un masochiste de passage de trouver comment on retrouve le tripplet x, y, z à partir de n.
(ça doit être simple quand on a la racine tétraédrique).

A titre de curiosité, voici une autre bijection de NxN vers N:

Code:

---

1 2	(x,y) |-> ((2^x)*(2*y+1)) - 1

---

Elle est très facile à inverser, mais elle a le défaut de donner une répartition des entiers dans le plan très mal équilibrée.

Par ailleurs, quand on a une formule pour la dimension 2, on en déduit facilement une formule pour toutes les dimensions. En effet, soit f: NxN -> N une bijection alors

Code:

---

1 2	(x,y,z) |-> f(f(x,y),z)

---

est une bijection NxNxN -> N, etc... mais encore une fois, les répartitions obtenues sont très mal équilibrées.

Citation:

---

Envoyé par DrTopos

A titre de curiosité, voici une autre bijection de NxN vers N:

Code:

---

1 2	(x,y) |-> ((2^x)*(2*y+1)) - 1

---

Elle est très facile à inverser, mais elle a le défaut de donner une répartition des entiers dans le plan très mal équilibrée.

---

En effet sa répartition m'a l'air un peu "aléatoire". Mais des bijections de NxN vers N on peut supposer qu'il en existe une infinité. Celle-là à au moins le mérite de ne faire apparaitre x et y qu'une seul fois.
Est-ce aussi une bijection de RxR vers R ? :)

Citation:

---

Par ailleurs, quand on a une formule pour la dimension 2, on en déduit facilement une formule pour toutes les dimensions. En effet, soit f: NxN -> N une bijection alors

Code:

---

1 2	(x,y,z) |-> f(f(x,y),z)

---

est une bijection NxNxN -> N, etc... mais encore une fois, les répartitions obtenues sont très mal équilibrées.

---

En effet je n'y avait pas pensé, ça donne peut-être des répartitions non optimale, mais au moins il est facile d'obtenir réccursivement une formule qui soit une bijection de N^a vers N.

Citation:

---

Envoyé par Celelibi

Mais des bijections de NxN vers N on peut supposer qu'il en existe une infinité. Celle-là à au moins le mérite de ne faire apparaitre x et y qu'une seul fois.
Est-ce aussi une bijection de RxR vers R ? :)

---

Il y a effectivement une infinité de bijections de NxN vers N, et même une infinité non dénombrable. Ceci résulte du théorème de Cantor. Par contre, une infinité dénombrables d'entre elles seulement sont programmables.

La formule ne donne pas une bijection de RxR vers R. De toute façon, il résulte du théorème de Brouwer-Joyal que si une bijection de RxR vers R était constructive (programmable), ainsi que sa réciproque, elle serait bicontinue, ce qui donnerait un homéomorphisme de RxR vers R ce qui est impossible pour des raisons des connexité.

Par contre, il est parfaitement possible de construire des bijections calculables (ainsi que leurs réciproques) de QxQ vers Q ou de QxQ vers N. Il est même possible de le faire avec des sous-corps de R plus grand que Q, par exemple des extensions algébriques de Q. Mais évidemment, le problème se complique un peu plus à chaque fois.