Interesante matriz de enteros con un extraño patrón

Question

Estaba experimentando y encontré este patrón:

Comienza con un array (infinito) con la fila superior con todos los unos, y las dos columnas de la izquierda también con todos los unos.

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Luego, para encontrar las columnas, a partir de la fila superior, suma los números de la diagonal hacia la izquierda:

$$ \begin{matrix} 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & 1 & 1 & \cdots \\ \color{blue}{1} & 1 & \color{blue}{1+1} & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & ? & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$ Después de este paso, reemplaza los números debajo del último así: $$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repite:

$$ \begin{matrix} 1 & 1 & \color{red}{1} & \color{red}{1} & 1 & 1 & 1 & 1 & \cdots \\ 1 & \color{red}{1} & 2 & \color{red}{1+1} & ? & ? & ? & ? & \cdots \\ \color{red}{1} & 1 & 2 & \color{red}{1+1+1} & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & ? & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Reemplazar:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Repite:

$$ \begin{matrix} 1 & 1 & 1 & \color{blue}{1} & \color{blue}{1} & 1 & 1 & 1 & \cdots \\ 1 & 1 & \color{blue}{2} & 2 & \color{blue}{1+2} & ? & ? & ? & \cdots \\ 1 & \color{blue}{1} & 2 & 3 & \color{blue}{1+2+1} & ? & ? & ? & \cdots \\ \color{blue}{1} & 1 & 2 & 3 & \color{blue}{1+2+1+1} & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & ? & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Reemplazar:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 4 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & ? & ? & ? & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Supongo que ahora entiendes la idea. Así que después de rellenar la matriz, tengo:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & ? & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & ? & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & ? & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & ? & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{?} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Así que parece que los números de la diagonal podrían ser los números primos. Pero el cálculo de la siguiente columna destruye esta esperanza:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdots \\ 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & \cdots \\ 1 & 1 & \color{red}{2} & 3 & 4 & 5 & 7 & 8 & \cdots \\ 1 & 1 & 2 & \color{red}{3} & 5 & 6 & 9 & 11 & \cdots \\ 1 & 1 & 2 & 3 & \color{red}{5} & 7 & 10 & 13 & \cdots \\ 1 & 1 & 2 & 3 & 5 & \color{red}{7} & 11 & 14 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & \color{red}{11} & 15 & \cdots \\ 1 & 1 & 2 & 3 & 5 & 7 & 11 & \color{red}{15} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{matrix} $$

Escribir esta secuencia:

$$2, 3, 5, 7, 11, 15, \cdots $$

Así que mi pregunta es, ¿cuál es esta secuencia, que reflejaba los primos pero que de repente divergía?

Answer 1

La entrada en el $m$ la fila y $(n+1)$ es igual al número de particiones de $n$ en partes no superiores a $m$ . En particular, el $m$ de la diagonal es igual al número de particiones de $m$ (como señala BoizWeir).

Si $p(k,j)$ denota el número de particiones de $k$ en partes no superiores a $j$ y luego ordenar las particiones de $k$ por su mayor parte $i$ rinde $$ p(k,j) = \sum_{i=1}^{\min\{j,k\}} p(k-i,i), $$ que coincide con el procedimiento que has utilizado para construir la matriz (al igual que las condiciones iniciales).

Answer 2

Así que después de mirar la página de la OEIS (y el comentario que me señaló @bburGsamohT), ¡creo que lo tengo resuelto!

El comentario define las cantidades (aunque he cambiado los nombres de las variables):

$$a_1 = \frac{1}{1-x}$$

$$a_2 = \frac{1}{1-x^2}$$

$$a_3 = \frac{1}{1-x^3}$$

$$a_4 = \frac{1}{1-x^4}$$

etc.

La clave es que podemos escribirlas como series.

$$a_1 = \frac{1}{1-x} = 1+x+x^2+x^3+x^4+\cdots$$

$$a_2 = \frac{1}{1-x^2} = 1+x^2+x^4+x^6+x^8+\cdots$$

$$a_3 = \frac{1}{1-x^3} = 1+x^3+x^6+x^9+x^{12}+\cdots$$

$$a_4 = \frac{1}{1-x^4} = 1+x^4+x^8+x^{12}+x^{16}+\cdots$$

etc.

Entonces el coeficiente de $x^n$ en el producto infinito $a_1a_2a_3a_4\cdots$ es sólo el número de formas en que podemos escribir el número $n$ como una suma:

$$n=x_1+2x_2+3x_3+4x_4+\cdots$$

donde el $x_i$ son enteros positivos. (Esto resulta de multiplicar el producto infinito).

En realidad, la matriz está construida de tal manera que los números de las diagonales (o más bien, como señala el comentario, las filas (que se estabilizan a segmentos cada vez más largos de la secuencia)) cuentan exactamente el número de formas de escribir $n$ como la suma mencionada anteriormente.

Pero, por supuesto, ¡el producto infinito mencionado anteriormente es una fórmula para la función generadora de los números de partición! Así, igualando los coeficientes, encontramos que la secuencia de la matriz es la secuencia de los números de partición. Q.E.D.

Gracias a todos por la ayuda.