• Author / Uploaded
• Arturo Mickey Mousse

Citation preview

Combinatoria | Arturo Flores Aguilar

Objetivo: En este capítulo se aprenden los conceptos básicos de la combinatoria elemental como son las ordenaciones, permutaciones y las combinaciones. Además se da una breve introducción a la lectura e interpretación de ciertas fórmulas matemáticas de interés practico por ejemplo el concepto de factorial de un número y el coeficiente binomial.

1.1

Principios elementales de conteo: Principio del producto y de la suma

Comenzamos con algunos problemas introductorios a este principio, típico en muchos cursos de combinatoria.

Problema 1 Félix tiene 4 playeras distintas. Quiere elegir dos playeras para llevar de viaje. ¿De cuantas maneras puede hacerlo? Solución: Supongamos que las playeras están diferenciadas por colores, es decir 𝑃𝒍𝒂𝒚𝒆𝒓𝒂𝒔 = {𝑨𝒛𝒖𝒍, 𝑽𝒆𝒓𝒅𝒆, 𝑩𝒍𝒂𝒏𝒄𝒐, 𝑹𝒐𝒋𝒐}, Algunas posibles elecciones serian: Azul y Verde, Azul y Blanco, Azul y Rojo. De hecho todas las elecciones se pueden representar por medio de un diagrama de árbol como el que se muestra a continuación.

1

Combinatoria | Arturo Flores Aguilar

Verde Azul

Blanco Rojo Azul

Verde

Blanco Rojo

Elecciones de dos playeras

Azul Blanco

Verde Rojo Azul

Rojo

Verde Blanco

Como sabes el número de formas en las que se pueden elegir las dos playeras se obtiene al contar las ramas finales de nuestro diagrama de árbol, en este caso son 12… De esas doce elecciones observa que la elección Azul y Verde es la misma que Verde y azul; Verde y Blanco es la misma que Blanco y Verde…etc., esto quiere decir que cada una de las 12 elecciones se está contando dos veces. Por lo tanto el número de formas en las que se pueden elegir las playeras es

12 2

= 6 𝑓𝑜𝑟𝑚𝑎𝑠.

2

Combinatoria | Arturo Flores Aguilar Problema 2: En ciertas transmisiones de tipo telegráfico se dispone de dos sonidos, uno corto llamado punto (•) y uno largo llamado raya (—). Con estos podemos formar señales de un solo sonido, de dos sonidos, de tres sonidos, etc. ¿Cuántas señales de tres sonidos se pueden formar? Solución Podemos proceder usando un diagrama de árbol, pero en este caso daremos una segunda forma posible de resolver el problema Primero formaremos señales de dos sonidos y para ello usaremos la siguiente tabla. •

—

•

•

—

— •

•

•

—

— —

El siguiente paso es tomar las señales de dos sonidos para formar los de 3. • • —

•

• • • — • •

•

—

• • — — • —

— • • — • — —•

— — • — — — ——

Luego entonces las señales de tres sonidos que podemos formar con los símbolos • y — son 8. Problema 3: En el ejemplo anterior supongamos que hay 3 sonidos •, — y ▲. ¿Cuántas señales de 4 sonidos se pueden formar? Solución: 81 señales En el problema anterior es muy complicado elaborar tablas que nos permitan encontrar todas las posibles señales que se pueden formar. Sin en cambio el siguiente principio permite resolver de manera muy sencilla este problema, se conoce como principio del producto y es pieza clave para lo que resta del libro.

3

Combinatoria | Arturo Flores Aguilar

1.1.1 Principio del Producto Si una cierta acción (tarea) puede realizarse de M maneras diferentes y, para cada una de esas acciones, una segunda tarea puede realizarse de N maneras distintas, entonces las dos tareas JUNTAS pueden realizarse (en ese orden) de 𝐌 ∙ 𝐍 formas diferentes. Observación: El uso de este principio radica en que solo es aplicable en situaciones que ocurren al mismo tiempo, es decir, de manera simultánea. Ejemplo 1 En una Kermes hay pastel, gelatina y soda. Hay 8 sabores de pastel, 12 de gelatina y 6 sabores de soda. Si te dicen “elige un sabor de pastel, uno de gelatina y uno de soda ¿de cuantas maneras puedes elegir esta combinación de postres? Solución: Para aplicar el principio del producto consideramos tres casillas, cada casilla representa un postre: __________ _________ __________ En la primera casilla podemos colocar el pastel, en la segunda la gelatina y en la restante la soda; podemos ver entonces que el pastel se puede elegir de 8 maneras diferentes, la gelatina de 12 de maneras diferentes y la soda de 6, este proceso se está realizando al mismo tiempo, entonces por el principio del producto el número de combinaciones que podemos realizar es 8 ∙ 12 ∙ 6 = 576. Ejemplo 2 Considérense los números del 0 al 9 y el alfabeto usual de 27 letras. Una placa de auto consta de números y letras, si queremos formar placas con 3 números a la izquierda y 4 letras a la derecha. ¿Cuántas placas podemos formar? Solución: Consideremos 7 casillas __ __ __ __ __ __ __, las tres primeras son para los números y las últimas cuatro son para las letras. Siguiendo el principio del producto hay 10 • 10 • 10 • 27 • 27 • 27 • 27 = 103 • 274 = 531,441,000 Placas.

4

Combinatoria | Arturo Flores Aguilar Ejemplo 3 Para guardar un regalo se dispone de una caja que puede ser chica, mediana o grande. Si elegimos la caja chica entonces podemos escoger la envoltura de 5 colores diferentes; si se elige la mediana, la envoltura puede ser de tres colores distintos y si se elige la grande, de 6. Si, independientemente del tamaño la caja puede llevar o no un moño (que puede ser de 7 colores distintos), ¿de cuantas maneras diferentes podemos armar el regalo? Solución: Conviene separar el problema en casos: Primero supongamos que la caja no lleva moño: Si la caja no lleva moño, entonces el número de formas en las cuales podemos armar el regalo es de 5 + 3 + 6 = 14 𝑓𝑜𝑟𝑚𝑎𝑠 𝑑𝑖𝑠𝑡𝑖𝑛𝑡𝑎𝑠. Si la caja lleva moño entonces en número de formas en las cuales podemos armar el regalo quedarían como sigue 

Si elegimos la caja chica y además incluimos moño, entonces el número de formas de decorar el regalo es de 5 ∙ 7 = 35 𝑓𝑜𝑟𝑚𝑎𝑠.



Si elegimos la caja mediana y además se incluye moño, entonces el número de formas en que se puede decorar el regalo es de 3 ∙ 7 = 21 𝑓𝑜𝑟𝑚𝑎𝑠 𝑑𝑖𝑠𝑡𝑖𝑛𝑡𝑎𝑠.



Análogamente si la caja escogida es la grande e incluimos moño, entonces el número de formas en las que se puede decorar el regalo es de 6 ∙ 7 = 42 𝑓𝑜𝑟𝑚𝑎𝑠.

Por lo tanto el número de formas en las cuales se puede decorar el regalo suponiendo que la caja lleva moño es de 35 + 21 + 42 = 98 𝑓𝑜𝑟𝑚𝑎𝑠 𝑑𝑖𝑠𝑡𝑖𝑛𝑡𝑎𝑠. Finalmente el resultado total es la suma de los dos casos anteriores, es decir, el regalo se puede decorar de 14 + 98 = 112 𝑓𝑜𝑟𝑚𝑎𝑠 𝑑𝑖𝑠𝑡𝑖𝑛𝑡𝑎𝑠.

El razonamiento usado para resolver el problema anterior sugiere que cuando un problema se separa en casos el resultado final o la solución total del problema es la suma de los resultados de cada uno de los casos, esté razonamiento podemos resumirlo en lo que se conoce como principio de la suma.

5

Combinatoria | Arturo Flores Aguilar

1.1.2 Principio de la Suma Si una cierta tarea puede realizarse de M formas distintas y a su vez otra tarea se realiza de N formas diferentes pero ambas tareas son independientes, es decir, no se realizan simultáneamente, entonces las posibles formas de realizar alguna de ambas tareas se puede hacer de 𝐌 + 𝐍 𝐟𝐨𝐫𝐦𝐚𝐬 𝐝𝐢𝐟𝐞𝐫𝐞𝐧𝐭𝐞𝐬.

Ejemplo 4 ¿Cuántos números enteros entre 1 y 110 hay tal que sean múltiplos de 5 ó de 11? Solución: Primero vamos a calcular los múltiplos de 5 que están entre el 1 y el 110; para ello notamos que en la tabla de multiplicar del 5 todos los números tienen como último dígito el 0 o el 5, los números 55 y 110 no se consideran en esta lista, pues son a su vez múltiplos de 11. Para formar a todos los múltiplos de 5 consideramos dos casillas (pues el número 110 es múltiplo de 5 y 11) y el 100 y 105 ya son múltiplos de 5 _____ _____ En la primera casilla pueden estar cualesquiera de los 9 dígitos, mientras que en la última solo está el 5 𝑜 𝑒𝑙 0; por el principio del producto hay 9 ∙ 2 = 18 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑜𝑠 𝑑𝑒 5 y agregando al 100, 105 y quitando al 55, vemos que hay en total 19 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑜𝑠 𝑑𝑒 5 𝑦 𝑛𝑜 𝑑𝑒 11. Calculemos ahora los múltiplos de 11, pero no de 5, es decir, él 55 y 110 serán eliminados de esta lista; esta lista es fácil porque los múltiplos de 11, del 1 al 110 son 11, 22, 33, 44, 66,77, 88 y 99. Por el principio de la suma los números enteros entre 1 y 110, múltiplos de 5 o de 11 son 19 + 8 = 27.

Ejercicios 1.2 Problema 1 Se tienen 6 sabores de helado. Julián quiere comprar un helado con dos bolas de helado, de modo que los sabores sean distintos ¿cuantas posibles combinaciones puede hacer? ¿Cuántas si el helado llevara 3 bolas de diferente sabor?

6

Combinatoria | Arturo Flores Aguilar Problema 2 Karina para vestirse tiene 8 blusas, 6 faldas y cuatro pantalones, para calzar tiene un par de botas, un par de tenis y uno de zapatos. ¿De cuantas formas distintas puede arreglarse? Problema 3 Las ciudades de Nápoles, Venecia, Roma y Florencia están unidas entre sí. A cada dos de ellas las unen 7 caminos diferentes. ¿De cuantas formas se puede ir de Venecia a Florencia sin pasar por dos de ellas? Problema 4 ¿Cuantos números hay del 1 al 100 que sean múltiplos de 2, pero no de 5? Problema 5 La palabra P A B L O se desbarata para generar palabras quizás sin sentido. ¿Cuántas palabras distintas se pueden formar con las letras de la palabra original? Problema 6 Luz ha comprado 12 colores diferentes de pintura para pintar las cuatro paredes de su cuarto y también el techo. a) ¿de cuantas formas puede pintar su habitación? b) Si Luz no quiere que dos paredes juntas queden con el mismo color ¿de cuentas formas puede quedar el decorado? c) Si Luz no quiere que dos paredes queden con el mismo color ¿de cuantas formas puede quedar el decorado?

Problema 7 Se disponen de 5 lienzos de colores (verde, Blanco, Rojo, Azul y Negro) de tela para formar banderas bicolores. a) ¿Cuántas banderas bicolores podemos formar si no disponemos de un asta? Ayuda: banderas como VERDE-BLANCO y BLANCO-VERDE se consideran iguales. b) Misma pregunta que en el ejercicio anterior, pero ahora la bandera llevara un asta.

7

Combinatoria | Arturo Flores Aguilar

1.3 Ordenaciones y Permutaciones Una variación interesante del principio de la multiplicación es el concepto de ordenación y permutación para ilustrar cada concepto vale la pena realizar la siguiente definición.

1.3.1 Factorial de un número Si 𝒏 es un número natural, el producto de todos los números naturales del 𝟏 𝒂 𝒏 se le llama el factorial de 𝒏 y se denota como 𝒏!. En símbolos

𝒏! = 𝒏 ∙ (𝒏 − 𝟏) ∙ (𝒏 − 𝟐) … 𝟑 ∙ 𝟐 ∙ 𝟏 Ejemplo 1: 2! = 2 ∙ 1 = 2

6! = 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 720

Además por comodidad definimos 0! = 1. Veamos una aplicación de esta definición: Ejemplo 2 ¿De cuantas formas se pueden sentar 6 personas en 6 sillas numeradas del 1 al 6? Solución: Consideremos 6 casillas, una por cada silla ___ ___ ___ ___ ___ ___, vemos que en la primera silla puede sentarse cualquiera de las seis personas, en la segunda silla puede sentarse cualquiera de las 5 personas restantes y así sucesivamente. Entonces por el principio del producto, el número de formas en las cuales se pueden sentar las 6 personas en las seis sillas es 6! = 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 720 𝑓𝑜𝑟𝑚𝑎𝑠 Ordenaciones de este estilo donde no hay repetición de objetos recibe el nombre de:

1.3.3 Permutación de n elementos Si tenemos una colección de 𝒏 elementos distintos y queremos ordenarlos en 𝒏 lugares enumerados desde 𝟏 𝒂 𝒏. Entonces el número de formas en que se puede realizar esta acción se le llama permutación y se designa con el símbolo 𝑷𝒏 , en símbolos:

𝑷𝒏 = 𝒏!

8

Combinatoria | Arturo Flores Aguilar Ejemplo 3 En una clase de matemáticas hay 6 hombres y 4 mujeres. Se les aplica un examen y con ello los alumnos son clasificados de acuerdo a su desempeño. Al analizar los resultados del examen se observa que los 10 estudiantes obtienen diferente puntuación. a) De manera general ¿Cuántas clasificaciones diferentes hay? b) Si los hombres se clasifican entre ellos y las mujeres se clasifican entre ellas. ¿cuantas clasificaciones posibles hay? Solución: a) Dado que hay 10 estudiantes y cada uno tiene una cierta calificación (diferente a la de los demás), entonces todas las posibles clasificaciones que puede haber son 𝑃10 = 10! b) Las clasificaciones posibles entre los hombres son 𝑃6 = 6! y las posibles clasificaciones entre las mujeres son 𝑃4 = 4!. Por lo tanto el número total de clasificaciones que puede haber (según el principio del producto) es de 6! ∙ 4!

Ejemplo 4 La señora Jones tiene 10 libros que pondrá en una estantería. De estos, 4 son de matemáticas, 3 de química, 2 de historia y 1 de inglés. La señora Jones quiere organizar sus libros para que todos los libros del mismo tema queden juntos en dicho estante. ¿Cuántos arreglos posibles hay? Solución Primero veamos de cuantas manera podemos organizar los libros del mismo tema sobre el estante, para ello supongamos que los libros de cada tema forman un solo libro (como si estuvieran pegados), por ejemplo 𝐐𝐔𝐌𝐈𝐂𝐀 − 𝐇𝐈𝐒𝐓𝐎𝐑𝐈𝐀 − 𝐈𝐍𝐆𝐋𝐄𝐒 − 𝐌𝐀𝐓𝐄𝐌Á𝐓𝐈𝐂𝐀𝐒. Entonces el número de formas en las que pueden ordenarse los libros del mismo tema sobre el estante es de 4! Ahora bien los 4 libros de matemáticas pueden ordenarse en su propio lugar de 4! 𝑓𝑜𝑟𝑚𝑎𝑠, mientras que los de química pueden ordenarse de 3! 𝑓𝑜𝑟𝑚𝑎𝑠, los de historia de 2! 𝑓𝑜𝑟𝑚𝑎𝑠 y el de inglés de 1! 𝑓𝑜𝑟𝑚𝑎𝑠.

9

Combinatoria | Arturo Flores Aguilar Observa que estos procesos ocurren al mismo instante, por lo tanto el número de formas en las que pueden organizarse los libros sobre el estante es de 4! (4! ∙ 3! ∙ 2! ∙ 1!) = 4! ∙ 4! ∙ 3! ∙ 2! ∙ 1!

Ejemplo 5 La palabra A N I T A se descompone para formar otras palabras por ejemplo 𝐴 𝑁 𝑇 𝐴 𝐼 o bien 𝑁 𝐼 𝑇 𝐴 𝐴. ¿Cuántas palabras podemos formar al descomponer la palabra dada? Solución: En este problema hay que tener cuidado ya que al ordenar las letras A podemos obtener la misma palabra por ejemplo 𝐴 𝑁 𝑇 𝑨 𝐼 𝑒𝑠 𝑙𝑜 𝑚𝑖𝑠𝑚𝑜 𝑞𝑢𝑒 𝑨 𝑁 𝑇 𝐴 𝐼 . Para eliminar ese tipo de palabras supongamos que todas las letras de la palabra A N I T A son diferentes, para ello etiquetemos a las A con los subíndices 𝐴1 𝑦 𝐴2 . Entonces hay 5 letras diferentes y el número de palabras diferentes que podemos formar es 5!. Ahora bien, considera el arreglo 𝐴1 𝑁 𝑇 𝐴2 𝐼, nota que 𝑃2 = 2! es el número de formas en las cuales se permutan las A sobre su propio lugar, esto muestra que la palabra 𝐴 𝑁 𝑇 𝐴 𝐼 se repite dos veces, es decir, de manera general cada palabra se repite dos veces. Por lo tanto el número de palabras diferentes que podemos formar es de: 5! 5𝑥4𝑥3𝑥2𝑥1 = = 60 2! 2𝑥1

Ejemplo 6 ¿Cuántas banderas tricolores (con asta bandera) se pueden formar si contamos con 7 lienzos de tela de distinto color? Solución Consideramos tres casillas ___ ___ ___, una para cada color, en la primera casilla puede estar cualquiera de los 7 lienzos de color, en la segunda cualquiera de los 6 restantes y en la última cualquiera de los 5 restantes, por el principio del producto, el total de banderas tricolores es 7 ∙ 6 ∙ 5 = 210

10

Combinatoria | Arturo Flores Aguilar El siguiente ejemplo es un poco más abstracto que los anteriores, en muchos cursos básicos puede omitirse y saltarse directamente a la definición 1.3.4.

Ejemplo 7 Se quieren acomodar en una fila con 𝑚 𝑙𝑢𝑔𝑎𝑟𝑒𝑠 un grupo de 𝑛 personas. Si 𝑛 ≥ 𝑚. ¿De cuantas formas se puede realizar esta ordenación? Solución Consideramos 𝑚 𝑐𝑎𝑠𝑖𝑙𝑙𝑎𝑠, cada una representando un lugar m lugares

____ ____ ____ … ____ En la primera casilla puede estar cualquiera de las 𝑛 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠, en la segunda casilla puede estar cualquiera de las 𝑛 − 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 𝑟𝑒𝑠𝑡𝑎𝑛𝑡𝑒𝑠 y así sucesivamente hasta que en la última casilla se puede colocar cualquiera de las 𝑛 − 𝑚 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 𝑟𝑒𝑠𝑡𝑎𝑛𝑡𝑒𝑠. Por el principio del producto el número de formas en las cuales podemos hacer esta ordenación es de: 𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2) ∙ (𝑛 − 3) ∙ (𝑛 − 4) ∙ … ∙ (𝑛 − 𝑚 + 1) La fórmula anterior recibe el nombre de Ordenaciones de 𝒏 elementos tomados de 𝒎 𝒆𝒏 𝒎 y se denota como 𝑶𝒏𝒎 . Una forma de escribir esta fórmula es la siguiente:

𝑶𝒏𝒎 = 𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2) ∙ (𝑛 − 3) ∙ (𝑛 − 4) ∙ … ∙ (𝑛 − 𝑚 + 1) =

𝑛 ∙ (𝑛 − 1) ∙ (𝑛 − 2) ∙ (𝑛 − 3) ∙ (𝑛 − 4) ∙ … ∙ (𝑛 − 𝑚 + 1) ∙ (𝑛 − 𝑚) ∙ (𝑛 − 𝑚 − 1) ∙ … ∙ 2 ∙ 1 (𝑛 − 𝑚)(𝑛 − 𝑚 − 1) ∙ … ∙ 2 ∙ 1

=

𝒏! (𝒏 − 𝒎)!

Resumiendo, tenemos la siguiente definición

11

Combinatoria | Arturo Flores Aguilar

1.3.4 Ordenaciones Si 𝒏 ≥ 𝒎, entonces el número de formas en las cuales se pueden ordenar 𝒏 𝒐𝒃𝒋𝒆𝒕𝒐𝒔 𝒆𝒏 𝒎 𝒄𝒂𝒔𝒊𝒍𝒍𝒂𝒔 se llama ordenaciones de 𝒏 elementos tomados de 𝒎 𝒆𝒏 𝒎 y viene dado por:

𝑶𝒏𝒎 =

𝒏! (𝒏 − 𝒎)!

Ejemplo 8 Se dispone de 7 lienzos de tela de distinto color {Verde, Blanco, Rojo, Azul, Negro, Café, Morado}. Queremos formar con ellas bandera tricolores. Si no disponemos de un asta bandera ¿cuantas banderas podemos formar? Solución Dado que no contamos con un asta bandera, entonces configuraciones como 𝑉𝐸𝑅𝐷𝐸 − 𝐵𝐿𝐴𝑁𝐶𝑂 − 𝑅𝑂𝐽𝑂 son exactamente iguales a la configuración 𝑅𝑂𝐽𝑂 − 𝐵𝐿𝐴𝑁𝐶𝑂 − 𝑉𝐸𝑅𝐷𝐸. El total de banderas tricolores que se pueden formar son 𝑂37 , dado que no hay un asta bandera, entonces cada arreglo se está repitiendo dos veces, entonces el total de banderas que se puede formar son

𝑂37 7 ∙ 6 ∙ 5 = = 105 2 2

Ejemplo 9 En una bolsa hay 4 pelotas rojas y 3 azules. Queremos formar una fila con todas ellas. ¿De cuantas maneras distintas puede quedar la fila? Solución Lo que haremos será un conteo indirecto, pensemos primero que las 7 pelotas en la bolsa son todas de distinto color y etiquetémoslas {𝑅1 , 𝑅2 , 𝑅3 , 𝑅4 , 𝐴1 , 𝐴2 , 𝐴3 }. Si las pelotas están etiquetadas de esa manera, entonces el número de filas de 4 lugares que podemos formar con ellas es de:

𝑂77 = 𝑃7 = 7!

12

Combinatoria | Arturo Flores Aguilar De esa cantidad total de filas escogemos una fila particular, por ejemplo: 𝑅2 , 𝐴3 , 𝐴1 , 𝑅4 , 𝑅1 , 𝑅3 , 𝐴2 Si en esa fila solamente las pelotas rojas se permutan, entonces el arreglo anterior se repite 4! 𝑣𝑒𝑐𝑒𝑠 y si las azules se permutan entre ellas, entonces el arreglo se repite 3! 𝑣𝑒𝑐𝑒𝑠. Dado que dicho proceso está ocurriendo al mismo tiempo, entonces, todo el arreglo se repite 4! ∙ 3! 𝑣𝑒𝑐𝑒𝑠 . Entonces el número de filas que se pueden formar con las 7 pelotas es: 7! = 35 4! ∙ 3!

Ejercicios 1.4 Problema 1 Obtén el resultado de las siguientes operaciones.

𝑎)

𝑃29 𝑃27

𝑏)

𝑃4 ∙ 𝑃12 𝑃16

𝑐) 𝑂3100

𝑑) 𝑂59 ∙ 𝑂24 ∙ 𝑂22

𝑒) 𝑂47 ∙ 𝑃3

Problema 2 Encuentra el valor de la siguiente operación. 2! + 3! + 4! + 5! =¿ ? Problema 3: Comprueba la validez de las siguientes expresiones. 𝑎) 𝑂47 ∙ 𝑃3 = 𝑃7

𝑏) 7! + 8! = 7! ∙ 9

∗ 𝑐) 1003! + 1004! + 1005! = 1003! ∙ 10052

Problema 4 Entre un grupo de 30 personas se debe elegir una mesa directiva que conste de un presidente, un secretario, un tesorero y un vocal. ¿De cuantas maneras puede realizarse la elección? Problema 5 ¿Cuántas placas de automóvil de 7 cifras distintas pueden formarse si la primera, la cuarta y la séptima deben ser cifras impares?

13

Combinatoria | Arturo Flores Aguilar Problema 6 Encuentra el número de formar en las que se pueden organizar en una estantería tres novelas, 2 libros de matemáticas y un libro de química si a) Los libros pueden ordenarse en cualquier orden. b) Los libros de novelas y los libros de matemáticas deben estar juntos. c) Los de novelas deben estar juntos y el resto en cualquier orden.

Problema 7 a) De un grupo de 5 estudiantes quiere elegirse una comisión de 3 para que las tres personas seleccionadas visiten un mismo de una lista de tres museos. ¿Cuántas comisiones se pueden formar? b) Misma pregunta que en el inciso anterior, solo que ahora cada miembro de la comisión visitara un mismo museo. Problema 8 ¿Cuántas palabras distintas podemos formar con la palabra C A N I C A? Problema 9 ¿Cuántas palabras podemos formar con la palabra M A T E M A T I C A? Problema 10 Se tienen 4 pelotas rojas, 2 verdes y 3 azules. Se quiere formar una fila de 4 pelotas con todas ellas. ¿De cuantas maneras se puede formar la fila? Problema 11 Encuentra el número de formas en las que pueden sentarse 8 personas en una fila de 8 sillas si a) Se pueden sentar en el orden que sea. b) Las personas A y B deben de quedar juntas. c) Hay 4 hombres y 4 mujeres, pero dos hombres o dos mujeres no pueden sentarse juntos. d) Hay 5 hombres y deben sentarse uno al lado de otro. e) Hay 4 parejas casadas y cada pareja debe sentarse junta.

14

Combinatoria | Arturo Flores Aguilar

Objetivo: En esta sección se presenta el tratamiento de problemas donde no importa el orden de los elementos estudiados, es decir, se estudia el concepto de combinación de 𝑛 elementos tomados de 𝑚 𝑒𝑛 𝑚. También se incluye una sección especial sobre ciertos problemas que resultan de una aplicación de todos los conceptos antes mostrados, tales como Juego de Póker, Domino, Caminos, etc. Comenzamos con algunos problemas introductorios

2.1 Combinaciones Problema 1 De un grupo de 10 niños y 15 niñas se quiere formar una colección de 5 personas. Halle el número de formar en las cuales se puede formar esta comisión si: a) La colección tiene exactamente 4 niñas b) La colección tiene a lo más 3 niñas Soluciones a) Primero vamos a escoger a las niñas, usando las ordenaciones vemos que, el total de formas en las que se pueden escoger a las niñas es de 𝑶𝟏𝟓 𝟒 , pero el arreglo 𝐴𝑁𝐴 − 𝑅𝑂𝑆𝐴 − 𝑃𝐸𝑅𝐿𝐴 − 𝑀Á𝑅𝐼𝐴 es igual a

15

Combinatoria | Arturo Flores Aguilar 𝑀Á𝑅𝐼𝐴 − 𝑃𝐸𝑅𝐿𝐴 − 𝑅𝑂𝑆𝐴 − 𝐴𝑁𝐴 , 𝑒𝑡𝑐, es decir, cada cuarteto de niñas se está contando 𝑃4 = 4!. Por lo tanto el número de formas en las cuales se puede escoger a las niñas es de: 𝑂415 15 ∙ 14 ∙ 13 ∙ 12 = = 1365 𝑃4 4! A continuación vamos a escoger a los niños lo cual es sencillo ya que solo hay 10 formas diferentes de hacerlo, por lo tanto, el total de formas en las cuales puede escogerse dicha comisión es de 𝑂415 = 1365 ∙ 10 = 13,650 𝑝4 b) El hecho de que la comisión tenga a lo más tres niñas abre la posibilidad a que haya 3 niñas, 2 niñas o ninguna. Realicemos el conteo por separado Caso 1: Que la comisión tenga tres niñas Usando un razonamiento similar, vemos que el número de formas en las cuales podemos escoger a las niñas es de 𝑂315 15 ∙ 14 ∙ 13 = = 455 3! 3∙2∙1 Mientras que los niños se pueden escoger de 𝑂210 10 ∙ 9 = = 45 2! 2 Por lo tanto el número de formas en las cuales puede escogerse dicha comisión, es de 455 ∙ 45 = 20,475 Caso 2: Que la comisión tenga dos niñas El número de formas en las que se puede escoger a las niñas es de 𝑂215 = 105 2! Mientras que los niños se pueden escoger de 𝑂310 = 120 3!

16

Combinatoria | Arturo Flores Aguilar Por tanto el total de formas en que se puede escoger dicha comisión, es de 120 ∙ 105 = 12,600 Caso 3: Que la comisión tenga exactamente una niña Las niñas se pueden escoger de 15 maneras diferentes, mientras que los niños se pueden escoger de 𝑂410 = 210 4! Por lo tanto la comisión se puede formar de 210 ∙ 15 = 3150 𝑓𝑜𝑟𝑚𝑎𝑠. Caso 4: Si la colección no tiene ninguna niña, entonces, los niños se puede escoger de 𝑂510 = 252 5! Por lo tanto, el total de formas en las cuales se puede escoger la comisión es la suma de los casos 20,475 + 12,600 + 3,150 + 252 = 36,477

En los ejemplos anteriores aprendimos el siguiente principio:

2.1.1 Combinaciones de 𝒏 elementos tomados de 𝒎 en 𝒎 El número de colecciones (en las que orden no importa) con 𝒎 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒐𝒔 que se pueden seleccionar dentro de un conjunto de 𝒏 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝒐𝒔 𝒄𝒐𝒏 𝟏 ≤ 𝒎 ≤ 𝒏 se le llama combinaciones y viene dada por

𝑪𝒏𝒎

𝒏 𝑶𝒏𝒎 𝒏! =( )= = 𝒎 𝒎! 𝒎! (𝒏 − 𝒎)!

Ejemplo 1 Un grupo de 15 personas quiere dividirse en 3 equipos de 5 personas cada uno. Cada equipo tendrá cierta labor diferente a la de los demás. ¿De cuantas formas distintas es posible realizar la distribución? Solución: Vamos a escoger a los equipos de uno en uno:

17

Combinatoria | Arturo Flores Aguilar El primer equipo resulta de obtener las combinaciones de 15 en 5, por lo tanto el número de formas en las que se puede escoger este equipo es de:

𝐶515 =

𝑂515 15 ∙ 14 ∙ 13 ∙ 12 ∙ 11 = = 3003 5! 5!

Ahora bien, una vez elegido este equipo solo hay 10 personas disponibles y por lo tanto el segundo equipo puede elegirse de:

𝐶510

𝑂510 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = = = 252 5! 5!

El tercer equipo solo puede escogerse de 1 sola forma. Finalmente el número de formas en las que se puede realizar la distribución según el principio del producto es de 3003 ∙ 252 ∙ 1 = 756,756

Ejemplo 2 Considera un conjunto de 100 antenas de las cuales se sabe que 40 no funcionan. Supongamos que las antenas defectuosas y las funcionales son indistinguibles. Si las ordenamos en una fila ¿Cuántos ordenamientos hay tales que no hay dos antenas consecutivas defectuosas?

Solución: En total sabemos que hay 100 − 40 = 60 antenas funcionales, entonces si ordenamos en una fila las 60 antenas funcionales tendremos que entre cada una a lo más hay una antena defectuosa, es decir, si pensamos como F a las antenas funcionales y N al espacio donde van las no funcionales, entonces los arreglos pedidos tendrían la siguiente forma 𝐹 𝑁 𝐹 𝑁 𝐹…𝐹 𝑁 𝐹 Ahora bien en total hay 60 − 1 = 59 espacios para colocar las antenas que no sirven. Entonces el problema se reduce a encontrar solamente el total de formas en cómo podemos acomodar las 40 antenas no funcionales en los 59 espacios, dado que las antenas son indistinguibles entonces ese número de formas viene dado por 59 𝐶40 =

59 𝑂40 40!

18

Combinatoria | Arturo Flores Aguilar Ejemplo 3 De un grupo de 30 personas debe “elegirse” un comité de 6 miembros. Pero por ciertas razones, en él debe figurar forzosamente Pablo y Víctor o solo Juan, pero no los tres, pues se “vería mal”. ¿Cuantos comités pueden resultar electos? Solución El problema se dividirá en casos Caso 1: El comité cuenta con Pablo y Víctor Si el comité solo contara con Pablo y Víctor, entonces hay 28 personas disponibles para elegir los 4 miembros restantes, pero como Juan no estará en este comité, entonces el número de personas se reduce a 27. Así el número de formas en las cuales podemos formar este comité es

𝐶427 Caso 2: El comité solo cuenta con Juan Si el comité cuenta con Juan, entonces hay 29 personas restantes para elegir las 5 que hacen falta, pero en este comité no estará Pablo ni Víctor, por lo tanto solo hay 27 personas para elegir, estas personas se puede elegir de

𝐶527 Por lo tanto el número de comités que se pueden formar son:

𝐶427 + 𝐶527

Ejemplo 4 Comprobar la siguiente igualdad conocida como identidad de pascal

𝑛+1 𝑛 𝑛 ( )=( )+( ) 𝑚+1 𝑚 𝑚+1 Solución 1 Observa que la igualdad equivale a demostrar

19

Combinatoria | Arturo Flores Aguilar

𝑛 𝑛+1 𝑛 ( )=( )−( ) 𝑚 𝑚+1 𝑚+1 Comenzando del lado derecho, tenemos que

(

( 𝑛 + 1) ! 𝑛+1 𝑛 𝑛! )−( )= − (𝑚 + 1)! (𝑛 − 𝑚)! (𝑚 + 1)! (𝑛 − 𝑚 − 1)! 𝑚+1 𝑚+1 =

(𝑛 + 1)𝑛! 𝑛! (𝑛 − 𝑚) − (𝑚 + 1)𝑚! (𝑛 − 𝑚)! (𝑚 + 1)𝑚! (𝑛 − 𝑚)(𝑛 − 𝑚 − 1)! =

𝑛! ((𝑛 + 1) − (𝑛 − 𝑚)) 𝑛! (𝑚 + 1) = (𝑚 + 1)𝑚! (𝑛 − 𝑚)! (𝑚 + 1)𝑚! (𝑛 − 𝑚)! =

𝑛! 𝑛 =( ) 𝑚! (𝑛 − 𝑚)! 𝑚

Solución 2 Para demostrar la igualdad

𝑛+1 𝑛 𝑛 ( )=( )+( ) 𝑚+1 𝑚 𝑚+1 Consideremos un conjunto de 𝑛 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠. El número de grupos de 𝑚 + 1 personas que podemos formar a partir del conjunto original se puede formar como sigue (recordar el ejemplo anterior): Una vez fijada una persona (digamos Juan), entonces hay 𝑛 personas disponibles para seleccionar a las otras 𝑚 restantes, este selección puede hacerse de 𝑛 ( ) 𝑚 Hay otro caso más, que consiste en formar un grupo de 𝑚 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠, que no contenga a Juan, entonces hay 𝑛 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 disponibles para seleccionar a las 𝑚 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 que forman parte del grupo. Dicho número de formas viene dado por 𝑛 ( ) 𝑚+1 Con lo anterior el número de grupos de 𝑚 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠, que podemos formar a partir de un grupo de 𝑛 + 1 𝑝𝑒𝑟𝑠𝑜𝑛𝑎𝑠 𝑒𝑠:

20

Combinatoria | Arturo Flores Aguilar

(

𝑛+1 𝑛 𝑛 ) = ( )+( )∎ 𝑚+1 𝑚 𝑚+1

Ejemplo 5 Hallar el número de diagonales que pueden trazarse en un polígono regular y convexo de 𝑛 𝑙𝑎𝑑𝑜𝑠. Solución Las diagonales de algunos polígonos se muestran trazadas a continuación

Observa que para formar diagonales, lo único que tenemos que hacer es unir dos vértices, entonces los grupos de 2 vértices tomados de un conjunto de 𝑛 𝑣𝑒𝑟𝑡𝑖𝑐𝑒𝑠 EXPRESAN tanto diagonales como lados; el número total de esos grupos es: 𝑛 ( ) 2

Para obtener solo diagonales, lo único que haremos es eliminar los lados, es decir, el total de diagonales que podemos trazar en un polígono es: 𝑛 𝑛! 𝑛 ∙ (𝑛 − 1)(𝑛 − 2)! 𝑛(𝑛 − 1) ( )−𝑛 = −𝑛 = −𝑛 = −𝑛 2 2! (𝑛 − 2)! 2! (𝑛 − 2)! 2

21

Combinatoria | Arturo Flores Aguilar

2.2 Problemas Dinámicos En esta sección presentamos problemas de diversa naturaleza cuya solución requiere de temas antes visto o simplemente alguna estrategia ingeniosa.

2.2.1 Caminos En esta sección analizamos problemas referentes a contar caminos en figuras siguiendo líneas y uniendo puntos. Problema 1: Consideremos una cuadricula de 6 𝑥 8 , sea A el vértice inferior izquierdo y B el vértice superior derecho. ¿Cuántos caminos hay de A hacia B siguiendo las líneas de la cuadricula si solo podemos avanzar hacia la derecha y hacia arriba? Solución La cuadricula se muestra a continuación y también algún camino marcado.

Observa que cualquier camino de A hacia B recorre exactamente 6 + 8 = 14 segmentos, de los cuales 6 son horizontales y 8 verticales. Usando esto designemos por D a los segmentos recorridos en dirección derecha y con A a los segmentos recorridos en dirección vertical, entonces seleccionemos un camino

22

Combinatoria | Arturo Flores Aguilar cualquiera, por ejemplo él de la figura mostrada. Observa que este camino puede representarse por la palabra: 𝐷𝐴𝐴𝐷𝐴𝐷𝐷𝐴𝐴𝐴𝐷𝐴𝐴𝐷 Dado que siempre hay 6 letras D y 8 letras A, entonces el problema anterior se reduce a encontrar el número de palabras diferentes que podemos formar con esas letras (Recuerda el ejemplo 5 del tema de permutaciones). Siguiendo un razonamiento similar al ejemplo 5 del tema de permutaciones, tenemos que el número de palabras que podemos formar si todas las letras fueran distintas es 14! ; pero observa que las letras D pueden permutarse de 6! 𝑓𝑜𝑟𝑚𝑎𝑠, mientras que las A se permutan de 8! formas, es decir, cada palabra se repite 6! ∙ 8! 𝑣𝑒𝑐𝑒𝑠. Por lo tanto el total de caminos de A hacia B es: 14! 14 14 = ( ) = ( ) = 3003 6! ∙ 8! 6 8 Ejemplo 2 En la siguiente figura, para llegar del punto M al punto N solo se pueden recorrer caminos en la dirección que indican las flechas. ¿Cuántos caminos distintos se pueden encontrar?

Solución: Observemos que solo hay dos maneras de llegar a cada vértice que forma parte de la frontera superior de la cuadricula anterior, (excepto para el vértice superior izquierdo para este solo hay una forma de llegar siguiendo las flechas). Las formas de llegar son: horizontalmente desde el vértice localizado a la izquierda de él y en diagonal desde el vértice opuesto a él. Para la frontera inferior, para llegar a cada vértice también hay dos maneras de llegar: horizontalmente desde el vértice localizado a la izquierda y verticalmente desde el vértice justo arriba de él. Entonces el número de caminos para llegar desde M a cada vértice superior se encuentra sumando las direcciones horizontales y diagonales del vértice adyacente y opuesto respectivamente. De manera análoga para encontrar el total de caminos que van desde M a cada vértice inferior de la frontera hay

23

Combinatoria | Arturo Flores Aguilar que sumar las direcciones horizontales y verticales del vértice adyacente y el que está justo arriba de él respectivamente. La siguiente figura muestra el número de camino escrito en cada vértice.

Por lo tanto hay 987 caminos desde M a N.

24

Combinatoria | Arturo Flores Aguilar

2.2.2 Baraja de Póker Los siguientes ejemplos se refieren a la baraja usual de póker: Cada carta tiene un símbolo llamado número que puede ser cualquiera de los 13 símbolos siguientes

𝑁ú𝑚𝑒𝑟𝑜 = {𝐴, 2, 3, 4, 5, 6, 7, 8, 9, 10, 𝐽, 𝑄, 𝐾 } También contiene otro símbolo llamado palo que puede ser cualquiera de los cuatro siguientes

𝑃𝑎𝑙𝑜 = {♠, ♡, ♦, ♣} Todos los palos se combinan con todos los números para formar la baraja completa con 13 ∙ 52 𝑐𝑎𝑟𝑡𝑎𝑠

Nomenclatura usual: PAR: Dos cartas del mismo número. TERCIA: Tres cartas del mismo número. PÓKAR: Cuatro cartas del mismo número.

25

Combinatoria | Arturo Flores Aguilar FULL: Una tercia y un par. FLOR: Cinco cartas del mismo palo. CORRIDA o ESCALERA: Cinco cartas con numeración consecutiva según el orden de los números, pero permitiendo al número A como número final siempre y cuando este después de K.

Ejemplo 1: Una mano de póker consta de 5 cartas. ¿Cuántas manos de póker tienen tercia exactamente? Observa que en el arreglo tampoco debe haber pares ni Pókar Solución Comenzamos formando la tercia, para ello hay que fijar el número que formara la tercia, dicho número se puede escoger de 13 formas distintas. Ahora bien con el número fijo puede haber cuatro cartas posibles y dado que queremos seleccionar tres, entonces las podemos escoger de 4 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 3 Luego entonces la tercia puede ser escogida de 4 13 ( ) 3 Seleccione ahora las dos cartas restantes, para ello necesitamos dos números que pueden ser escogidos de un conjunto de 12 números, dado que en estas cartas no puede haber dos números iguales y no importa el orden, entonces estos pueden ser elegidos de 12 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 2 Cada pareja de números genera 4 ∙ 4 = 16 posibles cartas, entonces las dos cartas restantes se pueden escoger de 12 ( )∙4∙4 2 Por lo tanto hay 4 12 13 ( ) ∙ ( ) ∙ 4 ∙ 4 = 54,912 𝑚𝑎𝑛𝑜𝑠 𝑐𝑜𝑛 𝑢𝑛𝑎 𝑡𝑒𝑟𝑐𝑖𝑎 𝑒𝑥𝑎𝑐𝑡𝑎𝑚𝑒𝑛𝑡𝑒. 3 2

26

Combinatoria | Arturo Flores Aguilar Ejemplo 2 a) ¿Cuantas manos de póker habrá en las que aparezcan exactamente un par? Solución: Comencemos formando el par, para ello seleccionemos el número, este puede ser elegido de 13 formas. Ahora bien cada número genera 4 posibles cartas y como formaremos un par, entonces esa pareja se puede elegir de 4 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 2 Así el par puede formarse de 4 13 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒𝑠 2 Seleccionemos las tres cartas restantes, para ello necesitamos 3 números de los posibles 12 restantes, dado que el orden de las cartas no importa, entonces los tres números pueden escogerse de 12 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 3 Cada triplete de números, genera 4 ∙ 4 ∙ 4 𝑐𝑎𝑟𝑡𝑎𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒𝑠, entonces las tres cartas pueden elegirse de 12 ( ) 43 𝑓𝑜𝑟𝑚𝑎𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒𝑠 3 Así una mano con esta configuración tiene 4 12 13 ( ) ∙ ( ) 43 = 1,098,240 𝑓𝑜𝑟𝑚𝑎𝑠 𝑝𝑜𝑠𝑖𝑏𝑙𝑒𝑠 2 3 Ejemplo 3 ¿Cuántas manos de póker hay que tengan FULL? Solución Un full está formado por una tercia y un par. Comenzamos generando la tercia, para ello seleccionamos un número de los 13 disponibles, luego cada número genera 4 cartas disponibles de las cuales vamos a seleccionar solo tres, debe quedar claro que el total de tercias que podemos formar es 4 13 ( ) 3

27

Combinatoria | Arturo Flores Aguilar Para formar el par hay que tener en cuenta que el número a seleccionar no puede ser el mismo que él de la tercia, por lo tanto el número del par se puede seleccionar de 12 formas diferentes, cada uno de los 12 números genera 4 posibles cartas, pero como queremos formar un par, entonces el par viene dado por 4 ( ) 2 Así el total de formas que podemos formar el par es 4 12 ( ) 2 Finalmente el total de manos que tiene full es: 4 4 13 ( ) ∙ 12 ( ) = 3744 3 2

Ejemplo 4: Halle el número de manos de póker tales que tengan exactamente dos pares distintos. Solución: Puesto que los pares son distintos, entonces primero hay que seleccionar dos números distintos del conjunto de los 13 números diferentes, estos se pueden elegir de 13 ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 2 Cada número seleccionado genera 4 cartas posibles debido a los 4 palos, para cada número hay que elegir dos cartas, estas se pueden seleccionar de 4 ( ) 2 Entonces los dos pares se pueden formar de 13 4 4 ( ) ∙ ( ) ∙ ( ) 𝑓𝑜𝑟𝑚𝑎𝑠 2 2 2

28

Combinatoria | Arturo Flores Aguilar Finalmente la última carta no puede llevar ningún número de los pares anteriores, entonces la carta sobrante puede llevar cualquiera de los 11 números restantes, además como cada número genera 4 posibles cartas, entonces la última carta puede escogerse de 11 ∙ 4 𝑓𝑜𝑟𝑚𝑎𝑠. Así, el total de manos de póker que tienen dos pares distintos es de 13 4 4 ( ) ∙ ( ) ∙ ( ) ∙ (11 ∙ 4) = 123,552 2 2 2

Ejemplo 5 ¿Cuántas manos de póker tienen ESCALERA? Solución: Consideremos 5 casillas ______ ______ ______ ______ ______ La primera casilla será para la carta con el número más bajo y así sucesivamente hasta la quinta casilla que será para la carta con el número mayor. Sabemos que la escalera más alta es la formada por las cartas 10 − 𝐽 − 𝑄 − 𝐾 − 𝐼. Por lo tanto el la primera casilla, pueden estar los valores 𝐴, 2, 3, 4, 5, ,6, 7, 8, 9,10 Una vez seleccionado el primer número los cuatro restantes ya quedan determinados, ahora lo único que falta es seleccionar el palo para cada una de las 5 cartas, esté puede ser de 4 formas distintas, por lo tanto, el total de escaleras que se pueden formar es de 10 ∙ 45

29

Combinatoria | Arturo Flores Aguilar

Ejercicios 2.2.4 Problema 1 De un grupo de 24 personas se quiere elegir 5 representantes de la siguiente forma: Pedro y Luis deben estar en el grupo elegido. Hay 8 mujeres en total pero a lo más deben figurar 2 en el grupo. ¿de cuantas maneras distintas puede hacerse la elección? Problema 2 De un conjunto de 10 botes de distintos colores se quiere escoger 5 de tal manera que 3 sean para dulces y 2 para chocolates. ¿De cuantas formas distintas es posible hacer la elección? Problema 3 a) ¿Cuántas manos de póker hay que tengan al menos dos cartas del mismo número? b) ¿Cuántas hay que tengan al menos tres cartas del mismo número? Problema 4 a) ¿Cuántas manos de póker hay tal que tengan exactamente 4 cartas del mismo número? b) ¿Cuántas manos de póker hay que tengan FLOR? Problema 5 ¿Cuántas manos de póker posibles hay tal que sean FLOR y ESCALERA? A dicho arreglo se le llama FLOR IMPERIAL Problema 6 Una clase de baile consta de 22 estudiantes, de los cuales 10 son mujeres y 12 son hombres. Si seleccionamos 5 hombres y 5 mujeres y luego se emparejan. ¿Cuántos resultados son posibles? Problema 7 a) ¿Cuántos caminos diferentes hay de A hacia B en la cuadricula anterior si solo podemos movernos hacia la derecha y hacia arriba?

30

Combinatoria | Arturo Flores Aguilar b) Misma pregunta que en el ejemplo anterior, solo que ahora se tiene que pasar forzosamente por el punto Q.

Problema 8 En la siguiente cuadricula. ¿Cuántos caminos hay de A hacia B, tales que pasen por el segmento CD? Al igual que antes solo podemos movernos hacia la derecha y hacia arriba

Problema 9 Considera un grupo de 𝑛 𝐻𝑜𝑚𝑏𝑟𝑒𝑠 𝑦 𝑚 𝑚𝑢𝑗𝑒𝑟𝑒𝑠. a) ¿Cuántos grupos de tamaño 𝑟 son posibles? b) ¿puedes usar la respuesta del inciso anterior para comprobar que

𝑛+𝑚 𝑛 𝑚 𝑛 𝑚 𝑛 𝑚 ( )=( )∙( )+( )∙( ) + ⋯+ ( ) ∙ ( )? 𝑟 0 𝑟 1 𝑟−1 𝑟 0

31

Combinatoria | Arturo Flores Aguilar Problema 10 Comprueba que

𝑛 𝑛 ( )=( ) 𝑟 𝑛−𝑟 Problema 11 Siguiendo las líneas de la figura, ¿Cuántos caminos hay para ir del punto A al punto B que no pasen dos veces por el mismo punto y que solo avancen hacia abajo y hacia los lados pero no hacia arriba?

Problema 12 a) Utilizando los vértices de una cuadricula de 6 × 6. ¿Cuántos cuadrados se pueden formar si sus lados no necesariamente son paralelos a los lados del cuadrado original? ¿Cuántos si la cuadricula fuera de 𝑛 × 𝑛?

b) Utilizando los 36 vértices de una cuadricula de 5 × 5. ¿Cuántos triángulos distintos se pueden formar? Problema 13 ¿Cuántos cuadriláteros pueden formarse uniendo cuatro vértices de un octágono?

32

Combinatoria | Arturo Flores Aguilar Problema 14 Un polígono de 19 lados es trazado sobre una circunferencia a) Halle el número de diagonales del polígono b) ¿Cuántos triángulos pueden formarse uniendo los vértices del polígono? c) ¿Cuántos triángulos puede formarse uniendo los vértices de un polígono regular de 𝑛 𝑙𝑎𝑑𝑜𝑠 inscrito sobre un circulo?

Problema 15 Una caja contiene canicas de dos colores distintos, azul y verde. Supón que extraemos canicas al azar; bajo esta condición ¿Cuál es el mínimo número de canicas que hay que extraer de la caja para garantizar que hay 100 canicas del mismo color?

33

Combinatoria | Arturo Flores Aguilar

2.2.3 Principio de las Casillas El principio de las casillas

o también llamado principio de las pichoneras tiene múltiples

aplicaciones, una aplicación interesante que veremos será la técnica de coloración que se estudia en el siguiente apartado. El principio es simple y dice lo siguiente:

“Si se dispone de 𝒏 𝒑𝒊𝒄𝒉𝒐𝒏𝒆𝒓𝒂𝒔 (casillas) para colocar 𝒎 𝒑𝒂𝒍𝒐𝒎𝒂𝒔(𝒐𝒃𝒋𝒆𝒕𝒐𝒔) 𝒄𝒐𝒏 𝒎 > 𝒏 , entonces en alguna pichonera deberán colocarse por lo menos dos palomas” La mayoría de las veces este principio nos ayuda a resolver problemas de existencia; ayuda a garantizar si dentro de una serie de hechos hay la certeza de que alguna situación especial ocurra, desafortunadamente muchas veces no nos proporciona el método para mostrar la forma en cómo ocurre la situación. Ejemplificamos la aplicación de este método con los siguientes problemas, quizás en un curso básico puede omitirse esta sección.

34

Combinatoria | Arturo Flores Aguilar Problema 1 Una caja contiene canicas de dos colores distintos, azul y verde. Supón que extraemos canicas al azar; bajo esta condición a) ¿Cuál es el mínimo número de canicas que hay que extraer de la caja para garantizar que hay dos canicas del mismo color? Solución Imagina que las casillas son los colores (y las palomas las canicas), es decir, hay dos casillas, para garantizar dos canicas en la misma casilla necesitamos extraer 2+1=3 canicas por lo menos. b) ¿Cuál es el mínimo número de canicas que hay que extraer de la caja para garantizar 10 del mismo color? Si sacamos 2, puede ocurrir que una sea verde y la otra azul, por el principio de casillas, necesitamos sacar por lo menos 2 + 1, para garantizar que hay dos del mismo color. Si sacáramos 2 × 2 = 4 𝑐𝑎𝑛𝑖𝑐𝑎𝑠 puede ocurrir que haya dos verdes y dos azules, entonces, si sacamos 2 × 2 + 1 = 5 canicas, entonces con ello garantizamos que hay por lo menos 2 + 1 = 3 de un color. Continuemos el proceso una vez más, si sacáramos 2 × 3 = 6 canicas, entonces puede ocurrir que haya 3 de cada color, entonces para garantizar que hay por lo menos 4 = 3 + 1 de un color tendríamos que sacar por lo menos 2 × 3 + 1 𝑐𝑎𝑛𝑖𝑐𝑎𝑠. Queremos que haya 10 = 9 + 1 canicas de un mismo color, entonces, necesitaríamos sacar por lo menos 2 × 9 + 1 = 19 𝑐𝑎𝑛𝑖𝑐𝑎𝑠

Problema 2 Un millón de pinos crecen en el bosque. Se sabe que ningún pino tiene más de 600,000 𝑎𝑔𝑢𝑗𝑎𝑠. ¿Puedes asegurar que hay dos pinos que tienen el mismo número de agujas? Solución En este problema piensa que las casillas son las agujas de los pinos; entonces hay 600,001 𝑐𝑎𝑠𝑖𝑙𝑙𝑎𝑠 pues contamos con la casilla de 0 𝑎𝑔𝑢𝑗𝑎𝑠, 1 𝑎𝑔𝑢𝑗𝑎, 3 𝑎𝑔𝑢𝑗𝑎𝑠, 𝑒𝑡𝑐. ℎ𝑎𝑠𝑡𝑎 𝑙𝑙𝑒𝑔𝑎𝑟 𝑎 600,000. Para garantizar que

35

Combinatoria | Arturo Flores Aguilar hay dos pinos con el mismo número de agujas basta que haya más pinos que casillas lo cual es verdadero.

Problema 3 En un papel cuadriculado de 6 × 9 𝑐𝑢𝑎𝑑𝑟𝑎𝑑𝑜𝑠 se consideran 25 triángulos arbitrarios y diferentes que tienen sus vértices en los puntos de intersección de las líneas de la cuadricula. Comprueba que no importa la elección de los triángulos, forzosamente hay al menos dos triángulos con al menos un vértice en común Solución

36