Re: Bije��o entre NxN e N

["Ecass Dodebel" <ecassdodebel@xxxxxxxxxxx>]

>
>Acho que agora eu achei uma bije��o entre N^3 e N
>(x,y,z)|-> (x#y#z)(x#y#z-1)(x#y#z#4)/6 # (2x#y#z) # (x#y#z#1)(x#y#z#2)/2 - 
>(x#y#1)(x#y#2)/2
>N�o est� na forma expandida, os primeiros termos s�o:
>(0,0,0)
>(0,0,1);(0,1,0)
>(1,0,0)
>(0,0,2);(0,1,1);(0,2,0)
>(1,0,1);(1,1,0)
>(2,0,0)
>(0,0,3);(0,1,2);(0,2,1);(0,3,0)
>(1,0,2);(1,1,1);(1,2,0)
>(2,0,1);(2,1,0)
>(3,0,0)
>...
>Estou tentando generalizar o polin�mio.
>
>Obrigado!
>
>Eduardo Casagrande Stabel.
>________________________________________________________________________
>Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com
>

Ol�, pessoal!

Acho que consegui generalizar o polin�mio. Vamos � minha id�ia:
P_1(x_1)=x_1, esse n�s definimos. E direi que
Q_n(x)=n�mero de n-uplas naturais (x_1,...,x_n) com x_1+...+x_n=x, de forma 
que
Q_n(x)=P_n(x,0,...,0) - P_n(x-1,0,...,0), quando x>0 e
Q_n(0)=1

Para ordenarmos os elementos de NxNx...xN = N^n utilizaremos a seguinte 
regra:
i) (x_1,...,x_n) vem depois de (y_1,...,y_n) se x_1+...+x_n>y_1+...+y_n
ii) se x_1+...+x_n = y_1+...+y_n, ent�o (x_1,...,x_n) vem depois de 
(y_1,...,y_1) se, na ordena��o de N^(n-1), (x_2,...,x_n) vier antes de 
(y_2,...,y_n).

Com isso, fica f�cil de ver por que Q_n(x)=P_n(x,0,...,0) - 
P_n(x-1,0,...,0), e tamb�m podemos construir o P_(n+1) a partir do P_n, 
vamos � constru��o:
1) Q_(n+1)(x) = Q_n(0)+...+Q_n(x)
Isso por que os elementos (x_1,...,x_(n+1)) com a soma x_1+...+x_(n+1)=x 
podem ser entendidos como o n�mero de elementos com x_1=0 (que s�o Q_n(x)), 
com x_1=1 (que s�o Q_n(x-1)),..., com x_1=n (que s�o Q_n(x)=0), o que mostra 
a validade da f�rmula.
2) Seja S=x_1+...+x_(n+1), ent�o
P_(n+1)(x_1,...,x_(n+1)) = [Q_(n+1)(0) + ... + Q_(n+1)(S)]
                           - [P_(n)(x_2,...,x_(n+1)) + 1]
A demonstra��o � simples, de acordo com i e ii.

Por 2), aplicando 1), chegamos � f�rmula:
P_(n+1)(x_1,...,x_(n+1)) = [(S+1)Q_n(0) + ... + Q_n(S)]
                           - [P_(n)(x_2,...,x_(n+1)) + 1]
Onde S=x_1+...+x_(n+1). E essa � a constru��o de P_(n+1) a partir de P_n. A 
prova de que P_(n+1) � polinomial vem do fato que P_n � polinomial e a soma 
dos Q_(n)'s tamb�m �, acho que n�o � muito dif�cil de ver. Logo para 
qualquer n natural existe um polin�mio que defina uma bije��o entre N^n e N, 
e ainda conseguimos achar o polin�mio.

Obrigado!

Eduardo Casagrande Stabel.

PS. eu continuo curioso para saber se existem mais de dois polin�mios que 
definam bije��o entre NxN e N, e algo sobre bije��es por polin�mios em QxQ e 
Q, RxR e R.


________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com