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