Problema de Putnam: Partición de enteros con funciones generatrices

Question

Nos dieron las siguientes A-1 problema desde el 2003 Putnam de la Competencia:

Deje $n$ ser un entero positivo fijo. De cuántas maneras existen para escribir $n$ como suma de enteros positivos, $$n= a_1+a_2+ \cdots + a_k$$ Con $k$ un entero positivo arbitrario, y $a_1 \le a_2 \le \cdots \le a_k \le a_1+1$. Por ejemplo, con $n=4$ hay 4 maneras: 2, 2+2, 1+1+2, 1+1+1+1.

Me las arreglé para hacer esto por inducción, mostrando que no siempre se $n$ formas de dividir un número entero de tal manera. En mi combinatoria de clase, sin embargo, siempre hemos resuelto entero de problemas de particionamiento con funciones de generación y he sido incapaz de construir uno para este problema. Me preguntaba si las matemáticas.stackexchange de la comunidad me puede ayudar con esto, y al menos me dan un empujón en la dirección correcta.

Gracias

Answer 1

Recordar notación exponencial para las particiones: $a^b$ significa que se $b$ apariciones de $a$ en la partición. (Notación exponencial puede ser útil para ver las funciones de generación.) En notación exponencial, cada partición de la satisfacción de sus limitaciones son de la forma $m^k (m+1)^l$. En su $n = 4$ ejemplo, las particiones son $4^1 5^0$, $2^2 3^0$, $1^2 2^1$, y $1^4 2^0$. Observe que el número más pequeño, $a_1$, debe tener exponente al menos $1$, mientras que el sucesor puede tener exponente $0$.

Para una fija $m$, los aportes de las particiones de la forma $m^k (m+1)^l$ está dado por la siguiente generación de la función:

$$(x^m + x^{2m} + x^{3m} + \cdots)(1 + x^{m+1} + x^{2(m+1)} + \cdots)$$

Esto se simplifica a:

$$\frac{x^m}{1-x^m} \frac{1}{1-x^{m+1}}$$

Tales contribuciones proceden de cualquier $m \geq 1$, y, por supuesto, las contribuciones son disjuntas. Así, la generación total de la función es:

$$\sum_{m \geq 1} \frac{x^m}{1-x^m} \frac{1}{1-x^{m+1}}$$

Esto podría ser ya demasiado grande para un codazo, pero el punto es que ahora obtener algo que se puede manipular. Después de algunos obvios $1 - x$ factorings y algunos telescópica, llego $\frac{x}{(1 - x)^2}$, una generación de la función de $n$, como se desee. Déjeme saber si usted obtiene resultados similares o no.

Answer 2

Esto en realidad no responder a la pregunta en el sentido de que no utiliza funciones de generación. Pero pensar en el problema de la división de cualquier número positivo $n$ a un determinado número de $k$ de las piezas, con $1\leq k\leq n$, como justa como sea posible, en el sentido de que no hay dos partes difieren en más de $1$ (por si lo hicieron, uno podría hacer más equitativa mediante el movimiento de una unidad de la más grande a la más pequeña parte). Una solución es hacer primero $k$ a partes iguales de tamaño $\lfloor n/k\rfloor$, y luego si $k$ no se dividen equitativamente $n$ distribuir el resto de los $n\bmod k$ unidades mediante la asignación al azar de distintas partes, haciendo los $\lceil n/k\rceil$ (ya que el orden de las partes no son tomados en cuenta, no hace ninguna diferencia). Puede usted ver por qué no hay otros tales equitativa particiones de $n$ a $k$ partes? Una vez establecido esto, estos son claramente los $n$ posibles soluciones a su problema, uno para cada $k$.

Personalmente, con una descripción completa de la solución, estoy mentalmente bloqueado a pensar cómo la generación de funciones podría ser utilizado para encontrar una solución alternativa. De hecho, creo que el requisito de que se refiere a los tamaños de las diferentes partes (lo que limita su diferencia en la mayoría de las $1$) no se traducen fácilmente en el mundo de la generación de funciones (como se puede hacer para independiente de las condiciones en el tamaño de las piezas, o en multiplicidades de un tamaño dado).

Answer 3

Considerar el entero $n$. ¿Cómo son sus particiones relacionadas con las particiones de los enteros $k$ donde $1 \le k < n$? ¿Se puede encontrar una función recursiva que relaciona estos?

(FYI, proyecto Euler, problema 76 es una variación de esta pregunta).