Loading [MathJax]/extensions/TeX/mathchoice.js

4 votos

¿De cuántas maneras se pueden distribuir n bolas idénticas en k cajas distintas, de modo que al menos una caja esté vacía?

Este es un problema en mi combinatoria libro que utiliza el principio de inclusión-exclusión. Puedo seguir casi todo de lo que se dice, excepto el libro dice que si tenemos en cuenta Ai a ser el conjunto de soluciones donde el cuadro i es vacía, entonces |A_{i}| = {n-(k-1)-1 \choose k-1}.

El libro no explica por qué esto es cierto. Y quiero saber por qué, ya que yo pensaba que |A_{i}| = {n+(k-1)-1 \choose k-1}.

Por lo que se puede llegar a la raíz de mi incomprensión, mi razonamiento fue que una colocación de n bolas iguales en k cajas distintas es el mismo que el número de número entero no negativo soluciones a x_{1}+\cdots+x_{k} = n.

Cualquier ayuda sería muy apreciada!

4voto

Hagen von Eitzen Puntos 171160

Para empezar, solucionaría el problema de manera diferente: por estrellas y barras, hay n-1\choose k-1 maneras de colocar n bolas en k contenedores, de modo que no hay ningún contenedor vacío. Resta esto de las maneras n+k-1\choose k-1 para colocar n balls en k bins sin restricción.

1voto

G Cab Puntos 51

Primero de todo, dejar claro que, en el común de hablar
"la distribución de n idénticos (inapreciable) bolas en k distintos (distinguibles) cajas" no tiene la misma acepción como
"el lanzamiento de n idénticos (inapreciable) bolas en k distintos (distinguibles) cajas"

En el primer caso (distribución, verter, ..) se entiende que se considera el número de diferentes ocupación hystograms, es decir, el número de k-tuplas (x_1,x_2, \cdots , x_k) tales que \left\{ \matriz{ {\rm 0} \le {\rm integer}\;x_{\,j} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = n \hfill \cr} \right. que son "débiles", Composiciones de n a k partes,
y en su caso particular, el complemento del caso en el que el cuadro no está vacía \left\{ \matriz{ {\rm 1} \le {\rm integer}\;x_{\,j} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = n \hfill \cr} \right.\quad \Rightarrow \quad \left\{ \matriz{ {\rm 0} \le {\rm integer}\;y_{\,j} \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,k} = n - k \hfill \cr} \right. que son el "estándar" Composiciones de n a k partes.

Como se explica en la que se hace referencia en el artículo son, respectivamente, N_w = \binom{n+k-1}{n} \quad N_s =\binom{n-1}{n-k} \quad \left| {\;0 \le n,k} \right. tenga en cuenta que esta forma de escritura de los binomios se extiende la definición también nulos los valores de los parámetros. La repartición de N_w sobre las configuraciones con exactamente j cajas vacías está dada por N_w = \binom{n+k-1}{n} = \sum\limits_{\left( {0\, \le } \right)j\left( { \le k} \right)} {\binom{k}{j} \binom{n-1}{n - \left( {k - j} \right) } }

El número de configuraciones en las que, precisamente, el cuadro de i está vacía, entonces claramente se N_w(n,k-1) si los demás pueden estar vacías o no, y N_s(n,k-1) si los demás son no vacíos.
Así que tienes razón, y la respuesta global a su problema N = N_w - N_s = \binom{n+k-1}{n} - \binom{n-1}{n-k}

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