Resumen Nociones Básicas de Combinatoria

Introducción: conjuntos finitos e infinitos.
Un conjunto X puede indicarse enumerando sus elementos o bien describiéndose por medio de una propiedad que lo define.
Por ejemplo, X={manzana,casa,nube}, es un conjunto dado por mera enumeración.
Y por ejemplo, X={xR:x>3x<2π} es un conjunto definido por comprensión (a través de una propiedad).
Contar los elementos de un conjunto X quiere decir que asignamos un número natural a cada elemento del conjunto, hasta llegar al último de ellos, digamos n. En caso de poder hacer esto, decimos que X es finito, tiene n elementos. También se dice que el cardinal de X es igual a n.
Cuando no es posible asignar un número natural n de esta forma a un conjunto X, debido a que ningún número natural es suficiente, entonces decimos que X es un conjunto infinito. Por ejemplo, el conjunto de los números enteros impares es infinito (formalmente: X={2n+1:nZ} es infinito), y también el conjunto de los números reales mayores que 19, es infinito (formalmente: X={xR:x>19} es infinito).
En lo que sigue, vamos a tratar sólo con conjuntos finitos, y con diversas estrategias de conteo.
Aclaración importante: lo que sigue es sólo un resumen muy reducido de la teoría dada en clase.
Otra aclaración importante: se aceptan conjuntos vacíos, en cuyo caso el cardinal es 0.

1. Distinguir entre conjuntos y listas.
Un conjunto X está bien determinado si es posible dar un criterio que claramente especifica si un elemento z pertenece a X o si z no pertenece a X.
Como se trata de una mera cuestión de pertenencia o no, no interesa el orden en que se indican los elementos del conjunto.
Así, los siguientes conjuntos son todos iguales, porque contienen los mismos elementos:
{mesa,silla,cama}{silla,mesa,cama}{cama,mesa,silla}.

Más aún, si se repiten elementos en la descripción, es una mera redundancia, porque el conjunto sigue siendo el mismo.
Por ejemplo, si escribimos:
{mesa,silla,cama,silla,silla},

el conjunto es el mismo que antes, no ha cambiado. El hecho de que hayamos nombrado el elemento "silla" 3 veces no quiere decir que hay 3 sillas, sino que hay una sola, y que la hemos mencionado varias veces en forma redundante.
Una situación bien diferente es el caso de las listas ordenadas.
En una lista ordenada, la intención es indicar elementos que vienen en un orden determinado, y tal que los elementos pueden repetirse, pues procura modelar una situación en la cual es importante el orden y la repetición de elementos.
Por ejemplo, si queremos enumerar las letras de una palabra, por ejemplo: EVEREST (la montaña más alta del mundo),
entonces la lista sería: (E, V, E, R, E, S, T).
Para la palabra EVEREST usamos el conjunto de letras: {E, V, R, S, T}.
Pero también notamos que la letra E aparece 3 veces, y el resto de letras aparece 1 sola vez.
Y más aún, a fin de identificar el nombre de la montaña más alta del mundo,
esas letras deben aparecer en un orden específico: E, V, E, R, E, S, T.
El conjunto de letras {E, V, R, S, T} tiene 5 elementos,
pero la longitud de la lista (E, V, E, R, E, S, T) es de 7 posiciones.
Observemos que la notación de llaves {.....} es la que usamos para conjuntos (que contienen elementos en los que se desestima el orden en que figuran, y sólo se cuenta una repetición de cada uno, a lo sumo),
mientras que la notación de paréntesis (....) es la que usamos para listas ordenadas.
Usaremos la notación #(A) para indicar el cardinal (número de elementos) de un conjunto A,
y denotaremos (L) la longitud (número de posiciones) de una lista ordenada L.

2. Conteo de la unión de dos conjuntos (no necesariamente disjuntos).
Supongamos que tenemos dos conjuntos finitos A y B, tales que A tiene m elementos, y B tiene n elementos.
Aquí tenemos que m y n son números enteros positivos, o bien son 0.
¿Cuál es el cardinal de AB, es decir, de la unión de A y B?
Hay muchas maneras de responder esta pregunta,
pero tenemos que tener claro siempre que:
Al contar los elementos de A y de B, estamos contando 2 veces los elementos que están al mismo tiempo en ambos conjuntos, es decir, en su intersección AB.
Por lo tanto, escribimos:
#(AB)=#A+#B#(AB).

Esta fórmula tiene pleno sentido, pues al sumar #A y #B, hemos contado por duplicado los elementos que pertenecen a ambos conjuntos (es decir, a AB), pero entonces basta restar el cardinal de #(AB) para corregir el desfasaje y obtener el resultado correcto.
Por ejemplo, si sabemos que un grupo de deportistas tiene 15 alpinistas, 20 paracaidistas, y de entre ellos sabemos que hay 7 personas que son al mismo tiempo alpinistas y paracaidistas, ¿cuántos deportistas hay? La respuesta es:
#(deportistas) = #(alpinistas) + #(paracaidistas) - #(alpinistas y paracaidistas) = 15 + 20 - 7 = 28.
¿Está usted de acuerdo con este resultado?
Hay fórmulas más generales para la unión de una cantidad arbitraria (finita) de conjuntos.
No vamos a repetir esas fórmulas aquí.
Solamente pondremos un ejemplo para 3 conjuntos.
Consideremos personas que simpatizan con distintos partidos políticos, incluso varios partidos a la vez,
y supongamos que no se sabe el total de personas encuestadas, sino sólo la cantidad que ha manifestado simpatía con uno u otro partido. Hay personas a las que les ha simpatizado más de un partido.
Hay 20 que simpatizan con el partido Rojo, 15 que simpatizan con el partido Azul, y 11 que simpatizan con el partido Verde.
Pero también hay 8 que simpatizan a la vez con el Rojo y el Verde, y 5 que simpatizan con el Verde y el Azul.
Finalmente, hay 3 personas que simpatizan con los tres partidos.
El número de personas se calcula así
#(Personas) = #(Rojo) + #(Azul) + #(Verde) - #(Rojo y Azul) - #(Rojo y Verde) - #(Verde y Azul) + #(Rojo y Verde y Azul)
Luego:
#(Personas) = 20 + 15 + 11 - 0 - 8 - 5 + 3 = 36.

3. Conteo del producto cartesiano de dos conjuntos.
Dados dos conjuntos A y B, ¿cuántos pares ordenados pueden formarse con elementos de A y de B?
Primero que nada, digamos que el conjunto de todos los posibles pares ordenados se denota A×B.
Como se consideran todos los apareamientos posibles,
el total es igual al producto de elementos de A por el de elementos de B.
Ejemplo: en una fiesta de casamiento, se obliga a que todos los hombres (que son 9) saquen a bailar a todas las mujeres (que son 14), exactamente una vez durante la noche de la fiesta. Esto da un total de 914=126 bailes en la noche.

4. Conteo de listas ordenadas a partir de elementos de un conjunto dado.
Consideremos un conjunto X con n elementos, digamos: X={a1,a2,a3,,an}.
¿Cuántas listas ordenadas de longitud k podemos formar con los elementos de X?
Para esto, procuremos visualizar k casilleros vacíos, y en cada uno de ellos podemos poner una copia de cada uno de los elementos de X.
Es decir, en cada casillero vacío podemos elegir entre las n posibilidades.
La cantidad de posibilidades se obtiene multiplicando k veces el número n de posibilidades de cada casillero.
O sea que en total hay nk casos posibles.
Ejemplo: ¿cuántas cadenas de caracteres de longitud 3 pueden formarse con el conjunto de caracteres {'A','B','C','D'}?
Dado que el conjunto tiene 4 caracteres, y cada caracter tiene permitido repetirse en cada una de las 3 posiciones de la cadena de caracteres, el total de posibilidades es 43=64. Sólo por esta vez, las enumeraremos a todas, para tener un ejemplo concreto a partir del cual reflexionar por qué es verdad la fórmula nk en este caso:
AAA AAB AAC AAD ABA ABB ABC ABD ACA ACB ACC ACD ADA ADB ADC ADD
BAA BAB BAC BAD BBA BBB BBC BBD BCA BCB BCC BCD BDA BDB BDC BDD
CAA CAB CAC CAD CBA CBB CBC CBD CCA CCB CCC CCD CDA CDB CDC CDD
DAA DAB DAC DAD DBA DBB DBC DBD DCA DCB DCC DCD DDA DDB DDC DDD
5. Permutaciones: conteo de las maneras en que se puede ordenar un conjunto.
Consideremos un conjunto que tiene n elementos distintos:
X={a1,a2,,an}.

¿De cuántas maneras se pueden listar ordenadamente los elementos de ese conjunto, sin que se repitan elementos?
Para resolver esta cuestión, notemos que toda tal lista ordenada tiene que tener los n elementos puestos en algún orden.
Imaginemos pues n casilleros, en los cuales vamos poniendo los n elementos del conjunto.
En el primer casillero podemos poner cualquiera de los n elementos, es decir, tenemos n posibilidades para elegir con toda libertad.
Una vez que hemos elegido ese primer elemento, en el segundo casillero podemos elegir sólo entre los restantes elementos que nos quedan del conjunto, que son n1. Tomamos uno de ellos y lo ponemos en el casillero.
Ahora en el tercer casillero, podemos elegir entre las n2 posibilidades restantes, de entre los elementos del conjunto que aún no hemos elegido.
Así vamos llenando de uno en uno los casilleros, hasta llegar al último, en el que hay una sola opción, el último elemento que ha quedado sin elegir en ese momento.
Por lo tanto, la cantidad de formas en que podemos elegir la manera de ubicar estos n elementos es el producto:
n(n1)(n2)1.

Ese producto se abrevia como:
n!=12(n2)(n1)n.

Veamos un ejemplo con 3 elementos.
Consideramos el caso de un paquete con 3 cartas con las letras impresas a,b,c,
y extraemos al azar una carta, luego otra, y así hasta terminar.
Claramente, en una extracción como la descripta, cada carta se extrae una vez como máximo.
El conjunto de cartas sería: X={a,b,c}.
Según el razonamiento anterior, el número total de formas en que se pueden listar esos 3 elementos es:
3!=321=6.

Ilustrémoslo mostrando todas las listas ordenadas que pueden obtenerse con esos 3 elementos:
(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a).

En efecto, son 6, como habíamos calculado.
A cada una de las ordenaciones que se le puede dar a un conjunto se llama: permutación.
Se puede formar el conjunto de todas las permutaciones. En nuestro ejemplo sería este:
Perm({a,b,c})={(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)}.

La cantidad total de permutaciones posibles es el cardinal del conjunto de permutaciones.
Para conjuntos de n elementos se denota a la cantidad de posibles permutaciones como:
Pn
Y lo que hemos concluido antes es que:
Pn=n!
Casos triviales y primeros valores del factorial:
0!=1.
1!=1.
2!=2.
3!=6
4!=24
5!=120
6!=720

6. Variaciones: conteo de listas ordenadas sin repeticiones y de una longitud dada.
Si tenemos un conjunto de n elementos, digamos X={a1,a2,,an}.
¿Cuántas listas ordenadas de longitud k pueden obtenerse, y sin repetir elementos?
En este caso, podemos imaginar de nuevo que tenemos n cartas distintas,
y que extraemos en orden una tras otra, hasta completar una lista de k elementos.
Para que la cuestión tenga sentido, asumamos que kn.
De nuevo hacemos la representación mediante casilleros en blanco, que vamos rellenando en forma sucesiva.
Imaginemos esta vez una fila de k casilleros en blanco.
En el primer casillero podemos elegir cualquiera de entre las n posibilidades del conjunto.
En el segundo casillero ya no podemos volver a elegir la opción que hemos colocado en el primer casillero,
pero aún así nos quedan todavía n1 elementos posibles que podemos elegir para colocar allí.
Una vez elegido ese elemento, en el tercer casillero podemos elegir entre los n2 elementos restantes,
y así sucesivamente hasta completar los k casilleros.
El cómputo de todas las elecciones posibles de listas ordenadas de n elementos, tomadas con longitud k,
se denota como Vkn, y se calcula como:
n(n1)(n2)(nk+1).

Si observamos detenidamente, veremos que en ese producto hay exactamente k factores.
Ese producto de k números consecutivos comenzando desde n y yendo hacia atrás,
también se lo suele denotar mediante: (n)k.
Por lo tanto, escribimos estas expresiones:
Vkn=(n)k=n(n1)(n2)(nk+1).

Por ejemplo, consideremos el caso de una lista de 4 letras, y todas las posibles cadenas de caracteres de longitud 3 que pueden generarse a partir de ellas:
X={A,B,C,D}.
Según nuestro cómputo, la respuesta al problema sería:
V24=(4)3=432=24.
Pero esta vez, y sólo a modo ilustrativo, mostremos que en efecto son 24 todas las posibilidades:
ABC ABD ACB ACD ADB ADC
BAC BAD BCA BCD BDA BDC
CAB CAD CBA CBD CDA CDB
DAB DAC DBA DBC DCA DCB
Una forma alternativa de expresar el cálculo de variaciones proviene de observar la siguiente igualdad de factoriales:
n!(nk)!=n(n1)(n2)(nk+1)(nk)321(nk)321=n(n1)(n2)(nk+1).

Por lo tanto:
Vkn=n!(nk)!.


7. Partes: conteo de todos los subconjuntos posibles de un conjunto dado.
Supongamos que un conjunto tiene n elementos: X={a1,a2,,an}.
Nos preguntamos cuántos subconjuntos pueden formarse a partir de X,
es decir, conjuntos que contengan algunos de los elementos de X, o todos, o ninguno.
Por ejemplo, tenemos un conjunto de 4 personas: X={Ana,Beto,Carlos,Diana},
y queremos agruparlos de distintas formas, para ver qué foto sale mejor.
En la foto pueden aparecer las siguientes personas:
  1. Ninguno de ellos.
  2. Sale sólo Ana.
  3. Sale sólo Beto.
  4. Sale sólo Carlos.
  5. Sale sólo Diana.
  6. Salen Ana y Beto.
  7. Salen Ana y Carlos.
  8. Salen Ana y Diana.
  9. Salen Beto y Carlos.
  10. Salen Beto y Diana.
  11. Salen Carlos y Diana.
  12. Salen Ana, Beto y Carlos.
  13. Salen Ana, Beto y Diana.
  14. Salen Ana, Carlos y Diana.
  15. Salen Beto, Carlos y Diana.
  16. Salen todos en la foto.
Como vemos, hay en total 16 posibilidades distintas (estamos suponiendo que sólo importa quién sale en la foto, y que no interesa el orden en que aparecen en dicha foto).
Curiosamente, este número es 16=24, y oh casualidad, el exponente 4 es el número de personas del conjunto X.
¿Hay alguna manera de justificar este resultado?
Podemos reformular el problema de la siguiente manera:
Imaginemos un casillero con 4 posiciones, cada una representando una de las 4 personas.
Dado un subconjunto W de X, habrá personas que pertenecen a él, y otras que no pertenecen.
En cada una de esas 4 posiciones ponemos un "switch" (o llave como la que prende la luz),
que marca "encendido" si la persona en esa posición está en el conjunto W,
y que marca "apagado" si la persona en esa posición no está en el conjunto W.
De esta manera, estamos haciendo corresponder cada subconjunto W de X
con una determinada configuración de "switches" que están encendidos y/o apagados.
Como sólo hay 2 posiciones para el switch (encendido o apagado),
y pueden repetirse en las 4 posiciones,
tenemos un total de 24 posibilidades.
Este modelo puede usarse para un conjunto X de n elementos,
y la conclusión será que hay 2n subconjuntos posibles de X.
La colección de todos los subconjuntos de un conjunto X también es un conjunto,
y se lo denota mediante P(X).
Más aún, como hemos visto en los párrafos precedentes, su cardinal es:
#(P(X))=2#(X).

Ejemplo: Sea X={A,B,C,D}. Tenemos:
P(X)={,{A},{B},{C},{D},{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},
{A,B,C},{A,B,D},{A,C,D},{B,C,D},{A,B,C,D}}.
El símbolo denota el conjunto vacío.
Notemos que, a la hora de contar subconjuntos, no interesa el orden de los elementos, sino sólo qué elementos conforman el subconjunto en cuestión. Por ejemplo, hemos escrito {A;B}, pero no hemos escrito {B,A}, porque en realidad ambos son el mismo subconjunto.

8. Combinaciones: conteo de las maneras de obtener conjuntos de un cardinal dado.
Dado un conjunto de n elementos: X={a1,a2,,an},
queremos ahora contar cuántos subconjuntos W de X se pueden formar con un cardinal determinado k.
Para que la cuestión tenga sentido, supongamos que kn.
Esta cuestión es diferente a la del apartado anterior, en donde habíamos calculado todos los subconjuntos posibles de un conjunto de n elementos. Más aún, para contar todos los casos posibles realizaremos también un análisis diferente.
Consideremos un conjunto de 5 elementos: X={1,2,3,4,5}.
Consideremos un subconjunto de 3 elementos, digamos: W={2,4,5}.
Cada conjunto de 3 elementos, tal como W, puede asociarse a una lista de 3! maneras distintas en que esos elementos pueden ordenarse.
Pero nosotros no estamos interesados en las variaciones de 5 elementos tomadas con longitud 3,
pues ahora no damos relevancia al orden en que aparecen los elementos.
Entonces, para obtener el total de subconjuntos de longitud 3,
podemos contar todas las variaciones de longitud 3 y dividir por 3!.
Esto nos da un total de: 5!(53)!/3!=10.
Comprobemos que en este caso efectivamente es así.
Todos los subconjuntos de cardinal 3 del conjunto X (que tenía 5 elementos), son:
{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}.

Efectivamente son 10 subconjuntos de cardinal 3, y se ve que no hemos olvidado ningún caso, ni repetido nada indebidamente.
Dados dos números n y k, y un conjunto X de n elementos,
a cada subconjunto de X de cardinal k se le llama una combinación (de tamaño k).
El cardinal del conjunto de todas las combinaciones posibles de tamaño k,
es decir, de todos los subconjuntos de X de cardinal k,
se le llama número combinatorio n sobre k.
Se le denota y calcula, en general, de la siguiente manera:
Ckn=(nk)=(n)kk!=n!(nk)!k!.


La notación (nk) recibe el nombre de coeficiente binomial.
Es un factor que aparece en la fórmula de Newton para calcular potencias de binomios.

Mencionemos algunos casos extremos o curiosos de los números combinatorios:
(nk)=n!(nk)!k!=n!k!(nk)!=(nnk).


(n0)=1.
(nn)=1.

Esas expresiones tienen sentido práctico.
Por ejemplo: ¿cuántos subconjuntos pueden formarse con 0 elementos? Respuesta: sólo 1, el conjunto vacío.
¿Y cuántos subconjuntos pueden formarse con n elementos, si el conjunto total tiene también n elementos? Respuesta: sólo 1, el conjunto total.


9. Modelo de bosones.

Supongamos que debemos colocar n elementos indistinguibles (digamos, n bolitas) en k cajas.
En este caso, podemos considerar tanto que n>k, n<k o n=k.
Deseamos averiguar de cuántas maneras podemos colocar las n bolitas en las k cajas.
Para resolver el problema, la estategia que se puede utilizar es la de considerar que se ponen en una fila los n+k elementos, es decir, tanto las bolitas como las cajas, y de tal manera que el último elemento es una caja.
La convención que tomamos ahora es que en cada caja se colocan las bolitas que están inmediatamente a su izquierda.

Por ejemplo, con 5 bolitas y 3 cajas, una configuración posible sería esta:

o _ o o _ o o _

Otra posibilidad:

o o o _ _ o _

Aquí "o" denota una bolita y "_" denota una caja.

Como puede observarse, dado que en la última posición siempre ponemos una caja,
el problema se reduce ahora a calcular de cuántas maneras pueden elegirse las n+k1 posiciones restantes a fin de colocar allí las k1 cajas que aún resta acomodar.
Este número ya sabemos calcularlo: es el combinatorio

(n+k1k1).


En nuestro ejemplo de n=5 bolitas y k=3 cajas, la respuesta sería que:
"La cantidad de maneras en que pueden repartirse 5 bolitas indistinguibles en 3 cajas es (5+3131)=(72)=21".

Y sólo por esta vez enumeraremos todas las posibilidades, para ilustrar el tema (observar que son efectivamente 21 casos):

  1. o o o o o _ _ _
  2. o o o o _ o _ _
  3. o o o o _ _ o _
  4. o o o _ o o _ _
  5. o o o _ o _ o _
  6. o o o _ _ o o _
  7. o o _ o o o _ _
  8. o o _ o o _ o _
  9. o o _ o _ o o _
  10. o o _ _ o o o _
  11. o _ o o o o _ _
  12. o _ o o o _ o _
  13. o _ o o _ o o _
  14. o _ o _ o o o _
  15. o _ _ o o o o _
  16. _ o o o o o _ _
  17. _ o o o o _ o _
  18. _ o o o _ o o _
  19. _ o o _ o o o _
  20. _ o _ o o o o _
  21. _ _ o o o o o _

10. Anagramas

Supongamos que tenemos una palabra formada con ciertas letras, tales que algunas se repiten.
Cada palabra que puede formarse con esas letras es un anagrama.
Nos preguntamos cuántos anagramas distintos podemos formar.
Antes de responder esto, debemos ser precisos con el enunciado mismo del problema.
Consideremos por ejemplo la palabra AMASAS.
Vemos que consta de 3 letras distintas (A, M, S),
y que la letra A se repite 3 veces, la S se repite 2 veces, y la M, se repite sólo 1 vez.
Con este ejemplo particular, ¿cuántos anagramas posibles distintos pueden obtenerse en total?
Son 60 total, y sólo por esta vez los enumeraremos a todos para ejemplificar:
AAASSM AAASMS AAAMSS AAMASS AMAASS MAAASS
AASASM AASAMS AASMAS AASMAS AMASAS MAASAS
ASAASM ASAAMS ASAMAS ASMAAS AMSAAS MASAAS
SAAASM SAAAMS SAAMAS SAMAAS SMAAAS MSAAAS
AASSAM AASSMA AASMSA AAMSSA AMASSA MAASSA
ASASAM ASASMA ASAMSA ASMASA AMSASA MASASA
SAASAM SAASMA SAAMSA SAMASA SMAASA MSAASA
ASSAAM ASSAMA ASSMAA ASMSAA AMSSAA MASSAA
SASAAM SASAMA SASMAA SAMSAA SMASAA MSASAA
SSAAAM SSAAMA SSAMAA SSMAAA SMSAAA MSSAAA
¿Cómo se razona para calcular que son 60 casos en total?
Observemos que las letras repetidas son indistinguibles,
por lo tanto lo relevante es ver sólo qué posiciones ocupan.
En el caso de la letra A, que se repite 3 veces,
el problema de contar en cuántas posiciones se pueden colocar A's en una palabra de longitud 6,
es equivalente a preguntar cuántos conjuntos de 3 elementos del conjunto de posiciones {1,2,3,4,5,6} es posible elegir.
Esto es el número combinatorio (63).
Una vez elegidas las ubicaciones de la letra A,
de entre las 3 posiciones restantes, vemos cuántas formas posibles hay de elegir 2 de ellos para ubicar las letras S.
Esto da el combinatorio (32).
Luego, de entre las 1 posiciones restantes, vemos de cuántas formas es posible elegir 1 de ellas para ubicar la única letra M.
Esto da el combinatorio (11).
Y ahí ya se nos acabaron las letras.
El resultado final será el producto de todas las posibilidades analizadas para cada letra, que nos da:

(63)(32)(11)=6!(63)!3!3!(32)!2!1!(11)!1!=6!3!2!1!=60.


Este razonamiento puede generalizarse (aquí no lo haremos), para dar la respuesta en el caso general:
Si tenemos k letras distintas {a1,a2,,ak},
y la letra a1 se repite n1 veces, la letra a2 se repite n2 veces, etcétera,
hasta la letra ak que se repite nk veces,
entonces la cantidad total de posiciones de cualquier anagrama formado con esas letras es N=n1+n2++nk,
y la cantidad total de anagramas posibles que se pueden generar con esas letras es igual a:

#(anagramas(a1,a2,,an))=N!n1!n2!nk!.


Dicho en palabras: el número total de anagramas se calcula como el factorial de la longitud de cada anagrama (que es fija), dividido por el producto de los factoriales del número de repeticiones de cada letra.

No hay comentarios:

Publicar un comentario