Prueba de que el número de 1 en$P(n)$ es igual al número de magnitudes distintas en$P(n)$

Question

Dada la división de número de $n$ (dejar nombre que $\pi$) vamos a considerar:
$A(\pi)$ es un número de $1$ en $\pi$
$B(\pi)$ es un número de diferentes elementos en la $\pi$.

La prueba de que $$ \sum_{\pi} A(\pi) = \sum_{\pi} B(\pi) $$ Ejemplo: $$ \pi = 1 + 1 + 2 + 2 +2 + 4 $$ a continuación, $$A(\pi) = 2 \wedge B(\pi)=3$$

Sugerencia: Considerar a cada lado de la ecuación en el uso de $P(1), P(2), ... P(n-1)$ donde $P(k)$ es el número de divisiones de $k$.

Mi pruebe

No tengo idea de cómo usar esa sugerencia, así que me decidí a definir la $\delta = A(\pi) - B(\pi) $ y la esperanza de que me puede ayudar a encontrar bijection.

Ejemplo de $n=5$

\begin{array}{|c|c|c|c|} \hline \pi& \delta\\ \hline 5 & -1 \\ \hline 4+1 & -1 \\ \hline 3+2 & -2 \\ \hline 3+1+1 & 0 \\ \hline 2+2+1 & -1 \\ \hline 2+1+1+1 & 1 \\ \hline 1+1+1+1+1 & 4 \\ \hline \end{array} pero no me ayuda, así que probablemente sugerencia es realmente importante.

Answer 1

Esto podría resolverse teniendo en cuenta la generación de funciones. Llame a la primera suma $\mathcal A_n$ y la segunda suma $\mathcal B_n$.

Lo que primero tenemos: $$\begin{align*} \sum_{n\in\mathbb{N}} \mathcal A_nx^n&= \underbrace{\left(\sum_{k\ge0}kx^k\right)}_{\text{Counting # of 1's}}\underbrace{\left(\prod_{r\ge2}\frac1{1-x^r}\right)}_{\text{The rest}}\\ &= \frac x {\left ( 1-x \right )^2}\,\left(\prod_{r\ge2}\frac1{1-x^r}\right)\\ &=\frac x {1-x}\,\left(\prod_{r\ge1}\frac1{1-x^r}\right) \end{align*}$$ Entonces: $$\begin{align*} \sum_{n\in\mathbb{N}} \mathcal B_nx^n&= \frac{\partial }{\partial k}\left.\left ( \prod_{r\ge1}\left ( 1+kx^r+kx^{2r}+kx^{3r}+\cdots \right ) \right )\right|_{k=1}\\ &= \frac{\partial }{\partial k}\left.\left ( \prod_{r\ge1}\left ( \frac k {1-x^r}-k+1 \right ) \right )\right|_{k=1}\\ &=\left.\left ( \prod_{r\ge1} \frac k {1-x^r}-k+1 \right )\underbrace{\left ( \sum_{r\ge1} \frac{\frac 1 {1-x^r}-1}{\frac k {1-x^r}-k+1} \right )}_{\text{Product rule term}}\right|_{k=1}\\ &=\left ( \prod_{r\ge1} \frac 1 {1-x^r} \right )\left ( \sum_{r\ge1} x^r \right )\\ &=\frac x {1-x}\,\left(\prod_{r\ge1}\frac1{1-x^r}\right) \end{align*}$$ Por lo tanto, $\mathcal A_n=\mathcal B_n$ como se desee.

---

Como una nota del lado, esto también sugiere que ambos son iguales a $\sum_{h=0}^{n-1}P(h)$, así que tal vez hay un mayor acercamiento elemental.

Actualización:

Resulta que hay! Para el siguiente que voy a escribir $\mathcal P_n=\sum_{h=0}^{n-1}P(h)$.

$\text{1. }\mathcal A_n=\mathcal P_n\text{:}$

Para cada partición de $n$ contiene $k$ muchas $1$'s, mapa de a $k$ otras particiones de la siguiente manera, por ejemplo: $$\color{rojo}{1+1+1}+3+4~\longrightarrow~\begin{cases} \color{blue}{1+1}+3+4 \\ \color{blue}{1}+3+4 \\ 3+4 \end{casos}$$ Por lo tanto la correlación inversa es anexando "$+1$"s a cualquier partición de algunos $0\le h\le n-1$ hasta que la totalidad de las sumas evalúa a $n$.

Por lo tanto, la suma de todos los aspecto de $1$'s es igual a la cuenta de todas las particiones de cualquier $0\le h\le n-1$, lo que muestra que $\mathcal A_n=\mathcal P_n$ como se desee.

$\text{2. }\mathcal B_n=\mathcal P_n\text{:}$

Es evidente que se puede transformar $\mathcal B_n$ a la suma de $\sum_{k=1}^{n}P\left(n\mid\exists k\right)$ donde $P\left(n\mid\exists k\right)$ cuenta el número de particiones de $n$ el uso de al menos uno de los $k$.

Nota sin embargo que $P\left(n\mid\exists k\right)$ es sólo $P\left(n-k\right)$, lo que $$\mathcal B_n=\sum_{k=1}^{n}P\left(n-k\right)=\sum_{h=0}^{n-1}P(h)=\mathcal P_n$$ como se desee.

Answer 2

Cada partición que tiene un grupo de 1 puede ser transformado a su contraparte, donde el 1 de forma que una parte. Tomar todas las particiones P(5):

{5}

{4 1}

{3 2}

{3 1 1}

{2 2 1}

{2 1 1 1}

{1 1 1 1 1}

Ahora sumar 1 a cada uno. A continuación, agregue las nuevas particiones generadas por el colapso de cada grupo de 1 a una sola parte.

{5 1}

{4 1 1}

{3 2 1}

{3 1 1 1}

{2 2 1 1}

{2 1 1 1 1}

{1 1 1 1 1 1}

Siete 1 en total, dos de los cuales agregar distintas magnitudes (por {5,1} y {3,2,1}). Echemos un vistazo a los otros cinco:

{4 1 1} => {4 2} (distinta magnitud 2)

{3 1 1 1} => {3 3} (distinta magnitud 3)

{2 2 1 1} => {2 2 2} (distinta magnitud 2)

{2 1 1 1 1} => {4 2} (distinta magnitud 4)

{1 1 1 1 1 1} => {6} (distinta magnitud 6)

---

Llame a $P_1$ el grupo de particiones de $n$ que disponen de al menos un 1.

Llame a $P_{21}(n)$ el grupo de particiones de $n$ , cada uno , al menos, dos 1.

Llame a $P_{01}(n)$ el grupo de particiones de $n$ que no incluyen ningún tipo de 1.

Llame a $t(p)$ la transformación de una partición donde todos sus 1 se suman para representar una magnitud (por ejemplo, $t(\{2, 1, 1\}) = \{2, 2\}$).

Tres cosas son claras:

(1) $|P_1(n)| = |P(n - 1)|$ ya que se puede generar el lado izquierdo anexando un 1 a cada una de las particiones en el derecho.

(2) $P_{01}(n) \subseteq \{t(p) \mid p \in P_{21}(n)\}$ ya que de lo contrario algunas de las particiones en falta en $P_{21}(n)$.

Y, finalmente, (3) cada uno de distinta magnitud en cada partición en $P_{01}(n)$ está representado en una sola partición de $P_{21}(n)$ como un grupo de 1; de lo contrario, algunas de las particiones en falta en $P_{21}(n)$, y de ser representada más de una vez significaría un duplicado de la partición en $P_{21}(n)$.

(3) significa que el recuento de $P_{21}(n)$ es igual al número de distintas magnitudes en $P_{01}(n)$.

Así que si $\{a, b\} = f(n - 1)$ donde $a$ es el conteo de 1 en $P(n - 1)$ e $b$ es el recuento de las distintas magnitudes en $P(n - 1)$, luego

$f(n) = \{a + |P(n - 1)|, b + |P_{01}(n - 1)| + |P_{21}(n)|\}$

Por supuesto, $|P_{01}(n - 1)| + |P_{21}(n)| = |P_1(n)| = |P(n - 1)|$, por lo que

$f(n) = \{a + |P(n - 1)|, b + |P(n - 1)|\}$