Polynômes de Cantor.
Bijections de Nn sur N.
Plus généralement, pour des polynômes qui sont des fonctions de couplage de N n vers N, vous pouvez consulter la page provisoire du wiki de Jeux-et-Mathematiques sur les fonctions de couplage de Skolem.
Ce sont des polynômes de degré n. Quelques explications et des algorithmes sont donnés sur la fonction et son inverse inverse ainsi que sur la construction des polynômes.
La fonction de Cantor est le cas particulier que l'on obtient en prenant n=2.
Un choix plus important est proposé à la page provisoire du wiki :
Partie II - 2n-2 bijections de Nn vers N.
Aucune explication des calculs n'est donnée pour l'instant, sur cette page.
Codage de Nn 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 2 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 n sur N reste ouvert et semble très difficile.
En composant les polynômes précédents on obtient des bijections de N n sur N. Les polynômes suivants définissent des
bijections de N 3 sur N et de N 4 sur N, mais il y en a bien d'autres.
f(x,y) = ((x+y)^2+3*x+y)/2 de N2 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 N3 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 N4 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 N5 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 N2 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.
Décimation et bijection de N2 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 10 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 10(0,0)=0, f 10(0,1) = 10, f 10(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 10(1,0)=1, f 10(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 10(2,0)=2, f 10(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 fn(x, 0) lorsque x croît
f2(x, 0) : 0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,... OEIS A000225
f3(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
f4(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,...
f5(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 fn(x, 1) lorsque x croît
f2(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)
f3(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,...
f4(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 fn(x, x) lorsque x croît
f2(x, x) : 0,5,19,55,143,351,831,1919,4351,9727,21503,47103,...
f3(x, x) : 0,5,16,34,67,121,223,382,655,1091,1840,2977,4858,7834,12775,20290,32663,51421,82484,...
f4(x, x) : 0,6,15,31,55,90,147,223,338,509,745,1077,1589,2274,3239,4671,6557,9255,13149,18467,...
Suites fn(1, y) lorsque y croît
f2(1, y) : 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,...OEIS A016813
f3(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,...
f4(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 fn(2, y) lorsque y croît
f2(2, y) : 3,11,19,27,35,43,51,59,67,75,83,91,99,107,115,123,...OEIS A017101 8y+3
f3(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,...
f4(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,...
Liens
|
Pages de liens sur
