7 votos

Función de partición - sin duplicados

Hay una función equivalente a la función de partición, que no permite la duplicación? O, alternativamente, para cualquier N, ¿cuántas particiones habrá - desactivando los que tienen el mismo número entero que aparecen más de una vez.

Editar:

Lo siento, para ser más exactos, me gustaría saber de una función, o incluso simplemente complejidad asintótica, que producirá las particiones de la entrada, a excepción de aquellas que han enteros que ocurren más de una vez. Sólo he dado cuenta de que este es el equivalente lógico a mi problema; le agradezco que no lo he hecho exactamente publicado mucho esfuerzo en encontrar a mí mismo. A menos que alguien viene de atrás y los puestos de una solución relativamente rápida, usted puede esperar más de mí pronto.

1voto

Nikolai Prokoschenko Puntos 2507

El número de particiones de $n$ en distintas partes es OEIS A000009, lo que da un montón de referencias. A veces es llamada la función de partición $Q$ (en contraste a $P$ para todas las particiones). Como Gerry Myerson ha dicho, es la generación de la función es $\prod_{m\ge 1} (1+x^m)$.

Como para la generación de las particiones, usted podría utilizar algo ya preparado como el paquete partitions en R, que, por ejemplo, da para particiones de $12$

> library(partitions)
> Q(12)
[1] 15
> diffparts(12)
[1,] 12 11 10 9 9 8 8 7 7 7 6 6 6 5 5
[2,]  0  1  2 3 2 4 3 5 4 3 5 4 3 4 4
[3,]  0  0  0 0 1 0 1 0 1 2 1 2 2 3 2
[4,]  0  0  0 0 0 0 0 0 0 0 0 0 1 0 1

Si desea hacerlo usted mismo, me parece una manera (si se puede generar particiones ordinarias) se nota que las particiones de $n$ a $k$ positivas diferentes partes son equivalentes a las particiones de $n-\frac{k(k-1)}{2}$ a $k$ positivo partes (posiblemente igual), sólo mediante la adición de $k-1, k-2,\ldots,1,0$ respectivamente para cada parte. Por ejemplo, para encontrar particiones de $12$ a $4$ diferentes partes, mirar las particiones de $6$ a $4$ partes: hay dos, a saber:$3+1+1+1$$2+2+1+1$; ahora agregar a $3+2+1+0$ a estas término plazo para $6+3+2+1$$5+4+2+1$.

0voto

Marko Riedel Puntos 19255

Creo que es muy instructivo para derivar la anterior generación la función de uso de las especies, a pesar de ser muy simple, como presenta algunas estándar de trucos en la manipulación de ciclo de índices.

Observar que la especie $\mathcal{Q}$ que representa las particiones con únicos constituyentes es simplemente $$\mathcal{Q} = \mathfrak{P}\left(\sum_{k\ge 1} \mathcal{Z}^k\right).$$

Ahora recuerdo la recurrencia por Lovasz para el ciclo de índice $Z(P_n)$ de el conjunto operador $\mathfrak{P}_{=n}$ $n$ ranuras, que es $A$Z(P_n) = \frac{1}{n} \sum_{i=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{donde}\quad Z(P_0) = 1.$$

Deje $$F_n(z) = Z(P_n)\left(\frac{z}{1-z}\right)$$ en el segundo paréntesis de la derecha representa el ciclo de índice de sustitución e introducir la generación de la función $$G(y) = \sum_{n\ge 0} F_n(z) y^n,$$ así que estamos interesados en $G(1).$

La recurrencia de los rendimientos $$n Z(P_n) = \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}).$$

Sustituto de $a_l$, se multiplica por $y^{n-1}$ y suma más de $n\ge 1$ a obtener $$G'(y) = \sum_{n\ge 1} y^{n-1} \sum_{i=1}^n (-1)^{l-1} \frac{z^l}{1-z^l} F_{n-l}(z) \\= \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} \sum_{n\ge l} y^{n-1} F_{n-l}(z).$$ Este es $$\sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1} \sum_{n\ge l} y^{n-l} F_{n-l}(z) = G(y) \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1}.$$ Por lo tanto $$(\log G(y))' = \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} y^{l-1}.$$ La integración de tenemos $$\log G(y) = C + \sum_{l\ge 1} (-1)^{l-1} \frac{z^l}{1-z^l} \frac{y^l}{l} = C + \sum_{k\ge 1} \sum_{l\ge 1} (-1)^{l-1} z^{kl} \frac{y^l}{l} \\= C - \sum_{k\ge 1} \log \frac{1}{1+yz^k}.$$ La conclusión es que $$G(y) = e^C \exp\left( - \sum_{k\ge 1} \log \frac{1}{1+yz^k} \right) = e^C \exp\left( \sum_{k\ge 1} \log(1+yz^k) \right) \\= e^C \prod_{k\ge 1} (1+yz^k).$$

Ahora$G(0)=1$, y de ahí la constante obedece $e^C=1$, para una respuesta final de $$G(y) = \prod_{k\ge 1} (1+yz^k).$$

En particular, la generación de la función de particiones en piezas únicas es $$G(1) = \prod_{k\ge 1} (1+z^k),$$ precisamente como debe ser.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X