Uma função injectiva entre o conjunto de pares ordenados de números naturais no conjunto dos números naturais

O estudo da complexidade computacional assenta essencialmente sobre a descrição de algoritmos capazes de serem executados numa máquina de Turing e o número de passos necessários para a respectiva execução. Porém, os métodos inerentes às demonstrações essenciais requerem a construção de uma função bijectiva entre o conjunto de múltiplos de números naturais \left(x_1,x_2,\cdots,x_n\right)\in\mathbb{N}\times\mathbb{N} e o conjunto \mathbb{N} dos números naturais.

Começamos com o caso mais simples, n=2 e vamos tentar determinar a forma algébrica para uma função bijectiva entre o conjunto de pares de \mathbb{N}\times\mathbb{N} e o conjunto dos números naturais. Temos, por exemplo, a função

\begin{matrix}  (0,1)\to 1\\  (1,0)\to 2\\  (0,2)\to 3\\  (1,1)\to 4\\  (2,0)\to 5\\  (0,3)\to 6\\  (1,2)\to 7\\  (2,1)\to 8\\  (3,0)\to 9\\  \vdots  \end{matrix}

Trata-se efectivamente da ordenação lexicográfica dos pares ordenados graduada de acordo com a soma das coordenadas. Dados dois pares ordenados X_1=\left(x_1,y_1\right) e X_2=\left(x_2,y_2\right), se x_1+y_1<x_2+y_2, então X_1<X_2. Caso x_1+y_1>x_2+y_2, também X_1>X_2. Se x_1+y_1=x_2+y_2, X_1 é maior ou menor que X_2 consoante y_1 seja maior ou menor que y_2, sendo o empate decidido pelos valores de x_1 e x_2. Particionamos o conjunto dos pares ordenados de acordo com a gradação:

\left\lbrace (0,1),(1,0)\right\rbrace\cup\left\lbrace (0,2),(1,1),(2,0)\right\rbrace\cup\left\lbrace (0,3),(1,2),(2,1),(3,0)\right\rbrace\cup\cdots

Facilmente constatamos que o primeiro conjunto da partição possui \binom{2}{1} elementos, o segundo conjunto possui \binom{3}{1} elementos, o terceiro, \binom{4}{1} elementos e assim sucessivamente. Atribuímos, portanto, ao primeiro elemento de cada conjunto, considerando a ordenação lexicográfica graduada, os índices dados por aqueles valores, isto é,

\begin{matrix}  (0,1)\to\binom{1}{1}=\binom{2}{2}\\  (0,2)\to\binom{1}{1}+\binom{2}{1}=\binom{3}{2}\\  (0,3)\to\binom{1}{1}+\binom{2}{1}+\binom{3}{1}=\binom{4}{2}\\  \vdots  \end{matrix}

Os índices associados aos restantes pares calculam-se, a partir destes, somando o valor da coordenada x como pode ser prontamente observado. É fácil, portanto, constatar que a função

f(x,y)=\binom{x+y+1}{2}+\binom{x}{1}

nos resolve o problema. Como

\binom{x+y+1}{2}=\frac{(x+y+1)(x+y)}{2}

temos finalmente

f(x,y)=\frac{1}{2}\left(x^2 +2xy+y^2+3x+y\right)

Com alguns simples cálculos aritméticos verificamos efectivamente que

\begin{matrix}  f(0,1)=1\\  f(1,0)=2\\  f(0,2)=3\\  f(1,1)=4\\  f(2,0)=5\\  \vdots  \end{matrix}

Consideremos agora o caso da indexação dos ternos ordenados de \mathbb{N}^3 por índices em \mathbb{N}. Para o efeito, voltamos a considerar a partição do conjunto dos ternos de acordo com a gradação, isto é, com a soma das coordenadas:

\left\lbrace (0,0,1),(0,1,0),(1,0,0)\right\rbrace\cup\left\lbrace (0,0,2),(0,1,1),(1,0,1),(0,2,0),(1,1,0),(2,0,0)\right\rbrace\cup\cdots

A ordenação dos pares ordenados é decidida pela soma das coordenadas e, em caso de empate, começa a ser desempatada pela terceira coordenada, depois pela segunda e, por fim pela primeira. Cada um dos conjuntos da partição pode ainda ser separado nos subconjuntos dos ternos ordenados que possuam a mesma coordenada z. Por exemplo, o segundo conjunto da partição anterior pode ser partido do seguinte modo

\left\lbrace (0,0,2),(0,1,1),(1,0,1),(0,2,0),(1,1,0),(2,0,0)\right\rbrace=\left\lbrace (0,0,2)\right\rbrace\cup\left\lbrace (0,1,1),(1,0,1)\right\rbrace\cup\left\lbrace (0,2,0),(1,1,0),(2,0,0)\right\rbrace

Se ignorarmos a coordenada z em cada um destes subconjuntos, verificamos que estes se identificam com os conjuntos da partição dos pares ordenados apresentado acima. Segue-se daqui que o primeiro conjunto da partição dos ternos ordenados possui exactamente \binom{1}{1}+\binom{2}{1}=\binom{3}{2} elementos, o segundo conjunto da partição tem \binom{1}{1}+\binom{2}{1}+\binom{3}{1}=\binom{4}{2}, e assim sucessivamente. Como o fizemos atrás, começamos por indexar o primeiro elemento de cada conjunto da partição de \mathbb{N}, vindo

\begin{matrix}  (0,0,1)\to\binom{2}{2}=\binom{3}{3}\\  (0,0,2)\to\binom{2}{2}+\binom{3}{2}=\binom{4}{3}\\  (0,0,3)\to\binom{2}{2}+\binom{3}{2}+\binom{4}{2}=\binom{5}{3}\\  \vdots  \end{matrix}

Para completar a indexação procede-se a partir dos índices atribuídos, observando que cada um dos conjuntos da partição de \mathbb{N}^3 se subdividem da mesma forma que o caso dos pares ordenados. A indexação dos ternos ordenados é dada, portanto, pela função

f(x,y,z)=\binom{x+y+z+2}{3}+\binom{x+y+1}{2}+\binom{x}{1}

Não é difícil, neste ponto, obter uma forma polinomial para a função de indexação. Porém, essa identificação não acarreta quaisquer vantagens. Se procedermos de forma indutiva (cuja demonstração formal incide sobre o método da indução), conluímos que a função de indexação dos múltiplos ordenados \left(x_1,x_2,\cdots,x_n\right) de \mathbb{N}^n é dada pela função

f\left(x_1,x_2,\cdots,x_n\right)=\sum_{k=1}^n{\binom{k-1+\sum_{l=1}^k{x_l}}{k}}

Resta-nos elaborar um método que nos permita reconstruir o múltiplo ordenado a partir do respectivo índice. Para o efeito, observamos que vale a identidade

\binom{n+1}{p}=\frac{n+1}{n-p+1}\binom{n}{p}

a qual se segue trivialmente da fórmula

\binom{n}{p}=\frac{n!}{p!(n-p)!}

Um processo para inverter a indexação baseia-se na identidade anterior e facilmente se ilustra com um exemplo. Suponhamos que pretendemos determinar o terno  ordenado correspondente ao índice 30. Para o efeito, começamos por observar que

\begin{matrix}  \binom{3}{3}=1\\  \binom{4}{3}=\frac{4}{1}\binom{3}{3}=4\\  \binom{5}{3}=\frac{5}{2}\times 4=10\\  \binom{6}{3}=\frac{6}{3}\times 10=20\\  \binom{7}{3}=\frac{7}{4}\times 20=35  \end{matrix}

Como \binom{7}{3} excede 30, consideramos o coeficiente binomial \binom{6}{3}=20 e fazemos g_1=6-2=4. Verificámos, deste modo, que o terno correspondente possui gradação 4. Subtraímos o valor do coeficiente binomial, 20, a 30 adivindo 10. Mais uma vez fazemos

\begin{matrix}  \binom{2}{2}=1\\  \binom{3}{2}=3\\  \binom{4}{2}=\frac{4}{2}\times 3=6\\  \binom{5}{2}=\frac{5}{3}\times 6=10  \end{matrix}

Vemos que \binom{5}{2} é igual a 10 que corresponde à diferença que determinámos. Fazemos g_2=5-1=4 e vemos que a nova diferença é igual a 10-10=0. Neste caso, fazemos g_3=0 que corresponde a essa diferença (como estamos a lidar com ternos ordenados não irá existir a gradação g_4). O terno ordenado correspondente ao índice 30 é dado por

(x,y,z)=\left(g_3,g_2-g_3,g_1-g_2\right)=(0,4,0)

De facto, temos

f(0,4,0)=\binom{0+4+0+2}{3}+\binom{4+0+1}{2}+\binom{0}{1}=20+10+0=30

como seria de esperar. Não é muito difícil de verificar que a essência do algoritmo apresentado incide na determinação de cada uma das gradações segundo as quais particionamos sucessivamente cada um dos conjuntos de múltiplos ordenados.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s