prueba de identidad en las particiones de números naturales

Question

Definición:

Una tupla $\lambda = (\lambda_1, \cdots, \lambda_k)$ de los Números Naturales se llama numérico de la partición de n si $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$. A numeric partition $\lambda = (\lambda_1, \cdots, \lambda_k) \vdash n$ can be as well written as $\lambda = [m_1, \cdots, m_n]$ with $m_i = \# \{j | \lambda_j = i\}$ and $\sum_{k=1}^{n} m_k*k = n$.

---

Ejercicio:

$g_k(\lambda) := \# \{i | m_i(\lambda) \geq k\}$.

Ejemplo:

$\lambda = [5,3,3,3,2,2,0,\cdots,0] \Rightarrow m_3(\lambda) = 3, g_2(\lambda) = 6$

Probar para solucionar$n,k \geq 1$ $$\sum\limits_{\lambda \vdash n} m_k(\lambda) = \sum\limits_{\lambda \vdash n} g_k(\lambda)$$

---

Primero traté de escribir todas numérico particiones de $n = 3$

$$ \{\lambda | \lambda \vdash 3 \} = \{(1,1,1),(1,2),(3)\}$$

$$ \begin{array}{l|cccccc} \lambda & m_1 & m_2 & m_3 & g_1 & g_2 & g_3 \\\hline (1,1,1) & 3 & 0 & 0 & 1 & 1 & 1 \\ (1,2) & 1 & 1 & 0 & 2 & 0 & 0 \\ (3) & 0 & 0 & 1 & 1 & 0 & 0 \\\hline \sum & 4 & 1 & 1 & 4 & 1 & 1 \end{array} $$

Answer 1

Supongamos que se pudiera demostrar que el número de particiones con $m_l \geq k$ es igual al número de particiones con $m_k \geq l$. A continuación, se deduce que $$ \sum_{p \vdash n} m_k(p) = \sum_{l \geq 1} \sum_{p \vdash n}[m_k(p) \geq l] = \sum_{l \geq 1} \sum_{p \vdash n}[m_l(p) \geq k] = \sum_{p \vdash n} g_k(p). $$ Con el fin de demostrar la reclamación, que sea suficiente para limitarnos a las particiones cuyas partes sólo se $k,l$. De hecho, una partición arbitraria de $n$ se descompone de forma única como una partición de $n_1+n_2$ donde $n_1$ es una partición con $k,l$, e $n_2$ es una partición de no uso de $k,l$. Además, podemos suponer que las $k,l$ son relativamente primos (de lo contrario, cancelar el MCD).

Nos muestran que el número de $k,l$-particiones con $m_l < k$ es igual al número de $k,l$-particiones con $m_k < l$. Aviso que desde $k,l$ son relativamente primos, hay más de un $k,l$-partición con $m_l < k$ y en más de una $k,l$-partición con $m_k < l$. Se demuestra que si hay un $k,l$-partición con $m_l < k$, entonces hay una con $m_k < l$.

Supongamos que hay un $k,l$-partición con $m_k < l$. Si para esa partición también se $m_l < k$, hemos terminado. De lo contrario, repetidamente reemplace $k$ partes de tamaño $l$ $l$ partes de tamaño $k$ hasta llegar a una partición con $m_l < k$.

---

Aquí es una alternativa a la prueba de la afirmación acerca de la $k,l$-particiones, para coprime $k,l$.

Vamos $$\alpha = (k^{-1}n) \bmod{l}, \quad \beta = (l^{-1}n) \bmod{k}.$$ Aquí $k^{-1}$ se ha tomado con respecto a $l$, y viceversa.

Definir la siguiente operación ("conjugación") en los pares $(a,b)$ que solucionar $ak+bl=n$: $$(a,b)' = \left(\frac{l}{k}(b - \beta) + \alpha, \frac{k}{l}(a - \alpha) + \beta\right).$$ Uno puede comprobar las siguientes propiedades:

1. La conjugación de la toma de una solución de $ak+bl=n$ a otra solución.
2. La conjugación es una involución (es su propio inverso).
3. Si hay una solución integral,$(a,b)$$0 \leq a < l$, entonces su conjugado $(a',b')$$0 \leq b < k$, y viceversa.
4. Si $kl|n$$(a,b)' = (b,a)$.

Aquí están algunos ejemplos, con $k = 5$$l = 3$. Uno puede comprobar que $k^{-1} \bmod{l} = 2$$l^{-1} \bmod{k} = 2$.

Si $n = 30$$(a,b)'=(b,a)$. Tenemos $(0,10)' = (6,0)$$(3,5)' = (3,5)$.

Si $n = 40$$\alpha = 80 \bmod{3} = 2$$\beta = 80 \bmod{2} = 0$. Por lo tanto $(a,b)' = (3/5b + 2, 5/3(a - 2))$. Tenemos $(8,0)' = (2,10)$$(5,5)' = (5,5)$.

Si $n = 7$$\alpha = 14 \bmod{3} = 2$$\beta = 14 \bmod{2} = 0$. Esta vez no hay un mínimo de soluciones. En su lugar, tenemos el par $(2,-1)' = (7/5,0)$.

---

He aquí una prueba mediante la generación de series. La ventaja de esta prueba es que no requiere ningún pensamiento.

La costumbre de generación de la serie de particiones $$P = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}.$$ El coeficiente de $x^n$ es el número de particiones de $n$.

Supongamos que queremos sumar más de $m_k$. Así que tenemos que reemplazar el factor de $1/(1-x^k)$ con $$ x^k + 2x^{2k} + 3x^{3k} + \cdots = \frac{x^k}{(1-x^k)^2}. $$ Para la generación de series para $\sum m_k$ es $$ M = \frac{x^k}{1-x^k} P. $$

Ahora vamos a la suma de más de $g_k$. ¿Cuánto $1$-las partes que contribuyen a la suma? Solo se tiene en cuenta si hay, al menos, $k$ de ellos. Así que necesitamos para reemplazar a $1/(1-x)$ con $$ x^k + x^{k+1} + \cdots = \frac{x^k}{1-x}. $$ Por lo $1$-las partes que contribuyen $x^k P$. Del mismo modo, $2$-las partes que contribuyen $x^{2k} P$, y así sucesivamente. En total, la generación de series para $\sum g_k$ es $$ G = (x^k + x^{2k} + x^{3k} + \cdots) P = \frac{x^k}{1-x^k} P = M. $$