2 votos

Número de particiones con x partes

Puede que me equivoque, pero así es como yo defino "partes" cuando hablo de particiones:

La partición 1+1+1 tiene 3 partes. La partición 1+2+2 tiene 3 partes. Los números, sean distintos o no, no importan: lo que importa es el número de dígitos.

Las particiones de 5 son las siguientes: 1+1+1+1+1 = 1+1+1+2 = 1+2+2 = 1+1+3 = 2+3 = 1+4 = 5

De esas 7 particiones, dos constan de 3 partes (1+2+2 y 1+1+3). Dos de ellas constan de 2 partes (2+3 y 1+4).

El número de piezas se define como la variable $x$ y el número que se particiona se define como la variable $n$ . Quiero una ecuación que dé el número de particiones con $x$ cantidad de piezas, cuando $n$ está dividida. Los valores de entrada son $x$ y $n$ y el valor de salida es el número de particiones con $x$ cantidad de piezas.

Digamos que el nº de particiones formado por $x$ se define como la variable $y$ .

Esto es lo que sé:

Hay tres constantes: Si $x = 1, n, (n-1)$ entonces $y = 1$ , independientemente de la $n$ -valor.

Para demostrarlo, observa de nuevo las particiones de 5. Sólo una partición tiene un $x$ -valor de 1, y que es la partición 5. Sólo una partición tiene un $x$ -valor de $n$ y que es la partición de 1+1+1+1+1. Sólo una partición tiene un $x$ -valor de $n-1$ y esa es la partición de 1+1+1+2.

Espero que haya quedado más claro. He editado esta pregunta drásticamente, porque creo que me expresé de forma poco clara en la primera edición.

EDITAR: Mi pregunta es la siguiente: ¿Existe una ecuación para determinar $y$ basado en $n$ y $x$ ?

6voto

Matt Dawdy Puntos 5479

Parece que estás preguntando por el número $p_k(n)$ de particiones de un número $n$ en exactamente $k$ piezas. Se trata de un tipo estándar de partición restringida y puede resolverse de la siguiente manera. Dada dicha partición, "girar el Diagrama de Ferrers lo que demuestra que $p_k(n)$ también cuenta el número de particiones de un número $n$ cuya parte más grande tiene exactamente el tamaño $k$ . La eliminación de esta parte produce una partición de $n-k$ cuya parte más grande tiene un tamaño máximo de $k$ y utilizando esto podemos demostrar que para $k$ esta secuencia tiene un función generadora dada por

$$P_k(x) = \sum_{n \ge 0} p_k(n) x^n = \frac{x^k}{\prod_{i=1}^k (1 - x^i)}$$

lo que en principio permite escribir una forma cerrada para $p_k(n)$ (de nuevo, para $k$ se complica cuanto mayor es $k$ es), aunque no lo haré. Como ejemplo al azar, establecer $k = 5$ da

$$\begin{align} \sum_{n \ge 0} p_5(n) x^n &= \frac{x^5}{(1 - x)(1 - x^2)(1 - x^3)(1 - x^4)(1 - x^5)} \\ &= x^5 + x^6 + 2x^7 + 3x^8 + 5x^9 + 7x^{10} + 10x^{11} + 13x^{12} + 18x^{13} + \dots \end{align}$$

que muestra, por ejemplo, que el número de particiones $p_5(13)$ de $13$ en exactamente $5$ piezas es $18$ . $p_5(n-5)$ que también cuenta el número $p_{\le 5}(n)$ de particiones de $n$ en un máximo de $5$ partes, resulta ser A001401 sobre la OEIS.

Entre otras cosas, esta función generadora puede utilizarse para deducir la tasa de crecimiento asintótica de $p_k(n)$ (para fijos $k$ como $n \to \infty$ ), que resulta ser

$$p_k(n) \sim \frac{n^{k-1}}{(k-1)! k!}.$$

Edita: Vale, mea culpa - dije que escribiría la forma cerrada que se obtiene de la función generadora pero para grandes $k$ La verdad es que no sé muy bien cómo hacerlo aunque sea de forma desordenada. La estrategia básica es calcular el descomposición de fracciones parciales de la función generadora $P_k(x)$ arriba. Esto se vuelve muy complicado en general; esto es lo que se obtiene para valores pequeños de $k$ .

Para $k = 1$ existe una única partición de $n$ con $1$ parte, a saber $n = n$ . Esto corresponde a la función generadora

$$P_1(x) = \frac{x}{1 - x} = x + x^2 + x^3 + \dots $$

que da $\boxed{ p_1(n) = 1 }$ si $n \ge 1$ y $0$ si $n = 0$ . Bastante sencillo.

Para $k = 2$ la descomposición de la fracción parcial es

$$P_2(x) = \frac{x^2}{(1 - x)(1 - x^2)} = \frac{1}{2(1 - x)^2} - \frac{3}{4(1 - x)} + \frac{1}{4(1 + x)}$$

(esto se puede hacer a mano) que da el ya sorprendentemente complicado

$$\boxed{ p_2(n) = \frac{n}{2} + \frac{(-1)^n - 1}{4} }.$$

Esto se puede simplificar, y demostrar, con un poco de trabajo de caso de la siguiente manera. Las particiones en dos partes son $n = i + j$ donde, si $i \ge j$ tenemos $1 \le j \le \lfloor \frac{n}{2} \rfloor$ . Así obtenemos $\boxed{ p_2(n) = \left\lfloor \frac{n}{2} \right\rfloor }$ lo que equivale a lo anterior después de entrecerrar un poco los ojos.

Para $k = 3$ la descomposición de la fracción parcial es (según WolframAlpha )

$$P_3(x) = \frac{-x^2 + 20x - 7}{72(1 - x)^3} - \frac{8}{1 + x} + \frac{x + 2}{9(1 + x + x^2)}$$

lo que da, utilizando ese $\frac{x + 2}{1 + x + x^2} = \frac{2 - x - x^2}{1 - x^3}$ y $-x^2 + 20x - 7 = - (1 - x)^2 - 18(1 - x) + 12$ y tras algunas simplificaciones,

$$\boxed{ p_3(n) = \frac{6n^2 - 7}{72} - \frac{(-1)^n}{8} + \frac{\omega_3(n)}{9} }$$

donde $\omega_3(n)$ es una función periódica con período $3$ que repite $2, -1, -1, 2, -1, -1, \dots $ . Ya no es del todo obvio que se trate de un número entero, y no puedo afirmar que no haya cometido ningún error de cálculo, pero el resultado tiene que parecerse a esto aunque haya metido la pata. A partir de aquí la cosa empeora. $p_k(n)$ tiene periodo- $d$ componentes para cada $1 \le d \le k$ . Puede consultar la descomposición de fracciones parciales para $k = 4$ por ti mismo aquí .

Así que hay un sentido importante en el que es inútil esperar una forma cerrada para grandes $k$ aunque, como en el caso anterior, la asintótica de orden superior en $n$ para fijo $k$ es fácil de calcular y puede que los siguientes términos tampoco estén tan mal. La buena noticia es que para muchos propósitos no importa; la función generadora es lo suficientemente potente como para responder a muchas preguntas que puedas tener sobre particiones con partes restringidas.

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