Combinatoria: Encuentra una fórmula recursiva para las particiones de enteros en tres particiones.

Question

Necesito encontrar una fórmula recursiva para $p_n$ el número de formas de partición $n$ en tres particiones. Por ejemplo, si buscamos las particiones de $6$ entonces son $1+1+4$ , $1+2+3$ y $2+2+2$ . Intuitivamente busco el número de formas de partición $5$ que son $1+1+3$ y $1+2+2$ y tratar de relacionarlo con el número de particiones de $6$ . Por supuesto, para cada partición de $n-1$ hay una partición correspondiente de $n$ en el que el (o un) elemento máximo se incrementa en $1$ . Sin embargo, me cuesta encontrar una buena caracterización para el resto de particiones que no se forman de esta manera. Podría pensar en aumentar también un elemento mínimo, pero entonces tendría que encontrar una forma de contar el número de dobles, lo que significaría contar el número de formas de partición $n=a+b+c$ tal que $a\leq b\leq c$ y $a+1=b$ o $a+1=c+1$ . Y ni siquiera confío plenamente en que esta descripción recoja todas las formas en que los elementos podrían ser contabilizados por partida doble.

En el caso de la partición $5$ y $6$ , aumentando el elemento máximo toma las particiones $1+1+3$ y $1+2+2$ y los rendimientos $1+1+4$ y $1+2+3$ . Aumentando el elemento mínimo se obtiene $1+2+3$ y $2+2+2$ por lo que el elemento doblemente contabilizado es $1+2+3$ .

Answer 1

Creo que lo más fácil sería empezar con la función de generación de particiones en $3$ partes.

La función generadora se utilizará para construir la partición en capas.

Por ejemplo, una partición de $15$ a $3$ Las piezas se forman en capas: $3$ capas de ancho $3$ , $2$ capas de ancho $2$ y $2$ capas de ancho $1$ .

$$\begin{array}{c|ccc} \text{layer $7$}&\Large{*} & &\\ \text{layer $6$}&\Large{*} & &\\ \text{layer $5$}&\Large{*} &\Large{*} &\\ \text{layer $4$}&\Large{*} &\Large{*} &\\ \text{layer $3$}&\Large{*} &\Large{*} &\Large{*}\\ \text{layer $2$}&\Large{*} &\Large{*} &\Large{*}\\ \text{layer $1$}&\Large{*} &\Large{*} &\Large{*}\\\hline \textbf{part no.}& 1 & 2 & 3 \end{array}$$

Esta es la partición $(7,5,3)$ .

Si construimos las particiones en capas, entonces podemos tener un número arbitrario ( $\ge 1$ ) de capas de anchura $3$ . Estas posibilidades pueden ser representadas por:

$$x^{1\cdot 3}+x^{2\cdot 3}+x^{3\cdot 3}+\cdots=\frac{x^3}{1-x^3}\tag{1}$$

entonces un número arbitrario ( $\ge 0$ ) de capas de anchura $2$ . Estas posibilidades pueden ser representadas por:

$$x^{0\cdot 2}+x^{1\cdot 2}+x^{2\cdot 2}+\cdots=\frac{1}{1-x^2}\tag{2}$$

entonces un número arbitrario ( $\ge 0$ ) de la anchura $1$ . Estas posibilidades pueden ser representadas por:

$$x^{0\cdot 1}+x^{1\cdot 1}+x^{2\cdot 1}+\cdots=\frac{1}{1-x}\tag{3}$$

La función generadora de particiones en exactamente $3$ partes es

$$P(x)=\sum_{k\ge 0}p_kx^k\, , \tag{4}$$

donde $p_k$ es el número de particiones de $k$ en exactamente $3$ partes. $P(x)$ viene dada, por tanto, por el producto de los factores $(1)$ , $(2)$ y $(3)$ :

$$P(x)=\frac{x^3}{(1-x)(1-x^2)(1-x^3)}=\frac{x^3}{1-x-x^2+x^4+x^5-x^6}\tag{5}$$

Así, nuestra partición de ejemplo de $15$ anterior está representado por el término de recepción de factores contribuyentes $x^{3\cdot 3}x^{2\cdot 2}x^{2\cdot 1}$ en esta expansión de $(5)$ .

Reorganización de $(5)$ :

$$P(x)(1-x-x^2+x^4+x^5-x^6)=x^3$$

$$\implies P(x)=x^3+(x+x^2-x^4-x^5+x^6)P(x)\, .\tag{6}$$

Utilizando $(4)$ en $(6)$ y equiparar $x^k$ coeficientes:

$$p_k=p_{k-1}+p_{k-2}-p_{k-4}-p_{k-5}+p_{k-6}\tag{Answer}$$

con $p_3=1$ es nuestro valor de partida, como se muestra en $(6)$ .

Answer 2

Es mejor pensar en el problema como un ajuste de estrellas y barras, entonces sólo hay que dividir por el número de permutaciones que varían entre $3!$ , $3!/2$ , $1$ pero como esto es más bien complicado y exagerado para esta tarea, y no se ajusta a los requisitos, podría sentenciar la función recursiva de todas las particiones disponibles $A+B+C$ condicionado con una ordenación simbólica predefinida, elijo que sea descendente: $A>=B>=C$

$S_A(a,n)$ se considera el número de particiones descendientes $x_1x_2...x_n$ donde $x_1<=A+1$ y $x_1+x_2+...+x_n=n+a$

En su caso las particiones de 6 se calculan así $s_{3}(3,3)$

Podemos eliminar las unidades $1$ para simplificar los cálculos, que toman $x_1$ disminuido para ser $<=A$ y $x_1+x_2+...+x_n=a$

La función recursiva para este asunto se reduce a

$S_{3}(3,3)=\sum_i S_{3-i}(i,2) = S_{3}(0,2)+S_{2}(1,2)+S_{1}(2,2)$ donde:

$S_{A}(a,n)=\begin{cases} 0\ \text{if } \frac{a}{n}>A \\ 1\ \text{if } n=1 \\ \sum_{i=0\rightarrow a-1} S_{Min(A,a-i)}(i,n-1)\ \text{otherwise} \\ \end{cases}$

Haré que esta fórmula sea practicable pronto, ahora me voy al trabajo.