Distribución de bolas (iguales) en urnas sabiendo que algunas de las urnas tienen que quedar vacías

Continuando con los problemas de « bolas y urnas », ligados al patrón de combinaciones con repetición. El caso que se presenta ahora es similar al anterior, sin embargo, ahora fijaremos el número de urnas que deben quedar vacías al distribuir entre ellas un cierto número de bolas.

ENUNCIADO.
  a) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que $s$ cualesquiera de las urnas queden vacías ($s\le k$)?
  b) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que $s$ determinadas urnas queden vacías ?


SOLUCIÓN. En un artículo anterior se ha resuelto el problema básico de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$
a) Como $s$ urnas tienen que quedar vacías, ahora $k:=k-s$ en la solución del problema genérico, con lo cual tendremos $$\displaystyle \left(\binom{k-s}{n}\right)=\binom{n+((k-s)-1)}{(k-s)-1}=\binom{n+k-s-1}{k-s-1}\,\text{posibilidades}$$

b) Si $s$ determinadas urnas del total de $k$ urnas ($s\ge k$) tienen que quedar vacías, el problema difiere el algo del del apartado anterior. Debemos contabilizar primero de cuántas manera podemos elegir esas $s$ urnas que deberán quedar vacías, y ello se puede hacer de $\displaystyle \binom{k}{s}=k$ maneras distintas. A continuación, razonaremos de la siguiente manera: como de las $k-s$ urnas restantes no deberá quedar ninguna vacía, procedamos a ubicar exactamente $1$ bola en cada una de ellas para poder garantizar tal cosa, y, a continuación, veamos de cuántas manera podemos distribuir las $n-(k-s)$ bolas que nos quedan entre las $k-s$ urnas que deberán contener al menos una bola: estableciendo pues $n:=n-(k-s)$ y $k:=k-s$ en la solución genérica de distribución de bolas iguales en urnas distintas, la solución a este problema de reparto entre las urnas no vacías es $$\displaystyle \left(\binom{k-s}{n-(k-s)}\right)=\binom{(n-(k-s))+(k-s)-1}{(k-s)-1}=\binom{n-1}{k-s}$$
Por consiguiente, teniendo en cuenta además (como ya hemos dicho) las posibilidades que tenemos de elegir las $s$ urnas que han de quedar vacías, tendremos un total de $$\displaystyle \binom{k}{s}\cdot\binom{n-1}{k-s}\,\text{posibilidades}$$

-oOo-
Veamos un caso concreto: EJEMPLO. Supongamos que tenemos $n:=8$ bolas a distribuir en $k:=4$ urnas, de entre las cuales:
  (1) $s:=3$ urnas cualesquiera han de quedar vacías
  (2) $s:=3$ urnas prefijadas han de quedar vacías
¿De cuántas maneras se podrá hacer eso?


SOLUCIÓN.
Recordemos ahora que $n:=8$, $k:=4$ y $s:=3$, luego de las soluciones genéricas deducidas arriba, obtenemos los siguientes resultados:

  (1)             $\displaystyle \binom{8+4-3-1}{4-3-1}=\binom{8}{0}=1$ posibilidad

  (2)             $\displaystyle \binom{4}{3}\cdot \binom{8}{0}=4 \cdot 1=4$ posibilidades
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995

Otro problema de distribución de bolas (iguales) en urnas

Seguimos con los problemas de « bolas y urnas », ligados al patrón de combinaciones con repetición. Y, por supuesto, aprovecharemos lo que se ha estudiado ya con anterioridad.

ENUNCIADO.
  a) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que una de las urnas contenga exactamente $r$ bolas ($r\le n$)?
  b) ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), de manera que, elegida una determinada urna, ésta contenga exactamente $r$ bolas ($r\le n$)?


SOLUCIÓN. En un artículo anterior se ha resuelto el problema básico de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$
a) Si una de las $k$ urnas (cualquiera de ellas) tiene que contener exactamente $r\le n$ bolas, debemos resolver el problema de repartir $n-r$ urnas en $k-1$ urnas, así que, en la solución básica tendremos que $n:=n-r$ y $k:=k-1$, con lo cual el número de posibilidades es $$\displaystyle \left(\binom{k-1}{n-r}\right)=\binom{(n-r)+((k-1)-1)}{(k-1)-1}=\binom{n-r+k-2}{k-2}$$

b) Si una urna determinada de las $k$ urnas tiene que contener exactamente $r\le n$ bolas, el problema difiere el algo del del apartado anterior. Debemos contabilizar primero de cuántas manera podemos elegir la urna que contiene exactamente $r$ bolas, y ello se puede hacer de $\displaystyle \binom{k}{1}=k$ maneras. A continuación, razonaremos de la siguiente manera: por cada una de esas $k$ posibilidades, sabemos que existen (por la solución encontrada en el apartado anterior) otras tantas $\displaystyle \binom{n-r+k-2}{k-2}$ maneras de distribuir las $n-r$ bolas en las restantes $k-1$ urnas. Finalmente, por tanto, tendremos un total de $$\displaystyle \binom{k}{1}\displaystyle \binom{n-r+k-2}{k-2}=k\,\binom{n-r+k-2}{k-2}\,\text{posibilidades}$$

-oOo-
Veamos un caso concreto: EJEMPLO. Supongamos que tenemos $n:=8$ bolas a distribuir en $k:=4$ urnas, de entre las cuales:
  (1) en una de ellas (una cualquiera) deberá haber $r:=3$ bolas
  (2) en una determinada urna (prefijada) deberá haber $r$ bolas
¿De cuántas maneras se podrá hacer eso?


SOLUCIÓN.
Recordemos ahora que $n:=8$, $k:=4$ y $r:=3$, luego de las soluciones genéricas deducidas arriba, obtenemos los siguientes resultados:

  (1)             $\displaystyle \binom{8-3+4-2}{4-2}=\binom{7}{2}=6$ posibilidades

  (2)             $\displaystyle \binom{4}{1}\cdot \binom{8-3+4-2}{4-2}=4 \cdot 6=24$ posibilidades
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995

Del problema de contar el número de maneras de distribuir n bolas iguales entre k urnas identificables (n mayor o igual que k) — de forma que no quede ninguna urna vacía — al problema de contar « rachas »

Nos vamos a plantear ahora un problema que encaja en el patrón de las combinaciones con repetición: el de distribuir un cierto número de bolas iguales en un conjunto de urnas, de tal modo que cada urna vaya a contener por lo menos una bola. Para ello, aprovecharemos lo que se ha estudiado ya con anterioridad. A su vez, este problema constituye, como veremos, un patrón para resolver el de las rachas que se obitienen al extraer bolas de manera sucesiva de una urna que contiene un cierto número de bolas blancas y un cierto números de bolas negras, hasta que ésta quede vacía.

ENUNCIADO. ¿De cuántas maneras es posible distribuir $n$ bolas iguales en $k$ urnas (identificables), siendo $n\ge k$, de forma que no quede vacía ninguna urna?.

SOLUCIÓN. En el artículo anterior se ha resuelto el problema de repartir $n$ bolas iguales en $k$ urnas, en el que se había justificado que la solución consiste en calcular el número de combinaciones con repetición de $n$ bolas elegidas en una gama de $k$ clases: $$\displaystyle \left(\binom{k}{n}\right):=\dfrac{(n+(k-1))!}{n!\,(n-k)!}=\binom{n+(k-1)}{n}=\binom{n+(k-1)}{k-1}$$ Sin embargo, ahora debemos garantizar que ninguna urna va a quedar vacía, por lo que empezaremos ubicando exactamente una bola en cada urna; y, a continuación, procederemos a distribuir las $n-k$ bolas restantes entre las $k$ urnas. Así, el problema es análogo al que ya tenemos resuelto, pero con $k$ bolas menos. Entonces, la solución al mismo es: $$\displaystyle \left(\binom{k}{n-k}\right)\overset{def}{=}\dfrac{(n-k+(k-1))!}{(n-k)!\,(n-k)!}=\dfrac{(n-1)!}{(n-k)!(n-1-(n-k)!}=\dfrac{(n-1)!}{(n-k)!(k-1)!}=\binom{n-1}{k-1}=\binom{n-1}{n-k}\quad \quad [1]$$
-oOo-
Veamos un caso concreto sobre esto: EJEMPLO 1. ¿De cuántas maneras podemos distribuir $5$ bolas iguales entre $3$ urnas, de manera que no quede ningua urna vacía?.

SOLUCIÓN. Ahora, $n:=5$ y $k:=3$, luego podremos hacerlo de $$\displaystyle \left(\binom{3}{5-3}\right)=\left(\binom{3}{2}\right)=\binom{5-1}{3-1}=\binom{4}{2}=6\,\text{maneras}$$

***

OBSERVACIÓN (El problema de las « rachas »):
  Una bonita aplicación —de la que se habla en (Hernández, 1995)— es el de contar las rachas al extraer de manera sucesiva de una urna que contiene, en un principio, $b$ bolas blacas y $n$ bolas negras, hasta que la que la urna queda vacía, obteniendo secuencias del tipo $BBNNNBBBNBNNNN\,\ldots$. ¿Cuántas rachas formadas de $k$ bolas blancas y $k+1$ bolas negras &mdsh; donde, lógicamente, $k$ deberá cumplir que $k\le a$ y $k+1\le b$ — es posible obtener?.

SOLUCIÓN: Para resolver este problema podemos pensar en el problema patrón de distribuir un cierto número de bolas iguales en un conjunto de urnas, de manera que ninguna de las urnas quede vacía, esto es, de modo que, tras acabar la operación de ubicación de las bolas en las urnas, cada urna acabe conteniendo al menos una bola. Cada racha una de las $k$ rachas de bolas blancas puede asociarse a la distribución de $a$ bolas blancas en $k$ urnas (sin que ninguna de ellas quede vacía); sabemos, de [1] (haciendo $n:=a$) que esto puede hacerse de $\displaystyle \binom{a-1}{k-1}$ maneras, y contabilizando también las $k+1$ rachas de bolas negras intercaladas entre dos rachas de bolas blancas, vemos que, por cada una de esas posibilidades ($k$ rachas de bolas blancas), hay $\displaystyle \binom{b-1}{k+1)-1}=\binom{b-1}{k}$ (haciendo en [1] $n:=b$ y $k:=k+1$). Así pues, tendremos un total de $$\displaystyle \binom{a-1}{k-1}\cdot \binom{b-1}{k}\,\text{maneras de obtener}\,k\,\text{rachas de bolas blancas, y}\,k+1\,\text{rachas de bolas negras}$$ EJEMPLO 2. Consideremos una urna que contiene $8$ bolas, $3$ de las cuales son blancas y $5$ son negras. Nos dedicamos a extraer bolas, de manera sucesiva, hasta que la urna quede vacía. ¿De cuántas maneras pueden darse $2$ rachas de bolas blancas ($k:=2$), estando intercaladas por tanto (dichas rachas), entre $3$ rachas de bolas negras ($k+1=2+1=3$)?.

SOLUCIÓN. Ahora, $a:=3$ y $b:=5$, y $k:=2$, luego tal cosa podrá suceder de $$\displaystyle \binom{3-1}{2-1}\cdot \binom{5-1}{2}=\binom{2}{1}\cdot \binom{4}{2}=2\cdot 6=12\,\text{maneras}$$
$\square$

-oOo-

Referencias:
  [1] Hernández, V.; Vélez, R.: Dados, monedas y urnas, UNED, Madrid, 1995