Polynômes de Cantor.
Bijections de Nⁿ sur N.

Codage de Nⁿ par des éléments de N

Les deux seuls polynômes de degré 2, des deux variables x et y, qui soient des bijections de N² sur N, sont les polynômes de Cantor (Montré en 1923 par Fueter et Pólya) :

f(x,y)=((x+y)^2+3x+y)/2 et g(x,y)=((x+y)^2+x+3y)/2.

On a naturellement g(x,y)=f(y,x)

Le problème général qui est de déterminer les polynômes de degrés d bijectifs de Nⁿ sur N reste ouvert et semble très difficile.

En composant les polynômes précédents on obtient des bijections de Nⁿ sur N. Les polynômes suivants définissent des bijections de N³ sur N et de N⁴ sur N, mais il y en a bien d'autres.

f(x,y) = ((x+y)^2+3*x+y)/2     de N² vers N
       = 1/2*x^2 + x*y + 1/2*y^2 + 3/2*x + 1/2*y

h(x,y,z) = f(f(x,y),z)   de N³ vers N
         = 3/4*(x + y)^2 + 1/8*((x + y)^2 + 3*x + y + 2*z)^2 + 9/4*x + 3/4*y + 1/2*z
         = 1/8*x^4 + 1/2*x^3*y + 3/4*x^2*y^2 + 1/2*x*y^3 + 3/4*x^3 + 7/4*x^2*y + 1/2*x^2*z + 5/4*x*y^2 + 
           x*y*z + 1/2*y^2*z + 15/8*x^2 + 1/8*y^4 + 1/4*y^3 + 9/4*x*y + 3/2*x*z + 7/8*y^2 + 1/2*y*z + 
           1/2*z^2 + 9/4*x + 3/4*y + 1/2*z

k(x,y,z,t) = f(h(x,y,z),t) de N⁴ vers N
           = 9/8*(x + y)^2 + 3/16*((x + y)^2 + 3*x + y + 2*z)^2 + 1/128*(6*(x + y)^2 + ((x + y)^2 + 3*x + y + 
                  2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 1/2*t + 27/8*x + 9/8*y + 3/4*z

l(x,y,z,t,u) = f(k(x,y,z,t), u)  de N⁵ vers N
             = 27/16*(x + y)^2 + 9/32*((x + y)^2 + 3*x + y + 2*z)^2 + 3/256*(6*(x + y)^2 + ((x + y)^2 + 3*x + y + 
                  2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 1/32768*(144*(x + y)^2 + 24*((x + y)^2 + 3*x + y + 2*z)^2 + 
                  (6*(x + y)^2 + ((x + y)^2 + 3*x + y + 2*z)^2 + 8*t + 18*x + 6*y + 4*z)^2 + 64*t + 128*u + 432*x + 
                  144*y + 96*z)^2 + 3/4*t + 1/2*u + 81/16*x + 27/16*y + 9/8*z

Les calculs ont été réalisés à l'aide du logiciel libre et "open-source" Sage.
Seules les expressions développées de f(x, y) et de h(x,y,z) sont indiquées, celles de k et de l sont trop longues. Développé et réduit, l(x,y,z,t,u) contient plus d'un millier de monômes différents.

Table de valeurs

La table ci-dessous donne quelques valeurs du polynôme : f(x,y)=((x+y)^2+3x+y)/2.

Calculs

Bijection de N² sur N

À partir du couple (x, y) on peut calculer son image k = f(x, y) dans N.
Inversement, à partir de k, on peut calculer x et y tels que f(x, y) = k.

Ensembles équipotents

S'il existe une bijection de l'ensemble E vers l'ensemble F, on dit que E et T sont équipotents, qu'ils ont le même cardinal, ou encore qu'ils ont exactement le même nombre d'éléments.

Si l'ensemble E est un ensemble fini (ayant un nombre fini d'éléments) et F un sous-ensemble de E, différent de E, il n'existe pas de bijection de E vers F et donc E et F n'ont pas le même nombre d'éléments.
Mais si E est un ensemble infini, c'est parfois possible, un sous-ensemble F de E, différent de E peut dans certains cas avoir autant d'éléments que E, (il y a aussi d'autres exemples où ce n'est pas vrai, voir plus bas).

Par exemple l'ensemble N des entiers naturels est en bijection avec l'ensemble I des naturels impairs, il y a donc exactement autant de naturels impairs que de naturels (pairs ou impairs).

La bijection n --> (n-1)/2 de I dans N est illustrée ci-dessous :

Par contre, l'ensemble N des entiers naturels est un sous-ensemble de l'ensemble R des nombres réels mais N et R ne sont pas équipotents (n'ont pas le même nombre d'éléments).

Les ensembles N des naturels, Q des rationnels et D des décimaux sont équipotents.

Un ensemble E, fini ou infini, n'est jamais équipotent à l'ensemble P(E) de ses parties.

Pages de liens sur Cantor et sur la combinatoire.

Décimation et bijection de N² vers N

Dans l'exemple suivant il n'est plus question des polynômes de Cantor. Cette fois l'idée sous-jacente est la décimation (Voir la page d'Éric Angelini Decimation-like sequences), mais la mise en œuvre de cette décimation est sensiblement différente.

Méthode de calcul de f_n(x, y):

Choisissez une valeur de n au moins égale à 2. En prenant n=10 on comprend mieux le sens du mot décimation. Soit donc n=10 dans l'exemple qui suit et construisons une bijection f_n = f₁₀ de N^2 vers N :
Écrivez sur un papier, aussi loin que possible les éléments de N = 0, 1, 2, 3, ....
1) Soulignez le 1er nombre, le n+1=11ème, le 2n+1=21ème... vous aurez successivement les images f₁₀(0,0)=0, f₁₀(0,1) = 10, f₁₀(0,2) = 20... Puis effacez tous les nombres soulignés !
Vous n'avez plus sur votre feuille que 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26 ...
2) Recommencez en soulignant le 1er nombre, le 11ème, le 21ème... vous aurez les images f₁₀(1,0)=1, f₁₀(1, 1)=12, ... Puis effacez tous les nombres soulignés. Il reste 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18, 19, 21, 22, 24, 25, 26 ...
3) Recommencez le même processus une troisième fois pour obtenir les images f₁₀(2,0)=2, f₁₀(2,1)=14 ... Effacez tous les nombres soulignés.
Et ainsi de suite. (Il ne reste plus qu'à démontrer que l'on obtient effectivement une bijection f_n).

Dit plus simplement : On place dans N les éléments successifs, pour y croissant, de f_n(0,y), en avançant de n cases libres en n cases, puis ensuite ceux de f_n(1,y), puis ceux de f_n(2,y)... (Dans une construction pratique on garde x et y inférieurs à un nombre choisi, dans les tableaux construits ci-dessous, cette limite est 10).

Ces fonctions f_n permettent de construire de nombreuses suites d'entiers dont voici quelques exemples :
Suites f_n(x, 0) lorsque x croît

f₂(x, 0) : 0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,... OEIS A000225

f₃(x, 0) : 0,1,2,4,7,11,17,26,40,61,92,139,209,314,472,709,1064,1597,2396,3595,5393,8090,12136,18205,27308,40963,61445,... OEIS A006999

f₄(x, 0) : 0,1,2,3,5,7,10,14,19,26,35,47,63,85,114,153,205,274,366,489,653,871,1162,1550,2067,2757,3677,4903,6538,8718,...

f₅(x, 0) : 0,1,2,3,4,6,8,11,14,18,23,29,37,47,59,74,93,117,147,184,231,289,362,453,567,709,887,1109,1387,1734,2168,2711,3389,...

Suites f_n(x, 1) lorsque x croît

f₂(x, 1) : 2,5,11,23,47,95,191,383,767,1535,3071,6143,12287,24575,49151,98303,...OEIS A055010 et A083329 (sauf le premier terme) 

f₃(x, 1) : 3,5,8,13,20,31,47,71,107,161,242,364,547,821,1232,1849,2774,4162,6244,9367,14051,21077,31616,47425,71138,...

f₄(x, 1) : 4,6,9,13,18,25,34,46,62,83,111,149,199,266,355,474,633,845,1127,1503,2005,2674,3566,4755,6341,8455,11274,...

Suites f_n(x, x) lorsque x croît

f₂(x, x) : 0,5,19,55,143,351,831,1919,4351,9727,21503,47103,...

f₃(x, x) : 0,5,16,34,67,121,223,382,655,1091,1840,2977,4858,7834,12775,20290,32663,51421,82484,...

f₄(x, x) : 0,6,15,31,55,90,147,223,338,509,745,1077,1589,2274,3239,4671,6557,9255,13149,18467,...

Suites f_n(1, y) lorsque y croît

f₂(1, y) : 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,...OEIS A016813

f₃(1, y) : 1,5,10,14,19,23,28,32,37,41,46,50,55,59,64,68,73,77,82,86,91,95,100,104,109,113,118,...

f₄(1, y) : 1,6,11,17,22,27,33,38,43,49,54,59,65,70,75,81,86,91,97,102,107,113,118,123,129,134,139,145,150,155,161,166,171,177,182,187,193,...

Suites f_n(2, y) lorsque y croît

f₂(2, y) : 3,11,19,27,35,43,51,59,67,75,83,91,99,107,115,123,...OEIS A017101 8y+3

f₃(2, y) : 2,8,16,22,29,35,43,49,56,62,70,76,83,89,97,103,110,116,124,130,137,143,151,157,164,170,178,...

f₄(2, y) : 2,9,15,23,30,37,45,51,58,66,73,79,87,94,101,109,115,122,130,137,143,151,158,165,173,179,186,194,201,207,215,222,229,237,243,250,258,...