Contrariamente a mi práctica habitual, interpretaré $\Bbb N$ como $\Bbb Z^+$ como el conjunto de enteros positivos, en lugar de como el conjunto de enteros no negativos, ya que facilita un poco las cosas. Sólo por diversión, aquí está una biyección real de $\bigcup_{k\ge 1}\Bbb N^k$ a $\Bbb N$ que sólo utiliza un resultado combinatorio elemental.
Es un hecho estándar y es fácil demostrar que hay exactamente $\binom{n-1}{k-1}$ pedido $k$ -tuplas de números enteros positivos cuya suma es $n$ . De ello se deduce que existen $\sum_{k=1}^n\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}k=2^{n-1}$ secuencias finitas de números enteros positivos que suman $n$ ya que cualquier secuencia de este tipo es una $k$ -para algunos $k\le n$ . Para $n\in\Bbb N$ deje $S_n$ el conjunto de secuencias finitas de números enteros positivos cuya suma es $n$ Entonces $\left|\bigcup_{k=1}^{n-1}S_k\right|=\sum_{k=0}^{n-2}2^k=2^{n-1}-1$ intentemos definir una biyección entre $S_n$ y $[2^{n-1},2^n-1]$ . (Todos los intervalos están tomados en $\Bbb Z$ .)
Una posibilidad natural es pedir $S_n$ lexicográficamente y que $\varphi_n:S_n\to[2^{n-1},2^n-1]$ sea el único isomorfismo de orden; $\varphi=\bigcup_{n\in\Bbb Z^+}\varphi_n$ es entonces una biyección desde $\bigcup_{k\ge 1}\Bbb N^k$ a $\Bbb N$ . Esto está claramente bien definido, pero en realidad cuesta un poco de trabajo exponer las funciones $\varphi_n$ . En lugar de limitarme a presentar el resultado y luego justificarlo, creo que será más claro si lo planteo de forma más parecida a como lo hice al pensar en el problema.
En $S_n$ hay $2^{n-2}$ secuencias que empiezan por $1$ , $2^{n-3}$ que empiezan por $2$ y así sucesivamente hasta $2^0$ que empiezan por $n-1$ y luego está el $1$ -secuencia de términos $\langle n\rangle$ . Esto se debe a que cuando el primer término de una secuencia en $S_n$ es $d$ o bien $d=n$ y no hay más términos, o el resto de la secuencia es cualquiera de los $2^{n-d-1}$ miembros de $S_{n-d}$ . Una secuencia en $S_n$ que comienza con $d>1$ por lo tanto tiene al menos $\sum_{k=1}^{d-1}2^{n-1-k}=\sum_{k=n-d}^{n-2}2^k=2^{n-1}-2^{n-d}$ predecesores en $S_n$ y la expresión final es evidentemente válida también para $d=1$ .
El mismo razonamiento muestra que una secuencia en $S_n$ que comienza $\langle d_1,d_2\rangle$ tiene al menos
$$(2^{n-1}-2^{n-d_1})+(2^{n-d_1-1}-2^{n-d_1-d_2})=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}$$
predecesores en $S_n$ . Uno que comienza $\langle d_1,d_2,d_3\rangle$ tiene al menos
$$\begin{align*} &\;\;\;\;\;2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}+2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3}\\ &=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3} \end{align*}$$
predecesores en $S_n$ . Y en general $\langle d_1,d_2,\ldots,d_k\rangle\in S_n$ tiene exactamente
$$\begin{align*} &\;\;\;\;\;2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-2^{n-d_1-d_2-\ldots-d_k}\\ &=2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-1\\ &=2^{n-1}-1-\frac12\sum_{i=1}^{k-1}2^{n-\sum_{j=1}^id_j}\\ &=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\tag{1} \end{align*}$$
predecesores en $S_n$ . Como una comprobación rápida y sucia, $(1)$ dice que la secuencia $\langle n\rangle$ debería haber $2^{n-1}-1$ predecesores en $S_n$ mientras que la secuencia de $n$ no deberían tener ninguna, como de hecho es el caso.
Ahora podemos escribir $\varphi$ : si $\sigma=\langle d_1,d_2,\ldots,d_k\rangle$ es una sucesión finita de números enteros positivos cuya suma es $n$ entonces
$$\begin{align*} \varphi(\sigma)&=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\\ &=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\;. \end{align*}$$
Por supuesto, se entiende que el sumatorio final es $0$ cuando $k=1$ .
