¿Alguien conoce una expresión de forma cerrada para una biyección entre $\mathbb{N}^k$ y $\mathbb{N}$ ?

Question

Quiero publicar un artículo y uno de sus resultados es una sencilla expresión de forma cerrada para una biyección natural entre $\mathbb{N}^k$ y $\mathbb{N}$ . Me gustaría saber si ya se conoce.

Answer 1

Esta es mi idea, perdónenme si soy algo impreciso: Queremos ordenar todos los $n$ -tuplas $I=(i_1,\dots,i_n)\in\mathbb N^n$ . Estoy asumiendo $\boldsymbol{0\notin\mathbb{N}}$ . Para ello ordenamos sucesivamente las tuplas en cada una de las "conchas" $S_k=\{I: \max i_j=k\}$ . Tenga en cuenta que $|S_k|=k^n-(k-1)^n$ , por lo que una posibilidad para nuestra biyección $f:\mathbb N^n\to\mathbb N$ es

$$f(I)=(k-1)^n+\ \style{font-family:inherit;}{\text{something, whenever}}\ I\in S_k\,.$$

Ahora mira el número de entradas de $I$ igual a $k$ , digamos que $j$ con $1\leq j\leq n$ . Supongamos que todas las tuplas de $S_k$ con menos de $j$ entradas iguales a $k$ se han pedido. Tenga en cuenta que para $1\leq r<j$ hay $\binom nr\,(k-1)^{n-r}$ tuplas en $S_k$ con exactamente $r$ entradas iguales a $k$ . Por lo tanto, podemos refinar nuestra fórmula a

$$f(I)=(k-1)^n+\sum_{r=1}^{j-1}\binom nr\,(k-1)^{n-r}+\style{font-family:inherit;}{\text{something, whenever}}\ I\in S_k\\\ \style{font-family:inherit;}{\text{has exactly}}\ j\ \style{font-family:inherit;}{\text{entries equal to}}\ k\,.$$

Queda por ordenar dichas tuplas de alguna manera "decente". Primero ordenamos los subconjuntos de $\{1,\dots,n\}$ con $j$ elementos. Esto lo hice cuando estaba en la licenciatura (buenos recuerdos...), obteniendo el siguiente resultado: el mapeo $\gamma$ que envía el $j$ -subrayado $\{c_1<c_2<\cdots<c_j\}\subseteq\{1,\dots,n\}$ al número

$$1+\sum_{i=1}^j\binom{n-c_i}{j-i+1}$$

es una biyección sobre el conjunto $\{1,2,\dots,\binom nj\}$ . Como antes, suponemos que las tuplas "anteriores" han sido numeradas. Más concretamente: denotando por $F_I$ el conjunto $\{\ell: i_\ell=k\}$ suponemos que todas las tuplas $J\in S_k$ con $|F_J|=j$ y $F_J<F_I$ según la ordenación anterior se han numerado. Hay $\gamma(F_I)-1$ subconjuntos de $\{1,\dots,n\}$ de tamaño $j$ , cada uno "generando" $(k-1)^{n-j}$ tuplas "anteriores". Por lo tanto, tenemos

$$f(I)=(k-1)^n+\sum_{r=1}^{j-1}\binom nr\,(k-1)^{n-r}+\bigl(\gamma(F_I)-1\bigr)(k-1)^{n-j}+\style{font-family:inherit;}{\text{something, whenever}}\ I \cdots$$

Última etapa: considerar las entradas de $I$ que son estrictamente inferiores a $k$ y ordenarlos, digamos, por orden lexicográfico. Creo firmemente que esto se puede hacer mediante una fórmula explícita, pero estoy cansado.

Por supuesto, esto no es una forma cerrada analítica porque hay que especificar $k=\max\{i_1,\dots,i_n\}$ y $F_I=\{c_1<c_2<\cdots<c_j\}$ . Si esto no te molesta, entonces esta es tu fórmula (modulo rellena los detalles).

EDITAR

Inspirado por el comentario muy constructivo de OP, aquí vamos de nuevo. Las conchas en la respuesta anterior son en realidad "esferas" en el $\ell_\infty$ métrica. ¿Qué pasa con el $\ell_1$ ¿métrico?

Esta vez asumimos $0\in\mathbb N$ . Como puede adivinar, esta vez ordenaremos las tuplas según su $\ell_1$ norma. Dado $r\in\mathbb N$ cada solución $x=(x_1,\dots,x_n)\in\mathbb N^n$ de la ecuación $x_1+\cdots+x_n=r$ dan lugar al siguiente subconjunto $S(x)$ de $\{1,\dots,r+n-1\}$ :

$$S(x)=\{c_1<c_2<\cdots<c_{n-1}\}\,, \style{font-family:inherit;}{\text{where}}\ c_j=j+\sum_{i=1}^jx_i\,.$$

Es fácil ver que este mapeo define una biyección sobre el conjunto de $(n-1)$ -subconjuntos de $\{1,\dots,r+n-1\}$ , que obviamente tiene $\binom{r+n-1}{n-1}$ elementos. Como en mi solución anterior, utilizamos una numeración explícita de dichos subconjuntos, es decir, asociamos al subconjunto $\{c_1<\cdots<c_{n-1}\}$ el número $\sum_{i=1}^{n-1}\binom{r+n-1-c_i}{n-i}$ . Por último, dada cualquier tupla $I\in\mathbb N$ y definiendo $k=\|I\|_1$ numeramos las tuplas "anteriores", es decir, aquellas tuplas $J$ con $\|J\|_1<k$ . Hay $\sum_{r=0}^{k-1}\binom{r+n-1}{n-1}=\binom{k+n-1}{n}$ tales tuplas. Por lo tanto, nuestra biyección puede escribirse explícitamente (módulo de abreviaturas) como

$$(x_1,\dots,x_n)\in\mathbb N^n\mapsto\binom{k+n-1}{n}+\sum_{i=1}^{n-1}\binom{k+n-1-c_i}{n-i}\,,$$

donde $k=x_1+\cdots+x_n$ y $c_j=j+\sum_{i=1}^jx_i\,.$

Answer 2

Es bien sabido.

Aquí hay una fea biyección entre $\mathbb{N}\times \mathbb{N} $ y $ \mathbb{N}$ .

Si dejas que $k(n) = \left\lceil \frac{\sqrt{1+8n}-1}{2} \right\rceil$ y $j(n,k) = \frac{k (k+1)}{2}-n+1$ , entonces $\beta:\mathbb{N} \rightarrow \mathbb{N}\times \mathbb{N}$ definido por $$\beta(n) = (j(n,k(n)), k(n)-j(n,k(n))+1)$$ es una biyección. La inversa $\beta^{-1}: \mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}$ está dada por: $$ \beta^{-1}(j, l) = \frac{(l+j-1)(l+j)}{2}-j+1$$

Para formar una biyección entre $\mathbb{N}^3$ y $ \mathbb{N} $ Consideremos la función $(n_1,n_2,n_3) \to \beta^{-1}(n_1,\beta^{-1}(n_2,n_3))$ . Esto se puede repetir ad nauseum .

Answer 3

No es realmente una forma cerrada, pero espero que ayude. Sea $f_2:\mathbb N^2 \to \mathbb N$ definirse como $$f_2(n_1,n_2)=2^{n_1}(2n_2+1) - 1$$ Es claramente una biyección, porque todo entero positivo $n$ puede expresarse de forma única como $n=2^km$ , donde $m$ es un número entero impar. Ahora podemos construir $f_3:\mathbb N^3\to\mathbb N$ como $$f_3(n_1,n_2,n_3)=f_2(n_1,f_2(n_2,n_3))$$ y para cualquier $k\in\mathbb N$ , $f_k:\mathbb N^k\to\mathbb N$ $$f_k(n_1,...,n_k)=f_{k-1}(n_1,...,n_{k-2},f_2(n_{k-1},n_k))$$ es una biyección.

Answer 4

La biyección $\Psi_k$ proporcionada por el OP no es en realidad muy diferente de mi otra (primera) respuesta. Mi propuesta de biyección es

$$\begin{align*} (x_1,\dots,x_n)\in\mathbb N^n\mapsto&\,\binom{n-1+\sum_{r=1}^nx_r}{n}+\sum_{i=1}^{n-1}\binom{n-1-i+\sum_{r=i+1}^nx_r}{n-i}\\ =&\,\sum_{i=0}^{n-1}\binom{n-1-i+\sum_{r=i+1}^nx_r}{n-i}\,. \end{align*}$$

Utilizando el hecho de que $\sum_{i=0}^{n-1}a_i=\sum_{i=0}^{n-1}a_{n-1-i}$ (en la segunda suma estamos sumando desde el último al primer sumando de la suma original) podemos reescribir la biyección anterior como

$$\begin{align*} \sum_{i=0}^{n-1}\binom{n-1-(n-1-i)+\sum_{r=(n-1-i)+1}^nx_r}{n-(n-1-i)}=&\,\sum_{i=0}^{n-1}\binom{i+\sum_{r=n-i}^nx_r}{i+1}\\ =&\,\sum_{i=1}^n\binom{i-1+\sum_{r=n-i+1}^nx_r}{i}\,. \end{align*}$$

Consideremos ahora el mapeo $(y_1,\dots,y_n)\in\mathbb N^n\mapsto(y_n,y_{n-1},\dots,y_1)$ Es decir, cambiamos cada entrada $y_r$ por $y_{n+1-r}$ . Esto es evidentemente una biyección de $\mathbb N^n$ a sí mismo. Componiendo este mapa con el anterior obtenemos

$$\begin{align*} (x_1,\dots,x_n)\in\mathbb N^n\mapsto&\,\sum_{i=1}^n\binom{i-1+\sum_{r=n-i+1}^nx_{n+1-r}}{i}\\ =&\,\sum_{i=1}^n\binom{i-1+x_1+\cdots+x_i}{i}\,, \end{align*}$$

que es precisamente igual a $\Psi_n(x_1,\dots,x_n)$ .

ADDENDUM

He aquí una versión modificada y refinada del segundo argumento de mi otra respuesta. Incluyo algo de motivación para la definición de la biyección, así como una prueba razonablemente completa que, en mi opinión, evita cálculos engorrosos.

En aras de la brevedad, escribiremos $[m]=\{1,\dots,m\}, \mathbf x=(x_1,\dots,x_n)\in\mathbb N^n$ y $|\mathbf x|=x_1+\cdots+x_n$ . Considere la siguiente relación $<$ en $\mathbb N^n$ Declaramos que $\mathbf y<\mathbf x$ si $|\mathbf y|<|\mathbf x|$ o si $|\mathbf y|=|\mathbf x|$ y para algunos $i$ con $1\leq i\leq n-1$ tenemos $y_r=x_r$ para $r>i+1$ pero $y_{i+1}>x_{i+1}$ . Se puede comprobar que esto define una ordenación adecuada, de manera que cada elemento sólo tiene un número finito de predecesores (Pista: si $|\mathbf y|=|\mathbf x|$ y $y_r=x_r$ para todos $r\geq2$ , entonces necesariamente $\mathbf y=\mathbf x$ Así que si $\mathbf y\neq\mathbf x$ pero $|\mathbf y|=|\mathbf x|$ entonces $\max\{j: y_j\ne x_j\}=i+1$ con $1\leq i\leq n-1$ ). En particular, el mapeo $f:\mathbb N\to\mathbb N$ dado por $f(\mathbf x)=$ el número de predecesores de $\mathbf x$ es una biyección de $\mathbb N^n$ en $\mathbb N$ .

Dejemos que $\mathbf x$ se arreglen. A cada $\mathbf y$ con $|\mathbf y|<|\mathbf x|$ asociamos la secuencia estrictamente creciente $\bigl(j+\sum_{t=1}^jy_t\bigr)_{j=1}^n\subseteq[n-1+x_1+\cdots+x_n]$ y esto define una biyección entre los conjuntos de dichas tuplas $\mathbf y$ y el conjunto de $n$ -subconjuntos de $[n-1+x_1+\cdots+x_n]$ que tiene $\binom{n-1+x_1+\cdots+x_n}{n}$ elementos. Del mismo modo, para $i=1,\dots,n-1$ a cada $\mathbf y$ Satisfaciendo a $|\mathbf y|=|\mathbf x|, y_r=x_r$ para $r>i+1$ y $y_{i+1}>x_{i+1}$ asociamos la secuencia estrictamente creciente $\bigl[j+\sum_{t=1}^jy_t\bigr]_{j=1}^i\subseteq[i-1+x_1+\cdots+x_i]$ y esto define una biyección entre los conjuntos de dichas tuplas $\mathbf y$ y el conjunto de $i$ -subconjuntos de $[i-1+x_1+\cdots+x_i]$ que tiene $\binom{i-1+x_1+\cdots+x_i}{i}$ elementos. No es difícil demostrar que para $i=1,\dots,n$ el $i$ -El mapa inverso viene dado por

$$\begin{align*} \{c_1<\cdots<c_i\}\subseteq&\,[i-1+x_1+\cdots+x_i]\\[3mm] \mapsto&\,\bigl(\ c_1-1\ \boldsymbol,\ c_2-c_1-1\ \boldsymbol,\ c_3-c_2-1\ \boldsymbol,\ \dots\ \boldsymbol,\ c_i-c_{i-1}-1\ \boldsymbol,\\[3mm] &\,\underbrace{x_1+\cdots+x_{i+1}-c_i+i}_{(i+1)\text{-}\style{font-family:inherit;}{\text{th entry}}}\ \ \boldsymbol,\\[3mm] &\,x_{i+2}\ \boldsymbol,\ x_{i+3}\ \boldsymbol,\ \dots\ \boldsymbol,\ x_n\ \bigr)\in\mathbb N^n\,. \end{align*}$$

Por lo tanto, el número de predecesores de una tupla $\mathbf x$ es precisamente $\sum_{i=1}^n\binom{i-1+x_1+\cdots+x_i}{i}\,.$

Answer 5

Lamentablemente, mi manuscrito fue rechazado por la American Mathematical Monthly. Dijeron lo siguiente:

" El artículo se centra en la construcción explícita de una biyección entre $\bf N\times N$ y $\bf N$ y biyecciones similares para ${\bf N}^k$ . Sin embargo, para mí no está muy claro cuál es el público al que va dirigido y cuál es el objetivo principal del artículo. Una fórmula polinómica explícita para la biyección es, en efecto, agradable, pero definitivamente no es nueva (la he visto en libros de texto de lógica). Si el punto principal es una explicación accesible y agradable (para un público amplio) de por qué esta fórmula es verdadera, es posible, pero el estilo del artículo con muchas fórmulas es bastante confuso y no es adecuado para este objetivo.

Así que siento decir que, en mi opinión, este artículo no parece adecuado para AMM (y, probablemente, para otras revistas que se me ocurran)... "

Así que, como he prometido, he vuelto aquí para presentarles mi fórmula:

$$\Psi_k(n_1, \dots, n_k) = \sum_{i=1}^{k}\binom{i-1+n_1+\dots +n_i}{i}$$

Todavía intentaré presentar mi trabajo en algún coloquio, antes de revelar cómo he obtenido esta fórmula.