Mostrando entradas con la etiqueta combinatoria. Mostrar todas las entradas
Mostrando entradas con la etiqueta combinatoria. Mostrar todas las entradas

jueves, 15 de marzo de 2018

¿ De cuántas maneras podemos distribuir m lápices iguales entre k personas ?

ENUNCIADO. ¿ De cuántas maneras podemos distribuir $m$ lápices iguales entre $k$ personas ( o $m$ bolas iguales en $k$ urnas ) ?

SOLUCIÓN. Planteémonos primero un problema parecido, pero con números concretos y no muy grandes, para que no sea demasiado difícil establecer, luego, una generalización del resultado que vamos a encontrar. Pongamos que queremos distribuir tres lápices entre dos personas, $P_1$ y $P_2$. Podemos elaborar la siguiente codificación:
=========
|P_1|P_2|
=========
[xxx|   ] 
[   |xxx]
[ xx|  x]
[x  | xx]
Démonos cuenta de que al ser los lápices iguales, no importa el orden en que coloquemos en una misma celda de la tabla, por ello podemos decir que estamos abordando un problema de combinaciones, que no de variaciones, dada la irrelevancia del orden dentro de una misma celda. Por otra parte, elegida una cierta persona para asignar un lápiz, nada nos impide volver a elegirla para asignar otro lápiz, con lo cual el problema en cuestión es de combinaciones con repetición.

Construida la tabla, con todos los casos, podemos hacer fácilmente el recuento aditivo de todas las disposiciones, dando un total de $4$. Ahora bien, no podemos contentarnos con eso, pues si aumentamos el número de lápices o el número de personas, este tipo de recuento resultará inviable. Observemos que la codificación empleada nos hace pensar en el problema de formar "palabras" de $3+2-1$ símbolos: tres "x", y un separador "|" ( uno menos que el número de espacios a rellenar con los tres símbolos "x" ); así que, bien pensado, entendemos ahora de dónde sale el resultado obtenido. Como entre los $3+2-1$ símbolos que hay que forman cada "palabra" ( léase fila de la tabla ) debe haber necesariamente $3$ cruces y $2-1$ barras separadoras tendremos el siguiente número de disposiciones $$\dfrac{(3+(2-1))!}{3!\cdot (2-1)!}=4$$
En consecuencia, la generalización de ésto es inmediata: si se trata de distribuir $m$ lápices iguales entre $k$ personas ( o análogamente, pongamos que, querramos ubicar $m$ bolas iguales en $k$ urnas ), el número de maneras de hacerlo habrá de ser igual a $$\dfrac{(m+(k-1))!}{m!\cdot (k-1)!}$$ lo cual podemos expresarlo como un número combinatorio $$\binom{m+k-1}{m}$$ o lo que es lo mismo -- por las propiedades de dichos números -- podemos escribir también que el resultado es igual a $$\binom{m+k-1}{k-1}$$

Así pues, es ésta la solución a cualquier problema de combinaciones con repetición, de $m$ elementos y de orden $k$, pues representa el número de agrupaciones que se pueden formar tomando $k$ de dichos elementos iguales o distintos y considerando que dos agrupaciones son distintas cuando difieren en algún elemento. En algunos libros se suele notar de la forma $\text{CR}_{k,m}$ o incluso también así $\text{CR}_{k}^{m}$ En resumen,la siguiente expresión resuelve el problema de las combinaciones con repetición de $k$ objetos tomados en grupos de $m$: $$\displaystyle \text{CR}_{k,m}\equiv\binom{k+m-1}{m}=\binom{k+m-1}{k-1}$$

Observación. Si pretendemos aplicar las fórmulas sin mucha reflexión ( lo cual no es acosejable en absoluto ), en estos problemas hay que tener mucha precaución al concebir lo que son "objetos" y "lugares", pues muchas veces es contraintuitivo lo primero que se nos viene en mente. En este problema, por ejemplo, los "objetos" a repartir no son los lápices ( o las bolas ), sino las personas ( o las urnas ), y los "lugares" donde situar los objetos no son las personas ( urnas ), sino los lápices ( bolas ), ya que lo que estamos haciendo es asignar urna a cada bola ( o persona a cada lápiz ). Así, por ejemplo, la respuesta a la pregunta ¿ de cuántas maneras podemos repartir $6$ bolas idénticas ( $6$ lápices idénticos ) en $10$ urnas ( entre $10$ personas ) ? es de $\displaystyle \text{CR}_{10,6}\equiv\binom{10+6-1}{6}=\binom{15}{6}=5005$ maneras distintas
Nota: Las combinaciones con repetición de $n$ elementos de un conjunto en $k$ clases, $CR_{k,n}$, también puede designarse de la forma $\displaystyle \left(\binom{k}{n}\right)$ $\square$

¿ De cuántas maneras podemos distribuir m lápices distintos entre k personas ( o m bolas distintas entre k urnas ) ?

ENUNCIADO. ¿ De cuántas maneras podemos distribuir $m$ lápices, cada uno etiquetado con un número para poder distinguirlos, entre $k$ personas ?

SOLUCIÓN. Planteémonos primero un problema parecido, con números concretos y que no sean éstos muy grandes, para facilitar la comprensión del resultado que encontraremos sin muchas dificultades. Pongamos que queremos distribuir tres lápices, $\ell_1$, $\ell_2$ y $\ell_3$, entre dos personas. Hay $2$ posibilidades para asignar el lápiz $\ell_1$ ( pues podemos elegir dos personas ); también hay otras $2$ posibilidades a la hora de asignar el segundo lápiz $\ell_2$ ( otra vez podemos elegir a cualquiera de las dos personas ), y, desde luego, también hay $2$ posibilidades cando tenemos que asignar el tercer lápiz $\ell_1$ ( otra vez, cualquiera de las dos personas ). Como dichas elecciones las realizamos independientemente unas de otras, por el principio de independencia hay $2\cdot 2 \cdot 2 =2^3=8$ maneras distintas de distribuir los tres lápices.

Generalizando ahora el el problema, es evidente que el número de maneras de distribuir $m$ lápices distintos entre $k$ personas ( o análogamente, $m$ bolas distintas ( etiquetadas con un número, por ejemplo ) en $k$ urnas ) es $k^m$

Démonos cuenta de que al ser relevante el orden en el reparto ( que consite en asignar una persona a cada lápiz, pudiendo volver a elegir una persona, ya asignada, a otro de los lápices ), estamos ante un problema de variaciones, y al poder repetir ( la persona que se asigna a cada lápiz ), diremos que es un problema de variaciones con repetición, $\text{VR}_{k,m}$ ( que en algunos libros se nota también de la forma $\text{VR}_{k}^{m}$ .

Observación. En estos problemas hay que tener mucha precaución al concebir lo que son "objetos" y "lugares", pues muchas veces es contraintuitivo lo primero que se nos viene en mente. En este problema, por ejemplo, los "objetos" a repartir no son los lápices, sino las personas, y los "lugares" donde situar los objetos no son las personas, sino los lápices.

Observación. Si pretendemos aplicar las fórmulas sin mucha reflexión ( lo cual no es acosejable en absoluto ), en estos problemas hay que tener mucha precaución al concebir lo que son "objetos" y "lugares", pues muchas veces es contraintuitivo lo primero que se nos viene en mente. En este problema, por ejemplo, los "objetos" a repartir no son los lápices ( o las bolas ), sino las personas ( o las urnas ), y los "lugares" donde situar los objetos no son las personas ( urnas ), sino los lápices ( bolas ), ya que lo que estamos haciendo es asignar urna a cada bola ( o persona a cada lápiz ). Así, por ejemplo, la respuesta a la pregunta ¿ de cuántas maneras podemos repartir $6$ bolas idénticas ( $6$ lápices idénticos ) en $10$ urnas ( entre $10$ personas ) ? es de $\displaystyle \text{VR}_{10,6}=10^6=1\,000\,000$ de maneras distintas $\square$

lunes, 27 de abril de 2015

Demostrar la siguiente propiedad ... ( Artículo escrito en catalán )

Enunciat:
Designem amb $n$ el cardinal d'un conjunt finit $A$ (nombre d'elements del conjunt). Demostreu la següent propietat:
    $n(A \cup B)=n(A)+n(B)-n(A \cap B)$

Ajuts:

  a) Feu servir les definicions dels conjunts: $\bar{A}$, complementari absolut de $A$; i $\bar{A_{B}}$, complementari de $A$ relatiu a $B$, éssent $A \subseteq U$ i $B \subseteq U$ (on $U$ designa el conjunt universal ). Per tant,
    $\bar{A_{U}}=\{x \in U : x \notin A\}$
    $\bar{A_{B}}=\{x \in A : x \notin B\}$

  b) Feu servir la següent propietat (que considerarem trivial):
    Si $A \cap B = \varnothing$, llavors
    $n(A \cup B) = n(A)+n(B)$


Solució:
Considerant el fet que
    $\bar{A_{B}} \cap B = \varnothing$
podem escriure la unió de $A$ i $B$ de la forma
    $A \cup B = \bar{A_{B}} \cup B$
i per la propietat (b)
    $n(A \cup B) = n\big(\bar{A_{B}}\big) + n(B) \quad \quad (1)$
Tenint en compte, ara, que
    $A=\bar{A_{B}} \cup (A \cap B)$
i que
    $\bar{A_{B}} \cap (A \cap B) = \varnothing$
emprant, altra vegada la propietat (b), escriurem
    $n(A)=n(\bar{A_{B}}) + n(A \cap B)$
i, per tant,
    $n(\bar{A_{B}})=n(A) - n(A \cap B)$
que substituït en (1) permet arribar a la igualtat que volíem demostrar
    $n(A \cup B) = n(A) + n(B) - n(A \cap B)$
$\square$

Observació:   Per inducció es poden demostrar altres propietats que es desprenen d'aquesta que acabem de demostrar, tot generalitzant-la, per exemple:
    $n(A \cup B \cup C) = \ldots $
        $= n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$
Totes aquestes propietats són molt útils per al càlcul de probabilitats.

[nota del autor]