Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

COMBINACIONES CON REPETICIÓN Ó • Tenemos k objetos idénticos para distribuir en n cajas distintas ¿de cuántas formas distintas se pueden introducir los k objetos en las n cajas, teniendo en cuenta que cada caja puede contener los k objetos? Elegimos k de las n cajas para colocar en ellas los objetos, pudiendo elegir la misma caja más de una vez.

42

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

• La alineación de las n cajas da lugar a n  1 tabiques de separación entre las cajas. ooo

oo

oooo

ooo

o

o

Hay que elegir la posición de k objetos (ceros) ó de (n  1) t bi tabiques ( (unos) ) de d entre t un total t t l de d (n ( 1) 1) + k elementos. l t CRn , k

 n 1  k   n 1  k      k   n 1 

(Jacob Bernouilli, 1700) 43

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

• Combinación con repetición es una na Selección no ordenada de k elementos escogidos entre n tipos diferentes de elementos, donde el mismo elemento se puede elegir hasta k veces. veces El número de selecciones no ordenadas es

CRn , k

 n 1 k   n 1 k      k   n 1  44

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplo En una pastelería hay 12 clases de pasteles. Un cliente desea comprar 24 pasteles, ¿de cuántas formas puede hacer su elección? ooo

Hay que elegir

oo

oooo

k = 24

ooo

o

o

pasteles de un conjunto con

n = 12 clases distintas de pasteles. 45

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

La alineación de las n = 12 cajas da lugar a n  1 = 11 tabiques de separación entre las cajas. Hay que elegir la posición de ó la posición de de entre un total de

CRn12,k 24

k = 24 pasteles n  1 = 11 tabiques

(n 1) + k = 35 elementos.

 35   35         24   11  46

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplo ¿Cuántos ¿C á t resultados lt d distintos di ti t saldrán ld á all lanzar l t tres d d dados iguales a la vez? Solución Hay que elegir tres resultados (k = 3) del conjunto A = { 1, 2, ... , 6 } con n = 6 cajas. Si xi = nnº de veces que sale i en los dados, dados entonces

 x1  x 2  ...  x6  3  0  xi  3 

8 CRn 6, k 3     56  3 47

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

• Si tenemos k objetos idénticos para distribuir en n cajas distintas, teniendo en cuenta que cada caja puede contener k objetos, se puede considerar que elegimos xi objetos de tipo i para alguna nupla

 x 1 , , x n  con x i  0 y  x i  k i 1 n

• Combinación con repetición de k objetos elegidos entre n es una solución entera no negativa de la ecuación

 x1    x n  k   0  xi  k

CRn,k

n 1 k  n 1 k         k   n 1  48

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplos 1) El número de soluciones enteras no negativas de la ecuación  x1  x 2  x3  x 4  x5  30  0  xi 

es

CRn 5,k 30

 34      30 

2) ¿De cuántas formas se pueden seleccionar 8 piezas de fruta de una cesta que contiene i manzanas, naranjas j y peras sii ell orden d en que se seleccionan las piezas no se tiene en cuenta?  x1  x 2  x3  8   0  xi  8

tiene

10  CRn 3,k 8     45 8

soluciones 49

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

• Una U solución l ió entera t positiva iti de d la l ecuación ió x1    xn  k es una combinación con repetición de k objetos elegidos entre n tipos de objetos de modo que se elige, al menos, un objeto de cada tipo 1º  se elige un objeto de cada tipo n, de una única manera. 2º  se eligen g k  n objetos j de los n tipos, p , de CRn, k  n

 n 1 k  n   k 1      k  n  k  n

maneras distintas. di ti t

50

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplos 1) El número de soluciones enteras positivas de la ecuación  x1  x 2  x3  x 4  x5  30  1  xi 

es

 29  CRn 5,k 30 5     25 

2) ¿De cuántas formas se pueden repartir 15 caramelos idénticos entre 4 niños, si cada niño recibe al menos un caramelo?  x1  x 2  x 3  x 4  15  1  xi 

CRn  4,k 15 4

14      11  51

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

PERMUTACIONES CON REPETICIÓN • Tenemos n objetos de m tipos distintos, con ki objetos idénticos de cada tipo i,  i  1, , m ,

k1    k m  n para distribuir di t ib i en n cajas j distintas, di ti t ¿de cuántas formas distintas se pueden introducir los n objetos en las n cajas, teniendo en cuenta que cada caja contiene un único objeto? 52

Departamento de Matemática Aplicada. ETSIInf. UPM.

• Permutación con repetición

Victoria Zarzosa Rodríguez

es una

selección ordenada

de n objetos de m tipos distintos, con ki objetos idénticos d tipo de i i, i  i  1, 1 , m y con

k1    k m  n

Ell nºº de d selecciones l i ordenadas d d distintas di i es PR nk1km

 n   n  k1   n  k1  k2   n  k1    k m1          k3 km  k1   k2     

PR nk1km

 n  n!     k1!  k m !  k1  k m 

ll llamamos a esta expresión ió número ú multinómico. li ó i 53

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplos 1) ¿Cuántas palabras distintas se pueden formar con todas las letras de ABRACADABRA?

2) ¿Cuántas C á t sucesiones i d longitud de l it d 15 con las l letras l t { a, b, c, d, e } se ppueden formar, de modo qque haya y 7 a, 3 b, 2 c, 2 d y 1 e? 54

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

3) Un niño reparte 45 cromos entre 3 amigos, regalando 10 cromos a cada amigo, ¿de cuántas formas puede hacerlo?

4) ¿De cuántas formas se pueden distribuir a cuatro jugadores manos de 5 cartas utilizando una baraja de 52 cartas?

55

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Soluciones 1)) 11! 5, 2, 2,1,1 11  6   4  2 1           PR 11            5   2   2  1 1 5! 2! 2! 1!1! 2)

3) 4)

PR 157,3, 2,2,1

15     7

10,10,10,15 PR 45

5,5,5,5,32 PR 52

 8   5  3  1 15 !          3   2  2  1 7! 3! 2! 2!1!

 45   35   25  45 !          10   10   10  10! 10! 10! 15!

 52   47   42  37  52 !           5   5   5  5  5! 5! 5! 5! 32! 56

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

PRINCIPIO DE LA CRIBA (ó de inclusión-exclusión) • Si A y B son conjuntos finitos, no vacíos, entonces card ( A  B ) = card ( A )  card ( B )  card ( A  B )

Ejemplos 1) Hallar las permutaciones de {1, 2, ..., 9} que empiezan por 1 ó que terminan en 9.

57

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

2) En una encuesta realizada a un conjunto de 100 personas se obtienen bi l siguientes los i i resultados: l d • 25 personas van al cine y al teatro • 20 personas no van al cine ni al teatro y • van al cine el doble de personas que al teatro. Averiguar el número de personas que van sólo al cine y el número de personas que van sólo al teatro. 58

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Soluciones 1)

U = { permutaciones de {1, 2, ..., 9} } p de U qque empiezan p ppor 1 } A = { permutaciones B = { permutaciones de U que terminan por 9 } card A = 8 !

card B = 8 !

A  B = { permutaciones empiezan por 1 y terminan por 9 } card ( A  B ) = 7 ! card ( A  B ) = card A  card B  card ( A  B ) = 15.7 !

59

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

2) Sean U = { personas } A = {personas { van all teatro} t t }

B = {personas { van all cine} i }

A  B = {personas que van al cine y al teatro} entonces card U = 100 y se verifica cardd B = 2 card dA

card d ( A  B ) = 25 2

card ( A  B ) = card U  card (A  B )´ = card U  card ( A´  B´ ) = 80 card A  card B = card ( A  B ) + card ( A  B ) = 105. Por tanto,, card A = 35 , card B = 70 60

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

PRINCIPIO DE LA CRIBA (ó de inclusión-exclusión) • Si A , B y C son conjuntos finitos, no vacíos, entonces card (A  B  C) = = card (A)  card (B)  card (C)   card (A  B)  card (A  C)  card (B  C) + + card (A  B  C)

61

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Ejemplos

1) En el conjunto de los números naturales menores o iguales que 500, hallar cuántos números no son múltiplos de 2, ni de 3, 3 ni de 5. 5

2) Hallar las permutaciones de {1, 2, ..., 9} que contengan a una de las sucesiones 123 123, 456 456, 789 789.

62

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Soluciones 1) Sean N500 =  n  , n  500  A =  n 500 / n es múltiplo de 2   card A = 250 B =  n 500 / n es múltiplo de 3   card B = 166 C =  n 500 / n es múltiplo de 5   card C = 100 A  B =  n 500 / n es múltiplo de 2 y de 3  A  C =  n 500 / n es múltiplo p de 2 y de 5  B  C =  n 500 / n es múltiplo de 3 y de 5  A  B  C =  n 500 / n es múltiplo p de 2 , de 3 y de 5  card ( A  B ) = 83, card ( A  C ) = 50, card ( B  C ) = 33 card (A  B  C) = 16 card (A  B  C) = 366 Por tanto, card ((A´  B´  C´)) = card ((A  B  C)´ ) = card N500  card (A  B  C) = 134 63

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

64

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

2) A =  permutaciones i que contienen i 123  B =  permutaciones que contienen 456  C =  permutaciones que contienen 789  card A = card B = card C = 7. 6 ! = 7 ! A  B =  permutaciones que contienen 123 y 456  A  C =  permutaciones que contienen 123 y 789  B  C =  permutaciones t i que contienen ti 456 y 789  card ( A  B ) = card ( A  C ) = card ( B  C ) = 5 ! A  B  C =  permutaciones que contienen 123, 456 y 789  card (A  B  C) = 3 ! Entonces, card (A  B  C) = 3. 7 !  3. 5 ! + 3 ! = 14766 65

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

COMBINACIONES CON REPETICIÓN LIMITADA Ejemplos 1) ¿Cuántos n  , n < 104 , cumplen que la suma de sus cifras es 25?

1  n  x1 x 2 x 3 x 4  9999 x1  x 2  x 3  x 4  25 0  xi  9

2) ¿Cuántas soluciones enteras tiene la ecuación x1 + x2 + x3 = 17 3  x2  6,, 4  x3  7 ? 2  x1  5,, 66

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

3) Al lanzar tres dados distintos a la vez, ¿en cuántos resultados posibles la suma es 10? 4) Un niño dispone de un juego de 30 palitos y los dispone en forma de escalera con 4 tramos, según indica la figura.

a) ¿Cuántas escaleras diferentes puede construir? b) ¿Y si en cada uno de los tres primeros tramos debe haber a lo sumo 7 palitos? 67

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Soluciones 1) Sean X = soluciones no negativas de x1  x2  x3  x4  25  Ai = soluciones de X con xi  10. Entonces 4   card  X   Ai   card X   1   2   3   4     i 1   4  28  18   4  8   CR n 4,k 25  4CR n 4,k 15   CR n 4,k 5     4      2  3   3   2  3 

card X = CRn=4,k=25 1 = 4 card Ai = 4 CRn=4,k=15  4 4  2 =   card (Ai  Aj) =   CRn=4,k=5  2  2

3 = 4 = 0

68

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

y1  x1  2, y2  x2  3, y3  x3  4, 2) S Se ddefinen fi las l variables i bl entonces la ecuación se transforma en  y  y  y  8 1 2 3  0  yi  3 Sean X = soluciones  no negativas de y1  y2  y3  8  Ai = soluciones de X con yi  4 . 3   card  X   Ai   card X  1   2   3   i 1    3

 CR n 3,k 8  3CR n 3,k 4   CR n 3,k 0 2

card X = CRn=3,k=8 1 = 3 card Ai = 3 CRn=3,k=4  3  3   2 =  2  card (Ai  Aj) =  2  CRn=3,k=0 3 = 0

10   6   3  2      3       2   2   2  2 

69

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

3) Hay que elegir tres resultados, cuya suma sea k = 10 del conjunto A = { 1, 1 2, 2 3 } con n = 3 cajas, cajas al menos un elemento de cada caja. Sean

xi 

número que aparece en el dado i,

entonces hay que resolver la ecuación

 x1  x2  x3  10  x1  x2  x3  7    1  xi  6  0  xi  5 70

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

Sean X = soluciones no negativas de x1  x2  x3  7  Ai = soluciones de X con xi  6 . 3   card  X   Ai   card X  1   2   3   i 1  

 CRn3,k 7  3CRn3,k 1

 9   3     3   2  2

card X = CRn=3,k=7 1 = 3 cardd Ai = 3 CRn=3,k=1 2 = 3 = 0 71

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

4) a) Sea xi = nº de palitos que coloca en el tramo de escalera i-ésimo, entonces el nº de escaleras diferentes que puede construir es el nº de soluciones enteras de la ecuación  x1  x2  x3  x4  30  1  xi 

  x1  x2  x3  x4  26 

0  xi

 29 

esto es,, CRn4,k 26     26    72

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

b)) Si en cada uno de los tres pprimeros tramos debe haber a lo sumo 7 palitos, entonces el nº de escaleras diferentes es el nº de soluciones enteras de la ecuación  x1  x2  x3  x4  30  1  x1,x2 ,x3  7 , 1  x4



 x1  x2  x3  x4  26  0  x1,x2 ,x3  6, 0  x4

Si Ai = {soluciones de x1 + x2 + x3 + x4 = 26 / xi  7}, i=1, 2, 3 entonces la solución es

73