Argumentos básicos de conteo 3 (Combinaciones)

Versión para impresión

Intro

En este post vamos a derivar la fórmula para las combinaciones de n objetos tomados de r en r. Así se decía antes, ahora se prefiere decir el número de subconjuntos de tamaño r tomados de un conjunto de tamaño n. De nuevo, aquí lo importante es el razonamiento combinatorio que da lugar a la fórmula.

Instancias de uso

Instancia 1 (r-subconjuntos)

¿De cuantas formas se pueden elegir r objetos de entre n etiquetados $1,2,\ldots,n$?

Nota: una elección de r objetos de entre n etiquetados $1,2,\ldots,n$ forma un subconjunto de tamaño r del conjunto $\{1,2,\ldots,n\}$.

Solución

Sea C(n,r) el número de elecciones posibles de r objetos de entre n etiquetados $1,2,\ldots,n$. Las r-listas (listas de tamaño r de los n objetos $1,2,\ldots,n$ se pueden clasificar según el subconjunto de tamaño r que representan (cada r-lista son los elementos de un r-subconjunto tomados en un cierto orden). Para cada r-subconjunto hay r! r-listas. En otras palabras, la clasificación resulta en C(n,r) clases. De aquí que $r!C(n.r)=n!/(n-r)!$. Es decir $C(n.r)=n!/[(n-r)!r!]$.


Nota: Cualquier conjunto de n objetos puede etiquetarse de tal manera que quede representado por el conjunto genérico $\{1,2,\ldots,n\}$. Por ejemplo, el conjunto $\{A, B, C, D, E\}$ quedaría representado por $\{1,2,3,4,5\}$ etiquetando sus elementos en algún orden.

Instancia 2 (orden lexicográfico)

Las posibles elecciones de tres elementos (3-subconjuntos) de $\{A, B, C, D, E\}$ se pueden generar en orden lexicográfico de una por una y son:

{A, B, C},
{A, B, D},
{A, B, E},
{A, C, D},
{A, C, E},
{A, D, E},
{B, C, D},
{B, C, E},
{B, D, E},
{C, D, E}.

Contexto para el ejemplo anterior: Adán, Boris, Carlos, Denise y Elena son 5 adolescentes aficionados a las matemáticas y decidieron hacer una petición al director de su escuela para que se ofrezca un taller de matemáticas de concurso por las tardes. Al llegar a la dirección y solicitar la audiencia, el director les comunicó a través de su secretaria que recibiría a tres de ellos. ¿De cuántas formas se puede elegir la 3-comisión que hablará con el director?

Nota (a la enumeración de soluciones): Generalmente no nos importa cuáles son sino más bien cuántas son. En este sentido es que enlistarlas todas es un desperdicio de recursos. Según la fórmula recién obtenida C(5,3)=5!/(2!3!)=10.

Clases de equivalencia


El argumento de clasificación anterior agrupa todas las 5(4)3=60 3-listas de acuerdo al subconjunto que representan. Por ejemplo las 3-listas que representan al subconjunto {A, B, C} son ABC,ACB,BAC,BCA,CAB,CBA. Y son 10 clases, una para cada subconjunto. El argumento de clasificación se formaliza matemáticamente a través del concepto de clases de equivalencia (dada una relación de equivalencia entre los elementos).

Definimos la relación entre r-listas como "tiene los mismos elementos que". Para usarla formalmente habría que probar que es una relación de equivalencia entre r-listas; es decir, que cumple las tres propiedades de reflexividad (una r-lista tiene los mismos elementos que sí misma), transitividad (si tres r-listas $_1,l_2,l_3$ son tales que $l_1$ tiene los mismos elementos que $l_2$ y $l_2$ tiene los mismos elementos que $l_3$ entonces $l_1$ tiene los mismos elementos que $l_3$) y simetría (si $l_1$ tiene los mismos elementos que $l_2$ entonces $l_2$ tiene los mismos elementos que $l_1$).

La diferencia entre r-combinaciones y r-listas es que en éstas se consideran diferentes dos listas que, a pesar de que tienen los mismos elementos, éstos están enlistados en orden diferente; en cambio en las r-combinaciones son diferentes dos de ellas si y sólo si difieren en al menos un elemento. Desde el punto de vista del modelo de urna, para las r-listas se extraen sin reemplazo y en sucesión r bolas de una por una; en cambio para las r-combinaciones se extraen todas las r en una sola extracción.

Solución alternativa al problema de la fórmula de las combinaciones

Las r-listas se pueden generar de dos formas: 1) obtenemos todos los C(n,r) subconjuntos de tamaño r, y después generamos --con cada uno de ellos-- las r-listas a que dan lugar, permutando sus elementos en todos los órdenes posibles (esto da lugar a r!C(n,r) posibilidades), 2) obtenemos las r-listas de la manera usual, es decir, hay n posibilidades para el primer elemento, n-1, para el segundo etc. Como los dos métodos cuentan lo mismo, se tiene la ecuación r!C(n,r)=n!/(n-r)!

Nota: este tipo de argumento es muy útil en combinatoria y se denomina doble conteo (del mismo conjunto); como las dos formas de contar cuentan los elementos de un mismo conjunto se puede establecer una ecuación. (En la solución alternativa faltaría un argumento para demostrar que realmente los dos métodos cuentan lo mismo --pero esa es una tarea que se hará después y no dudamos que el lector la podrá hacer por su cuenta.)

Más instancias de uso

Muchas veces elegir r objetos de entre n etiquetados $1,2,\ldots,n$ se aplica a elegir r lugares de entre n (que uno puede imaginar como las posiciones de una palabra o de una cadena de dígitos y/o letras o asientos en una hilera de sillas, o posiciones en una línea de espera (cola), etc. Es decir, el problema equivalente es el de elegir r posiciones de entre n dadas.

Instancia 3 (palabras en un alfabeto)

¿Cuántas 3-palabras con el alfabeto $\{A, B, C, D, E\}$ tienen exactamente dos A's?

Solución: primero se eligen los lugares para las A's de C(3,2)=3 formas y después, en el lugar no ocupado se coloca cualquiera de las 4 letras no A de 4 formas; por el principio multiplicativo la respuesta es 3(4)=12 formas. Enseguida se enlistan las posibilidades:
AAB
ABA
AAC
ACA
AAD
ADA
AAE
AEA
BAA
CAA
DAA
EAA

Instancia 4 (separadores)

En la línea de espera de un aeropuerto se ha establecido la política de que no deben estar dos niños consecutivos en la línea. Si tenemos a 7 adultos y tres niños para colocarse en la fila ¿de cuántas forams se pueden formar respetando esa política?

El problema es muy difícil si uno trata de razonarlo de la manera usual de quién primero, quién después etc. El truco de los separadores es pensar el problema imaginando los 7 adultos en línea y los espacios entre dos consecutivos además de los dos extremos. Esto facilita el razonamiento pues ahora se puede razonar como elegir 3 espacios para los niños de entre los 8 disponibles. "Elijo los 3 lugares de entre los 8 de C(8,3), permuto los niños colocados en esos 3 lugares de 3! fromas y permuto los adultos de 7! formas" La respuesta es entonces C(8,3)(6)(7!).

Estos dos ejemplos imponen restricciones a las configuraciones ("3-palabras con 2 A's", "que no haya dos niños juntos en la fila"). El lector se dará cuenta de que es totalmente insuficiente el conocer las fórmulas para las n-listas, r-listas, las r-combinaciones. Lo importante es el razonamiento combinatorio usando el principio multiplicativo.

Los saluda
jmd
 

Ver también: 
Principio multiplicativo
Ver también: 
Combinatoria