4 votos

Sobre Entero De La Partición

Teorema:

Para cualquier $ n, k \in \mathbb N$, el número de particiones de $n$ en partes, cada una de las cuales aparece en la mayoría de las $k$ a veces, es igual al número de particiones de $n$ en piezas de tamaños que no son divisibles por $k+1$.

Yo supe de una prueba donde $k =2$. Puedo tomar ventaja de la prueba, pero no pude. La prueba consiste en la generación de función. (ver: el libro de chen chuan-chong- "Principios y Técnicas en la Combinatoria" ) No podría realmente ser una mejor manera de atacar este problema. Yo simplemente no lo sé. necesita ayuda para algunos consejos. Gracias

5voto

user8269 Puntos 46

$$\prod(1+x^j+x^{2j}+\cdots+x^{kj})=\prod{1-x^{(k+1)j}\over1-x^j}=\prod_{k+1\nmid j}{1\over1-x^j}$$

2voto

user8269 Puntos 46

También hay un bijective prueba.

Dada una partición de $n$, en el que ninguna parte es divisible por $k+1$, suponga que tiene una parte $a$ que se utiliza más de $k$ veces. A continuación, combinar $k+1$ apariciones de $a$ en una sola ocurrencia de $(k+1)a$. Repita hasta que ninguna parte se utiliza más de $k$ veces.

Dada una partición de $n$, en el que ninguna parte se utiliza más de $k$ de las veces, si usted tiene una parte $a=(k+1)r$ que es un múltiplo de a $k+1$, dividido en $k+1$ apariciones de la parte $r$. Repita hasta que ninguna parte es un múltiplo de a $k+1$.

Esto le da un bijection entre particiones con ninguna parte divisible por $k+1$, y las particiones con ninguna parte que se utiliza más de $k$ veces.

Para ilustrar, con $k=2$. Considere la posibilidad de la partición $$39=1+1+1+1+1+1+1+2+2+2+2+2+2+4+4+4+4+4$$ This partition has no part divisible by $3$. Let's abbreviate it to $1^72^64^5$. Then we go $$1^72^64^5\to1^31^42^64^5\to1^42^634^5\to1^312^634^5\to12^63^24^5\to12^32^33^24^5\to12^33^24^56\to$$

$$\to13^24^56^2\to13^24^34^26^2\to13^24^26^2(12)$$ y tenemos una partición con ninguna parte usarse más de dos veces.

En la otra dirección, supongamos que empezamos con $51=123^24^2567^29$, ninguna parte usarse más de dos veces. Hemos dividido el $9$ en tres $3$s, entonces la $6$ en tres $2$s, entonces cada una de las $3$ en tres $1$s: $$123^24^2567^29\to123^54^2567^2\to12^43^54^257^2\to1^{16}2^44^257^2$$ a partition with no part divisible by $3$.

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