Cap´ıtulo 4 Combinatoria La Combinatoria estudia las distintas formas de agrupar o seleccionar los elementos de un conjunto finito, calcula cuantas selecciones hay y, en ocasiones, las genera. El tipo de selecci´on que se puede hacer depende de varios aspectos; por ejemplo del n´ umero de selecciones de los elementos que se hacen, de si influye o no el orden en la selecci´on, de si un mismo elemento puede seleccionarse una o m´as veces o si deben seleccionarse todos los elementos disponibles.

Matemática Discreta. Área de Álgebra Universidade da Coruña

4.1.

T´ ecnicas b´ asicas

Proposici´ on 9. (Principio de la suma) Sean {Ai ; i = 1, . . . , n} conjuntos finitos con Ai ∩ Aj = ∅, para todo i 6= j. Entonces: n [

i=1

Demostraci´on. Inducci´on en n.

Ai

=

n X

|Ai |

i=1

Ejemplo 59. Se quiere elegir un representante de primero de la Facultad para ir a la Olimpiada de Inform´atica. ¿Cu´ antas posibilidades hay para elegir si en cada grupo de Ingenier´ıa hay 60 alumnos y en cada grupo de las T´ecnicas hay 100 alumnos? (hay dos grupos en la Ingenier´ıa y cuatro en las T´ecnicas). En total, tenemos 2 · 60 + 4 · 100 = 120 + 400 = 520 alumnos para escoger.

Ejemplo 60. Una biblioteca dispone de 50 libros sobre L´ ogica y 70 libros sobre Combinatoria. Por el principio de la suma, un alumno puede elegir entre 120 = 50 + 70 libros para consultar alguno de esos temas. 93

CAP´ITULO 4. COMBINATORIA

94

Ejemplo 61. Un restaurante italiano prepara 5 variedades de espaguetis, 6 de macarrones y 3 de lasa˜ na. Un cliente puede elegir entre 14 = 5 + 6 + 3 platos de pasta para comer. Podemos pensar que cada conjunto Ai est´a formado por las distintas maneras de realizar una cierta tarea i (i = 1, 2, . . . , n) y no se pueden realizar dos tareas simult´aneamente. El principio de la suma dice que el n´ umero de formas de realizar alguna de las n tareas es la suma de las maneras de realizar cada una de ellas. Proposici´ on 10. (Principio del producto) Sean {Ai ; i = 1, . . . , n} conjuntos finitos. Entonces: |A1 × A2 × · · · × An | =

n Y

|Ai |

i=1

Demostraci´on. Inducci´on en n.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 62. Para decidir sobre la instalaci´ on o no de un nuevo sistema operativo, el director de un centro reparte a 12 empleados en dos comit´es. El comit´e A consta de 5 miembros y estudiar´ a las ventajas del nuevo sistema. El comit´e B, formado por los 7 empleados restantes, analizar´ a los inconvenientes del sistema. Para tomar una decisi´ on el director quiere hablar con un miembro de cada grupo. Por el principio del producto lo podr´ a hacer de 5 · 7 = 35 formas distintas. Ejemplo 63. Se quiere dise˜ nar un c´ odigo para cada alumno de la Facultad utilizando dos letras (las 26 del alfabeto, sin la n ˜ ) y cuatro cifras (del 0 al 9). Si se pueden repetir las letras pero no las cifras, ¿cu´ antos c´ odigos diferentes se pueden hacer? Podremos formar 26 · 26 · 10 · 9 · 8 · 7 = 676 · 5040 = 3407040 c´ odigos distintos. Siguiendo con el ejemplo anterior, ¿cu´antos c´odigos podremos formar si permitimos que haya c´odigos sin letras (es decir s´olo con cifras), c´odigos con una sola letra y cuatro cifras y c´odigos con dos letras y cuatro cifras? (igual que antes, permitimos que se repitan las letras pero no las cifras) Hay 5040 c´odigos sin letras, 26 · 5040 = 131040 c´odigos con una sola letra y 3407040 c´odigos con dos letras y cuatro n´ umeros. En total tenemos, 5040+131040+3407040 = 3543120 posibles combinaciones. Alternativamente podemos pensar en este principio de la siguiente forma. Una gran tarea se puede dividir en n etapas o subtareas sucesivas, cada conjunto Ai est´a constituido por las distintas formas de realizar la etapa

´ ´ 4.1. TECNICAS BASICAS

95

i (i = 1, 2, . . . , n). Siempre que se cumpla que modificar la forma en que se realiza una etapa cualquiera modifica la forma de realizar la tarea total; el principio del producto dice que el n´ umero de formas de realizar la tarea principal es el producto de las formas de realizar cada una de las etapas. Proposici´ on 11. (Principio de distribuci´ on, del palomar o del caj´ on de Dirichlet) Sean m, n y p tres n´ umeros naturales. Si se desean colocar np + m objetos en n cajas, alguna caja debe contener al menos p + 1 objetos. Demostraci´on. Si cada caja contiene como mucho p objetos, el n´ umero total de objetos que podemos colocar es np < np + 1 ≤ np + m. En su versi´on m´as simple, este principio dice que si queremos colocar m objetos en n cajas, con m > n, al menos una caja debe contener 2 o m´as objetos. Es decir, si m > n no puede existir un aplicaci´on inyectiva de un conjunto de m elementos en un conjunto de n elementos. Ejemplo 64. En una reuni´on de ocho personas, al menos dos de ellas nacieron el mismo d´ıa de la semana. Si hay trece o m´ as, dos nacieron el mismo mes.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 65. Una reuni´on est´a formado por n matrimonios. ¿Cu´ antas personas tiene que tener un grupo para poder asegurar que hay al menos un matrimonio entre ellos? El grupo est´a formado por, al menos, n + 1 personas.

Ejemplo 66. Si la media aritm´etica de {x1 , x2 , · · · , xn } n´ umeros naturales es estrictamente mayor que p, uno de los n´ umeros es mayor que p.

Ejemplo 67. Si se escogen seis n´ umeros cualesquiera del 1 al 10, por lo menos dos de estos n´ umeros suman 11.

Consideremos las cinco “cajas” {1, 10}, {2, 9}, {3, 8}, {4, 7} y {5, 6}. Asociemos a cada n´ umero la caja que lo contiene. Puesto que hay cinco cajas y seis n´ umeros, habr´a dos n´ umeros en la misma caja, lo cual implica que suman 11. Ejemplo 68. Demuestra que, dado cualquier conjunto de siete enteros distintos, hay al menos dos de ellos cuya suma o diferencia es un m´ ultiplo de 10.

Consideremos las “cajas” {1, 9}, {2, 8}, {3, 7}, {4, 6}, {0} y {5}. Asociemos a cada n´ umero la caja que contiene a su cifra de las unidades. Puesto que hay seis cajas y siete n´ umeros, habr´a dos n´ umeros en la misma caja. Si

CAP´ITULO 4. COMBINATORIA

96

la caja es la u ´ltima o la pen´ ultima, su suma y su diferencia es un m´ ultiplo de 10. Si es una de las otras, y los dos n´ umeros tienen la misma cifra de las unidades, su diferencia es un m´ ultiplo de 10, mientras que si la cifra de las unidades es diferente, su suma ser´a un m´ ultiplo de 10. Ejemplo 69. Tenemos que pintar 64 bicicletas con 7 colores distintos. Demuestra que hemos de pintar al menos 10 del mismo color. Aplicaremos el principio de distribuci´on con n = 7 (colores), p = 9 y m = 1, ya que hay 7 · 9 + 1 = 64 objetos.

4.2.

Variaciones, Permutaciones y Combinaciones

Contaremos las diferentes colecciones que se pueden formar, seg´ un una ley dada (repitiendo o no los elementos, teniendo en cuenta o no el orden), con los elementos de un conjunto finito.

Variaciones

Matemática Discreta. Área de Álgebra Universidade da Coruña

Definici´ on 62. Sea n un n´ umero natural no nulo, se define el factorial de n, n! = n · (n − 1) · (n − 2) · . . . · 3 · 2 · 1. Adem´ as 0! = 1. Para todo natural n ≥ 1, se verifica que n! = n · (n − 1)! o (n + 1)! = (n + 1) · n!. Sea A = {a1 , a2 , . . . , an } un conjunto finito de n elementos y r un n´ umero natural menor o igual que n. Una variaci´ on (ordinaria o sin repetici´on) de los n elementos de A de orden r es una selecci´on o lista ordenada de r elementos distintos de A. Dos variaciones son distintas si se diferencian en alg´ un elemento o en la posici´on de alguno de estos en la variaci´on. Por ejemplo, si A = {1, 2, 3, 4} son variaciones de orden tres diferentes 123 y 124, pero tambi´en 123 y 321. Nota 2. Una variaci´on de orden r de los elementos de A es una aplicaci´on inyectiva de {1, 2, . . . , r} en A. Teorema 10. El n´ umero de variaciones de un conjunto de n elementos de n! orden r es V (n, r) = n(n − 1) · . . . · (n − r + 1) = (n−r)! . Demostraci´on. Aplicaci´on del principio del producto.

4.2. VARIACIONES, PERMUTACIONES Y COMBINACIONES

97

Ejemplo 70. ¿De cu´antas formas un equipo de bi´ ologos puede programar tres salidas al campo en los pr´oximos cinco d´ıas para recoger muestras? V (5, 3) = 5 · 4 · 3 = 60 Ejemplo 71. Disponemos de siete despachos y queremos asignar cuatro de ellos a cuatro nuevos empleados y dejar el resto para m´ as adelante. ¿De cu´antas formas se puede realizar la asignaci´ on? V (7, 4) = 7 · 6 · 5 · 4 = 840 Ejemplo 72. ¿Cu´antas palabras de cinco letras distintas se pueden formar con las letras de la palabra DISCRETA? V (8, 5) = 8 · 7 · 6 · 5 · 4 = 6720 Ejemplo 73. El consejo directivo de una empresa farmac´eutica tiene 10 miembros de los cuales tres son m´edicos. Se va a elegir presidente, vicepresidente, secretario y tesorero del consejo. i) ¿De cu´antas formas se pueden elegir si se quiere que lo presida un m´edico?

Matemática Discreta. Área de Álgebra Universidade da Coruña

ii) Idem si queremos que haya exactamente un m´edico entre los elegidos. iii) Idem si se quiere que haya al menos un m´edico entre los cuatro. i) Para presidente tenemos 3 candidatos. Para los otros tres puestos, podemos elegir a cualquiera que no sea el presidente (son 9), as´ı en total tenemos 3 · V (9, 3) = 3 · 9 · 8 · 7 = 1512 posibilidades. ii) Supongamos que el m´edico es el presidente. Tenemos 3 candidatos para ese puesto. Para los otros tres puestos hay 7 candidatos (todos los miembros del consejo que no son m´edicos), lo que nos da un total de 3 · V (7, 3) = 3 · 7 · 6 · 5 = 630 comisiones presididas por un m´edico. Para los otros tres puestos el razonamiento es similar, y la respuesta es 4 · 630 = 2520.

CAP´ITULO 4. COMBINATORIA

98

iii) Restaremos a las posibilidades totales (V (10, 4) = 10·9·8·7 = 5040) las posibilidades que tenemos de elegir los cuatro puestos sin ning´ un m´edico que ser´an V (7, 4) = 7·6·5·4 = 840. Nos quedan pues 5040−840 = 4200 formas de elegir los candidatos garantizando que al menos uno de ellos es un m´edico.

Variaciones con repetici´ on Sea A = {a1 , a2 , . . . , an } un conjunto finito de n elementos y r un n´ umero natural. Una variaci´ on con repetici´ on de los n elementos de A de orden r es una selecci´on o lista ordenada de r elementos, no necesariamente distintos, de A. Dos variaciones con repetici´on son distintas si se diferencian en n´ umero de veces que aparece alg´ un elemento de A o en la posici´on de estos en la variaci´on. Por ejemplo, si A = {1, 2, 3, 4} son variaciones con repetici´on de orden tres diferentes 123 y 124, 123 y 321, 122 y 112; por u ´ltimo, 122 y 212. En general, dos variaciones con o sin repetici´on de un conjunto A de orden r son distintas si en alguna de las r selecciones o posiciones los correspondientes elementos de A son diferentes.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Nota 3. Cualquier variaci´ on (con repetici´ on) de orden r de los elementos de A es una aplicaci´on de {1, 2, . . . , r} en A. Teorema 11. El n´ umero de variaciones con repetici´ on de un conjunto de n r elementos de orden r es V R(n, r) = n . Demostraci´on. Al poder repetir los elementos, en cada una de las elecciones tenemos disponibles los n elementos, por lo que el principio del producto garantiza el resultado. Ejemplo 74. ¿Cu´antos n´ umeros de cuatro cifras se pueden formar con los d´ıgitos 1, 3, 5, 7 y 9? V R(5, 4) = 54 = 625 Ejemplo 75. ¿Cu´antas palabras de cinco letras no necesariamente distintas se pueden formar con las letras de la palabra DISCRETA? V R(8, 5) = 85 = 32768 Ejemplo 76. En una cafeter´ıa nos dicen que cada bocadillo puede estar formado por los siguientes ingredientes: jam´ on, chorizo, queso, tomate, lechuga, mayonesa y esp´arragos, ¿cu´ antos bocadillos distintos podemos elegir?

4.2. VARIACIONES, PERMUTACIONES Y COMBINACIONES

99

Para cada ingrediente tenemos dos posibilidades, escogerlo (1) o no (0). Como hay siete ingredientes, tenemos, en total 27 = 128 posibles bocadillos. Ejemplo 77. ¿De cu´antas maneras se pueden distribuir 8 bolas diferentes en cinco cajas de distinto color? Se trata de contar el n´ umero de aplicaciones del conjunto {1, 2, . . . , 8} en el conjunto {1, 2, . . . , 5} que es V R(5, 8) = 58 = 390625.

Permutaciones Sea A = {a1 , a2 , . . . , an } un conjunto finito de n elementos. Una permutaci´ on del conjunto A es una aplicaci´on biyectiva de A en A. El conjunto de las permutaciones de A se representa por SA . Teorema 12. El n´ umero de permutaciones de un conjunto de n elementos es P (n) = n! = n · (n − 1) · . . . · 2 · 1. Demostraci´on. Para elegir la imagen de a1 tenemos n posibilidades (todas), para la de a2 tenemos n − 1 elementos para escoger (todos menos el que hemos tomado como imagen de a1 ), etc. El principio del producto garantiza el resultado.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 78. ¿Cu´antos n´ umeros de cinco cifras distintas se pueden formar con los d´ıgitos 1, 3, 5, 7 y 9? Como son cinco d´ıgitos distintos, el resultado es 5! = 120.

Ejemplo 79. Con las letras de “COMPUTER”, ¿cu´ antas palabras de ocho letras se pueden formar?

Como son ocho letras distintas, el resultado es 8!. Las permutaciones de un conjunto A tambi´en se pueden definir como las posibles reordenaciones de los n elementos de A; es decir, como aplicaciones inyectivas del conjunto {1, 2, . . . , n} en A o variaciones de n elementos de orden n, V (n, n).

Permutaciones con repetici´ on Estudiemos el caso de las permutaciones permitiendo la repetici´on de los elementos. Sabemos que hay 8! formas de ordenar las letras de “COMPUTER”. Si consideramos las letras de la palabra “CAJA”, est´a claro que no son 4! = 24 posibles ordenaciones ya que las dos A juegan el mismo papel. De hecho, s´olo hay 12 ordenaciones posibles. De forma similar, las posibles ordenaciones de las letras de “ARRABAL” no son 7! = 5040, s´olo son 420.

CAP´ITULO 4. COMBINATORIA

100

Consideremos n objetos, distribuidos en r tipos o clases distintas. Los objetos de un mismo tipo son iguales entre s´ı, pero diferentes de los de cualquier otro tipo. Hay n1 objetos del tipo 1, n2 objetos del tipo 2 y, sucesivamente, nr objetos del tipo r; as´ı n = n1 + n2 + · · · + nr . Las distintas permutaciones que se pueden hacer en estas condiciones reciben el nombre de permutaciones con repetici´on de n objetos con n1 , n2 , . . . , nr repeticiones y su n´ umero es P R(n; n1 , n2 , . . . , nr ) =

n! n1 ! n2 ! . . . nr !

con n = n1 + n2 + . . . + nr . Demostraci´on. Por el principio del producto, de cada una de las permutaciones con repetici´on se obtienen n1 ! · n2 ! · . . . · nr ! permutaciones usuales, una por cada posible ordenaci´on de los ni objetos de cada tipo, si los consideramos distintos. Por tanto, P R(n; n1 , n2 , . . . , nr ) · n1 ! · n2 ! · . . . · nr ! = n! = P (n). Despejando se obtiene la expresi´on. Ejemplo 80. i) ¿De cu´ antas formas se pueden ordenar las letras de la palabra ABRACADABRA? Como hay 5 A’s, 2 B’s, 2 R’s una C y una D, tenemos 11! 11 · 10 · 9 · 8 · 7 · 6 = = 5! 2! 2! 4 = 11 · 10 · 9 · 2 · 7 · 6 = 83160

Matemática Discreta. Área de Álgebra Universidade da Coruña

P R(11; 5, 2, 2, 1, 1) =

posibles ordenaciones. ii) ¿En cu´antas figuran cuatro A’s juntas (exactamente cuatro)? Formamos un bloque con cuatro A’s y ordenamos primero 2 R’s, 2 B’s, la otra A, una D y una C, lo cual puede hacerse de P R(7; 2, 2, 1, 1, 1) =

7! 7·6·5·4·3·2 = = 1260 2! 2! 4

formas. Por otro lado, el bloque de A’s que tenemos podemos colocarlo en cualquiera de las seis posiciones que no se corresponden con la anterior y la posterior a la A1 , para que no queden las cinco A’s juntas. As´ı, la respuesta es: 6 · 1260 = 7560 colocaciones posibles. 1

Si la ordenaci´on fuese ABBRRCD, podemos situarlo en lugar de cualquiera de los 2, es decir AB2B2R2R2C2D2.

4.2. VARIACIONES, PERMUTACIONES Y COMBINACIONES

101

iii) ¿En cu´antas figura cada B seguida de al menos 2 A’s? Formamos dos bloques BAA, BAA. Quedan 2 R’s, una C, una D, una A y dos bloques. Por lo tanto, tenemos 7! 7·6·5·4·3·2 = = 1260 posibilidades. 2! 2! 4 iv) ¿En cu´antas figuran los bloques ABR? Hay dos bloques ABR y quedan 3 A’s, una C y una D. tenemos, en total 7·6·5·4 7! = = 420 3! 2! 2 disposiciones con los bloques requeridos. Ejemplo 81. Para trasladarnos de un punto A(0,0) hasta un punto B(5,4) podemos movernos u ´nicamente de izquierda a derecha y de arriba a abajo. ¿De cu´antas maneras podemos ir desde A hasta B? Una posible ruta ser´ıa DDDDDAAAA (se corresponde con bordear el rect´angulo). Cualquier ruta es una cadena de 9 elementos con 5 D’s y 4 A’s. As´ı pu´es, la soluci´on es: 9! P R(9; 5, 4) = 5! 4! Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 82. La profesora de educaci´ on f´ısica de un colegio decide formar cuatro equipos de voleibol (A, B, C y D) de nueve ni˜ nas cada uno entre las 36 alumnas de primer curso. ¿De cu´ antas formas se pueden formar los cuatro equipos? 36! P R(36; 9, 9, 9, 9) = 9! 9! 9! 9!

Combinaciones Supongamos que entre cuatro alumnos; Ant´on, Brais, Carlos y Diego, queremos elegir una comisi´on de tres para asistir a una reuni´on. La comisi´on formada por Ant´on, Brais y Carlos es la misma que la formada por Carlos, Ant´on y Brais. El orden no importa, lo que importa es estar o no en la comisi´on, ¿Cu´antas comisiones se pueden formar? Sea A = {a1 , a2 , . . . , an } un conjunto finito de n elementos y sea r un n´ umero natural menor o igual que n. Una combinaci´ on (ordinaria o sin repetici´on) de los n elementos de A de orden r es un subconjunto (selecci´on no ordenada) de r elementos distintos de A. Dos combinaciones son diferentes si difieren en alguno de sus elementos.

CAP´ITULO 4. COMBINATORIA

102

Teorema 13. El n´ umero de combinaciones de un conjunto de n elementos de orden r es ! n n! C(n, r) = = . r r! (n − r)! Demostraci´on. De cada una de las C(n, r) posibles combinaciones se obtienen P (r) = r! variaciones distintas; las posibles ordenaciones de los r elementos seleccionados. Por el principio del producto C(n, r) · r! = V (n, r) =

n! (n − r)!

despejando se obtiene la expresi´on. Corolario 1.

!

!

n n = , r n−r

para todo 0 ≤ r ≤ n.

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 83. ¿De cu´antas formas se pueden seleccionar cinco jugadores de ! 10 un grupo de diez personas para formar un equipo? C(10, 5) = = 252. 5 Ejemplo 84. Un estudiante debe realizar un examen de MD con diez preguntas de las que debe contestar siete. ¿Cu´ antos tipos diferentes de examen puede corregir el profesor? Si debe contestar tres de entre las cinco primeras y cuatro de entre las cinco u ´ltimas, ¿cu´ antos tipos posibles de examen hay en este caso? Lo mismo si en las especificaciones previas se dice que debe contestar al menos tres de entre las cinco primeras preguntas. !

!

!

10 5 5 · = 10 · 5 = 50 = 120, en el segundo En el primer caso son 4 3 7 ! ! ! ! ! 5 5 5 5 5 y, en el tercero, · + · + = 50 + 50 + 10 = 110. 3 4 4 3 2 Ejemplo 85. Elena quiere escoger cinco cartas de una baraja de p´ oker (13 de cada palo: picas, tr´eboles, diamantes y corazones) ¿De cu´ antas formas puede hacerlo si quiere escoger al menos un tr´ebol? !

52 Tiene = 2598960 formas de escoger las cinco cartas. De estas, 5 las ! que no le interesan son aquellas en las que no hay tr´eboles que son 39 = 575757. Luego, la respuesta es 2598960 − 575757 = 2023203 posibles 5 selecciones

4.2. VARIACIONES, PERMUTACIONES Y COMBINACIONES

103

Ejemplo 86. Un profesor de Matem´ atica Discreta cuenta cinco chistes cada mes. ¿Cu´antos chistes diferentes debe conocer el profesor para que en un per´ıodo de cuatro a˜ nos no repita el mismo conjunto de cinco chistes? Necesitamos n para que C(n, 5) sea al menos 48 (n´ umero de meses en 4 a˜ nos). Puesto que C(7, 5) = 21 y C(8, 5) = 56, debe conocer al menos 8 chistes diferentes. Ejemplo 87. Un gimnasio abre todos los d´ıas de la semana y cada socio acude al menos tres d´ıas por semana. ¿Cu´ al es el m´ınimo n´ umero de socios que debe tener para garantizar que al menos dos de ellos coinciden los mismos d´ıas? Cada socio puede acudir 3, 4, 5, 6 o todos los d´ıas de la semana, lo que nos da un total de 7 X

k=3

!

!

2 X 7 7 = 27 − = 128 − 1 − 7 − 21 = 99 k k=0 k

posibles selecciones de los d´ıas de la semana que acude cada socio. Si hay 100 socios, al menos dos coinciden los mismos d´ıas.

Combinaciones con repetici´ on Matemática Discreta. Área de Álgebra Universidade da Coruña

En una helader´ıa disponen de 5 sabores diferentes para un helado. ¿De cu´antas formas se pueden elegir 10 helados? En este ejemplo, se trata de combinaciones (no importa el orden de elecci´on) pero es obvio que hemos de repetir sabor ya que n (5) es menor que r (10). Sea A = {a1 , a2 , . . . , an } un conjunto finito de n elementos y sea r un n´ umero natural. Una combinaci´ on con repetici´ on de los n elementos de A de orden r es una selecci´on no ordenada de r elementos, no necesariamente distintos, de A. Dos combinaciones con repetici´on de orden r son distintas si el n´ umero de apariciones de alg´ un elemento de A en las selecciones es diferente. Por ejemplo, si A = {1, 2, 3, 4} son combinaciones con repetici´on de orden tres diferentes {1, 2, 3} y {1, 2, 4}, {1, 2, 2} y {1, 1, 2}. Sin embargo, son la misma combinaci´on {1, 2, 3} y {1, 3, 2}, al igual que {2, 1, 2} y {2, 2, 1}.

Teorema 14. El n´ umero de combinaciones con repetici´ on de un conjunto de n elementos de orden r es !

!

n+r−1 n+r−1 CR(n, r) = C(n + r − 1, r) = = . r n−1

CAP´ITULO 4. COMBINATORIA

104

Demostraci´on. Cada combinaci´on con repetici´on de orden r de los elementos de A se corresponde con una soluci´on de x1 + x2 + . . . + xn = r, siendo xi el n´ umero de veces que elegimos el elemento i-´esimo. As´ı pues, estamos considerando u ´nicamente soluciones (x1 , x2 , . . . , xn ) con xi ∈ Z, xi ≥ 0, para cada i. Por otro lado, cada soluci´on no negativa (x1 , x2 , . . . , xn ) de la ecuaci´on anterior se corresponde con una cadena de r 1’s y n − 1 barras distribuidos como: x x x 1

z }| {

2

z }| {

n

z }| {

1...1 | 1...1|···|1...1 Por lo tanto, buscamos el n´ umero de formas decolocar   n−1  barras en n+r−1 n+r−1 n+r−1 2 posiciones . Ese n´ umero es claramente n−1 = . r

Ejemplo 88. En una gran cesta de frutas hay manzanas, naranjas, peras, fresas y pl´atanos. ¿De cu´ antas formas se!puede hacer un batido con cuatro 8 piezas de fruta? CR(5, 4) = C(8, 4) = = 70. 4

Matemática Discreta. Área de Álgebra Universidade da Coruña

Ejemplo 89. ¿De cu´antas formas se pueden colocar 12 bolas en cinco recipientes si a) cada bola es de un color diferente, b) todas las bolas son iguales? Si los objetos son todos diferentes, para cada objeto tenemos 5 elecciones posibles (los cinco recipientes), luego hay 512 posibilidades; son cadenas ordenadas de longitud 12 formadas con 1, 2, 3, 4 y 5, es decir V R(5, 12). Si las bolas son iguales, lo que interesa es saber cu´antas bolas habr´a en cada recipiente, es decir, el n´ umero de soluciones enteras positivas de x1 + x2 + . . . + x5 = 12, !

!

16 16 que es CR(5, 12) = = = 1820. 12 4 Ejemplo 90. ¿De cu´antas formas se pueden elegir 11 helados entre cinco sabores si queremos que haya al menos un helado de cada sabor? Empezamos sirviendo cinco helados, uno de cada sabor3 . Quedan por servir 6 helados con 5 sabores, lo cual equivale a encontrar las soluciones enteras no negativas de x1 + x2 + x3 + x4 + x5 = 6, 2

Pensemos en n = 3 y r = 5. La soluci´on 1+2+2 = 5 se corresponde con la combinaci´ on a1 a2 a2 a3 a3 y con la cadena 1 | 11 | 11. A su vez, la cadena 111 | 1 | 1 se corresponde con la soluci´on 3 + 1 + 1 = 5 y con la combinaci´on a1 a1 a1 a2 a3 . ¿Con qu´e cadenas se corresponden las combinaciones a1 a1 a1 a1 a1 y a2 a2 a3 a3 a3 ? 3 Es como introducir una bola en cada caja para que ninguna quede vac´ıa.

105

4.3. BINOMIOS Y MULTINOMIOS que son

!

!

10 10 CR(5, 6) = = = 210. 6 4 El siguiente cuadro resume las f´ormulas para las agrupaciones vistas r objetos entre n Sin repetici´on

Ordenadas n! V (n, r) = (n−r)!

Con repetici´on

V R(n, r) = nr

4.3.

No Ordenadas   n! C(n, r) = nr = r!(n−r)! CR(n, r) =





n+r−1 n−1

Binomios y Multinomios

Teorema 15. Binomio de Newton. Sean x, y dos variables y n un n´ unero natural, se tiene que n

(x + y) =

n X

k=0

!

!

n n k n−k X n n−k k x ·y = x ·y k k=0 k

Demostraci´on. (x + y)n = (x + y) · (x + y) · . n. . · (x + y)

Matemática Discreta. Área de Álgebra Universidade da Coruña

Para cada valor de k, 0 ≤ k ≤ n, el coeficiente de xk · y n−k coincide con el n´ umero de formas de seleccionar la variable x en k de los n factores (seleccionando la variable y en los n − k restantes) sin  importar el orden ni repetir factor. Esto es, puede realizarse de C(n, k) = nk formas. Por tanto n

(x + y) =

!

n X

n k n−k x ·y k

k=0

La segunda igualdad se tiene porque

  n k

=



n n−k



para todo k = 0, 1, . . . , n.

Corolario 2. n X

k=0 n X

!

n = 2n k k

(−1)

k=0

!

n =0 k

Demostraci´on. Basta tomar en el teorema anterior x = y = 1 en la primera igualdad y x = 1 y y = −1 en la segunda.

CAP´ITULO 4. COMBINATORIA

106

Ejemplo 91. Casos particulares son las f´ ormulas (x + y)2 = x2 + 2xy + y 2; (x + y)3 = x3 + 3x2 y + 3xy 2 + y 3; 7 X

7

(x + y) =

k=0

!

7 k 7−k x y = k

!

!

!

!

7 7 7 6 7 5 2 7 4 3 = x + x y+ xy + xy + 0 1 2 3 ! ! ! ! 7 2 5 7 7 7 7 3 4 6 xy + y = + xy + xy + 7 4 5 6 = x7 + 7x6 y + 21x5 y 2 + 35x4 y 3 + 35x3 y 4 + 21x2 y 5 + 7xy 6 + y 7 . Ejemplo 92. Halla el coeficiente de x9 y 3 en (2x − 3y)12 . ¿Cu´ al es la suma de todos los coeficientes? Seg´ un acabamos de ver (2x − 3y)

12

=

12 X i=0

!

12 (2x)i (−3y)12−i i

Matemática Discreta. Área de Álgebra Universidade da Coruña

Por lo tanto, el coeficiente que nos piden aparece en el sumando correspondiente a i = 9:   12 9

29 x9 (−3)3 y 3 = 220 · 512 · (−27) x9 y 3 = −3041280 x9y 3

Por otro lado, la suma de los coeficientes 12 X i=0

!

12 i 2 (−3)12−i i

se obtiene tomando x = y = 1 en (2x − 3y)12, es decir 12 X i=0

!

12 i 2 (−3)12−i = (−1)12 = 1. i

Teorema 16. Multinomio de Leibniz. Sean x1 , x2 ,. . . , xk variables y sea n un n´ umero natural. (x1 + x2 + . . . + xk )n =

X

P R(n; n1 , n2 , . . . , nk ) xn1 1 · xn2 2 · . . . · xnk k

n1 +...+nk =n

siendo n1 , n2 ,. . . , nk n´ umeros naturales.

´ ´ 4.4. PRINCIPIO DE INCLUSION-EXCLUSI ON

107

Demostraci´on. (x1 +x2 +. . .+xk )n = (x1 +x2 +. . .+xk )·(x1 +x2 +. . .+xk )· . n. . ·(x1 +x2 +. . .+xk ) El coeficiente de xn1 1 · xn2 2 · . . . · xnk k coincide con el n´ umero de formas de seleccionar en los n factores, n1 veces la variable x1 , n2 veces la variable x2 , y sucesivamente hasta nk veces la variable xk . Esto se puede realizar n! de P R(n; n1 , n2 , . . . , nk ) = formas, obteni´endose la expren1 ! · n2 ! · . . . · nk ! si´on. Ejemplo 93. (x + y + z)10 =

X

P R(10; r, s, t) xr y s z t =

r+s+t=10

10! r s t xy z r+s+t=10 r! s! t! X

Ejemplo 94. Halla el coeficiente de w 3 x2 yz 2 en (2w − x + 3y − 2z)8 . ¿Cu´ al es la suma de todos los coeficientes? Seg´ un acabamos de ver (2w − x + 3y − 2z)8 =

8! (2w)i(−x)j (3y)k (−2z)r i! j! k! r! i+j+k+r=8 X

Matemática Discreta. Área de Álgebra Universidade da Coruña

Por lo tanto, el coeficiente que nos piden aparece en el sumando correspondiente a i = 3, j = 2, k = 1, r = 2: 8! (2w)3(−x)2 (3y)1 (−2z)2 = 161280 w 3x2 yz 2 . 3! 2! 1! 2! Por otro lado, la suma de los coeficientes 8! 2i (−1)j 3k (−2)r i+j+k+r=8 i! j! k! r! X

se obtiene tomando w = x = y = z = 1 en (2w − x + 3y − 2z)8 , es decir 8! 2i (−1)j 3k (−2)r = (2 − 1 + 3 − 2)8 = 28 = 256. i! j! k! r! i+j+k+r=8

4.4.

X

Principio de inclusi´ on-exclusi´ on

En su forma m´as simple, el principio dice que si A y B son dos conjuntos finitos, entonces |A ∪ B| = |A| + |B| − |A ∩ B|.

CAP´ITULO 4. COMBINATORIA

108

En efecto, los elementos que pertenecen a ambos conjuntos se cuentan dos veces, una en el cardinal de A y otra en el cardinal de B. Para evitar esto se resta el n´ umero de elementos de A ∩ B. Para el caso de tres conjuntos A, B y C el principio es |A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B| + |B ∩ C| + |A ∩ C|) + |A ∩ B ∩ C|. Veamos la generalizaci´on de estas f´ormulas para obtener el cardinal de una uni´on finita de conjuntos. Sea S un conjunto finito y Pi , i = 1, 2, . . . , n, una colecci´on de propiedades sobre los elementos de S. Se definen los subconjuntos Si de S Si = {x ∈ S ; x verifica la propiedad Pi },

i = 1, 2, . . . , n

El conjunto n [

Si = {x ∈ S ; x verifica alguna propiedad Pi };

i=1

por otra parte, el conjunto n \

Si = {x ∈ S ; x no verifica ninguna propiedad Pi }

Matemática Discreta. Área de Álgebra Universidade da Coruña

i=1

siendo uno el complementario del otro:

n [

Si =

i=1

Teorema 17. n \

i=1

Si

n \

Si .

i=1

i)

= |S| − = |S| +

n X

i=1 n X

X

|Si | +

|Si ∩ Sj | + . . . + (−1)n |S1 ∩ . . . ∩ Sn | =

1≤i