6 votos

Particiones de $0$ $1$ por enteros en el intervalo de $[-N,\ldots,N]$

De fondo

A menudo uno se encuentra con el problema de tratar de encontrar el número de formas de dividir un entero positivo en una suma de números enteros no negativos. Hay tres formas de dividir el número 3, por ejemplo: \begin{align} 3 &= 3+0,\\ 3 &= 1+2,\\ 3 &= 1+1+1.\\ \end{align} Los dos primeros son una partición de $3$ a $2$ números enteros no negativos. La última es una división en $3$ números enteros no negativos.

La declaración del problema

Por otro lado, se podría considerar que el número de formas de dividir un número con más de un conjunto diferente. Estoy interesado en el caso de que los números de "hacer la partición" se dibujan a partir del conjunto $$ S_N = [-N,\ldots,N] $$ (con repeticiones permitidas) y los números de particiones se $0$$1$. En el caso general, $m$ se permiten los números para ser elegido de $S_N$ al hacer la partición.

Ejemplo

Supongamos $N = 1$, por lo que el $S_1 = \{-1,0,1\}$. Supongamos primero buscamos particiones en dos enteros -- en otras palabras, tome $m =2$. A continuación, $0$ se puede dividir en dos enteros de $S_1$ en la de dos maneras distintas, como se muestra a continuación: \begin{align} 0 &= 0 + 0 \\ 0 &= 1 + (-1), \end{align} $1$ puede ser dividida en una sola forma: \begin{align} 1 &= 1 + 0. \\ \end{align} Para $m=3$, $0$ puede ser dividido en dos maneras distintas de nuevo, \begin{align} 0 &= 0 + 0 + 0\\ 0 &= 1 + (-1) + 0, \end{align} mientras que $1$ ahora también puede ser particionado en dos formas distintas, \begin{align} 1 &= 1 + 0 + 0\\ 0 &= 1 + 1 + (-1). \end{align}

Existe una solución para el caso general?

Me pregunto si este problema puede ser resuelto en el caso general (para todos los $N$$m$) en forma cerrada. Referencias bibliográficas son bienvenidos. Gracias!

Edit: para responder a los comentarios, en el caso de $0$ ($1$), lo que estoy buscando es, de hecho, el coeficiente de $x^m y^0$ ($x^m y^1$) en la parte formal de la serie definida por $$ g(x,y) = \frac{1}{\prod_{k=-N}^{k=+N}(1-x y^k)}. $$

1voto

Fimpellizieri Puntos 155

Deje $P(k,m,N)$ denotar el número de distintas particiones de un número entero $k$ a $m$ partes en el entero del intervalo de $[-N,\dots,N]$.

Para cada entero $-N\leq n\leq N$, vamos a $LP(n\,;k,m,N)$ denotar el número de distintas particiones de un número entero $k$ a $m$ partes en el entero del intervalo de $[-N,\dots,N]$ y de tal manera que el valor de una de sus menos una parte(s)$n$.

Entonces tenemos

$$P(k,m,N)=\sum_{n=-N}^NLP(n\,;k,m,N)$$

Ahora, vamos a $p$ ser alguna partición contado por $LP(n\,;k,m,N)$. Podemos asociar a $p$ una única partición $\stackrel{\sim}{p}$ $k-m(n-1)$ a $m$ partes en el entero del intervalo de $[1,\dots,N-(n-1)]$, y de tal manera que el valor de (uno de) por lo menos su parte(s)$1$. Para ello, basta con restar $n-1$ de cada parte de la $p$. Observe que, en este punto, $\stackrel{\sim}{p}$ es un clásico de la partición.

Todavía es posible alterar $\stackrel{\sim}{p}$ mediante la eliminación de una de sus menos una parte(s), por lo tanto la obtención de alguna partición $p^*$ $k-mn+(m-1)$ a $m-1$ partes en el entero del intervalo de $[1,\dots,N-(n-1)]$.

Por conjugación, $p^*$ corresponde a una única partición $\overline{p}$ $k-mn+(m-1)$ en la mayoría de los $N-(n-1)$ partes y con la mayor parte de las $m-1$. La eliminación de una parte más grande, se obtiene finalmente una partición $\hat{p}$ $k-mn$ en la mayoría de los $N-n$ partes y con la parte más grande en la mayoría de las $m-1$.

En la obvia la notación, vamos a $\hat{P}(k,N,m)$ recuento de las particiones en este camino, de modo que, por ejemplo, nuestra $\hat{p}$ por encima de los obtenidos a partir de nuestras inicial $p$ serán contados por $\hat{P}(k-mn,N-n,m-1)$. Entonces tendríamos

$$P(k,m,N)=\sum_{n=-N}^N\hat{P}(k-mn,N-n,m-1)$$


Particiones contado por $\hat{P}$ han sido estudiados y descritos a través de Gauss coeficientes binomiales (o $q$-los coeficientes binomiales; véase $q$-analógico).

Utilizamos $q^n\left[f(q)\right]$ para denotar el coeficiente de $q^n$ en el poder de expansión de la serie de $f(q)$$0$. Con esta notación, tenemos

$$P(k,m,N)=\sum_{n=-N}^N\,q^{k-mn}\left[\binom{m-1+N-n}{N-n}_q\right]$$

No estoy seguro cuánto más simple que su respuesta original es esta. Supongo que depende de lo fácil o lo eficiente que es para usted para calcular los polinomios $\binom{m}r_q$.

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