¿Cómo se obtiene la fórmula para este bijection de $\mathbb{N}\times\mathbb{N}$ a $\mathbb{N}$?

Question

Cuando se demuestre que el $\mathbb{N}\times\mathbb{N}$ es en bijection con $\mathbb{N}$, parece estándar para dar una prueba de imagen que se muestra de una manera sistemática tejen a través de todos los puntos en $\mathbb{N}\times\mathbb{N}$ y la etiqueta de cada uno a medida que avanza.

Sé que hay una expresión polinómica para este método, dado por $$ J(m,n)=[1+2+\cdots+(m+n)]+m=\frac{1}{2}[(m+n)^2+3m+n] $$ donde $m$ es lo habitual en la $x$-coordinar y $n$ el habitual $y$-coordinar.

Pero, ¿cómo hace uno para "ver" cómo esta fórmula se llega a ella? Sé cómo manipular el medio de expresión para llegar a la derecha de la expresión, pero ¿cómo el medio de expresión se relacionan con el patrón de tejido a través de $\mathbb{N}\times\mathbb{N}$? Gracias.

Answer 1

Para tejer todo el camino a $(m,n)$, en primer lugar, $m+n$ completa superior izquierda a la inferior derecha pasa, de los cuales el primero contiene 1 punto $(0,0)$, el segundo a dos puntos de $(0,1)$$(1,0)$, ..., el $m+n$'th $m+n$$(0,m+n-1)$$(m+n-1,0)$, y luego el $m+1$'th punto en el paso siguiente es $(m,n)$.

Answer 2

$J(m,n)$ es el número de puntos que están antes de $(m, n)$ en este orden. Estos son los puntos a $(x,y)$$x+y < m+n$, y los puntos de $(x,y)$$x + y = m + n$$x < m$.

El primer tipo de puntos se pueden dividir en aquellas con $x+y = 0$ (de los cuales es $1$), los con $x+y = 1$ (de los cuales hay $2$), y así hasta llegar a los con $x +y = m+n-1$, de los cuales hay $m+n$. Estas son las $(m+n-1, 0), (m+n-2, 1), \cdots, (0, m+n-1)$. Así que hay $1 + 2 + \cdots + (m+n)$ de estos.

El segundo tipo son sólo los puntos de $(0,n), (1,n-1), \cdots, (m-1, m+n-1)$. Hay $m$ de estos.

Por lo que el número total de puntos anterior $(m,n)$ en este orden es $$ [1 + 2 + \cdots + (m+n)] + m $$ que es lo que quería.

Answer 3

Mirando el diagrama, el orden es lexicográfica, primero en $m+n$,$m$. La motivación es que es fácil ver que usted obtenga todos los puntos de $\mathbb{N} \times \mathbb{N}$, por lo que ahora solo falta averiguar lo $J(m,n)$ es.

Answer 4

Decir $m$ es la columna, $n$ es la fila. Quieres saber cuántos puntos tienes ya contaba en el momento de llegar a $(m,n)$, el uso de la imagen.

Si suben $n$ filas, le han contado la primera $n$ diagonales en su totalidad (desde la cuenta comienza con $0$). Estos le dan a $1+2+3+\cdots+n$ puntos, puesto que el $n$th hacia abajo en diagonal ha $n$ puntos.

Ahora, cada paso que se mueve a la derecha para llegar a $(m,n)$ agregará un total de diagonales que se debe ya ha "añadido". Esto le dará las diagonales con $n+1$, $n+2,\ldots,n+m$ puntos. Esto significa que, contando sólo con la baja de las diagonales que tiene completamente contadas, se han $$1 + 2 + 3 + \cdots + n + (n+1) + \cdots + (m+n) = \frac{(m+n)(m+n+1)}{2}$$ puntos.

Además, tiene algunos puntos en la diagonal está en que han sido contados. ¿Cuántas? Uno para cada columna se desplaza a la derecha; hay $m$ de las personas. Por eso, además de los puntos que ya se han añadido, no son los primeros a $m$ puntos en la diagonal. Así que una vez que llegues a ese punto, te han contado $$(1+2+3+\cdots+(n+m) + m = \frac{(m+n)(m+n+1)}{2}+m = \frac{1}{2}\left((m+n)^2+(m+n) + 2m\right)$$ puntos, lo que da la fórmula.