Análisis Combinatorio

Fidel Vera Obeso

OBJETIVO N° 01 INTERPRETAR EL PRINCIPIO FUNDAMENTAL DE CONTEO Y APLICARLO EN LA SOLUCION DE PROBLEMAS.

ACTIVIDAD N° 01 ANALICE LA SIGUIENTE INFORMACION EJEMPLOS DESARROLLADOS SOBRE EL

3.1.

Y

LOS

PRINCIPIO FUNDAMENTAL DE CONTEO. Examinemos el siguiente problema. Hay tres caminos-rutas, (1), (2) y (3), que unen la Ciudad Círculo y la Población Triángulo, y hay dos caminos-rutas, (4) y (5), que unen la Población Triángulo y Villa Cuadrada (Fig. 1-1). (3)

(5)

(2) (1)

(4)

Ciudad

Población

Villa

Círculo

Triángulo

Cuadrada

Fig. 1-1. Rutas que unen la ciudad círculo, la población triángulo y villa cuadrada. Ahora, si deseamos viajar desde Ciudad Círculo hasta la Población Triángulo, y después hacia Villa Cuadrada, podemos escoger una de varias maneras para llegar allá. Según la Fig. 1-1, vemos que podemos viajar desde Ciudad Círculo hasta la Población Triángulo por una cualquiera de tres rutas, y después, para cada una de estas rutas tenemos dos elecciones para viajar hacia Villa Cuadrada. Por tanto, tenemos 3x2, o sea, 6 posibles maneras en total. Una de las seis maneras consiste en tomar la ruta (1) y después la ruta (4). ¿Cuáles son las otras cinco maneras? Supóngase que hubiera cuatro caminos uniendo Ciudad Círculo y Población Triángulo, y seis caminos uniendo Población Triángulo y Villa Cuadrada, ¿Cuántas formas diferentes habría para llegar desde Ciudad Círculo Universidad Nacional del Santa

1

Análisis Combinatorio

Fidel Vera Obeso

pasando por la Población Triángulo? El principio general que se involucra aquí se llama Principio Fundamental de Conteo y se establece como sigue:

Principio Fundamental de Conteo. Si un primer suceso puede ocurrir de k1 maneras diferentes, y después de ocurrido de una de esas maneras, un segundo suceso puede ocurrir de k2 maneras diferentes, y después de ocurrido de una de esas maneras, un tercer suceso puede ocurrir de k3 maneras diferentes, y así sucesivamente para n sucesos, entonces, colectivamente, los n sucesos pueden ocurrir de k1.k2.k3...kn maneras diferentes.

Ejemplo 1. ¿De cuántas maneras pueden sentarse 6 personas en una fila de 6 asientos: (a) si 2 de ellas insisten en sentarse uno junto a otro; (b) si las mismas 2 no aceptan sentarse uno junto al otro? Solución. Indiquemos por medio de marcas la posición de los asientos que van a ser ocupados por las seis personas. (a)

Si dos personas insisten en sentarse uno junto al otro, dos de los 6 asientos van a ser ocupados por estas dos personas. Supongamos que, de izquierda a derecha, los dos primeros asientos son ocupados por estas dos personas, entonces el tercer asiento puede ser ocupado por cualquiera de las cuatro personas restantes, y después de ocupado, el cuarto asiento puede ser ocupado por cualquiera de las tres personas restantes, y así sucesivamente. Observe que después que los primeros cinco asientos han sido ocupados, solamente queda una persona para el último asiento. El número de posibilidades para ocupar cada uno de los seis asientos se indica como sigue: 1

1

Universidad Nacional del Santa

1

4

3

2

2

1

Análisis Combinatorio

Fidel Vera Obeso

Que, aplicando el Principio Fundamental de Conteo, el número de posibilidades se da por 1.1.4.3.2.1 = 4! = 24 Ahora, si el segundo y tercer asientos son ocupados por aquellas dos personas, entonces el primer asiento puede ser ocupado por cualquiera de las cuatro personas restantes, y después de ocupado, el cuarto asiento puede ser ocupado por cualquiera de las tres personas restantes, y así sucesivamente. En este caso, el número de posibilidades es: 2 4

1

1

3

2

1

4x1x1x3x2x1 = 4! = 24 A continuación se presenta los otros casos de las dos personas que insisten en sentarse uno junto al otro. 3

4

3

1

1

2

1

1

1

4

4

3

2

1

5

4

3

2

1

1

1

De lo cual se concluye que el número de maneras que pueden sentarse seis personas en una fila de seis asientos si dos de ellas insisten en sentarse uno junto al otro, es:

(b)

5x4! = 5! = 5x4x3x2x1 = 120 Si las mismas dos personas no aceptan sentarse uno junto al otro, dos de los seis asientos van a ser ocupados por estas dos personas.

Universidad Nacional del Santa

3

Análisis Combinatorio

Fidel Vera Obeso

Supongamos que, de izquierda a derecha, el primer y tercer asiento son ocupados por estas dos personas, entonces el segundo asiento puede ser ocupado por cualquiera de las cuatro personas restantes, y después de ocupado, el cuarto asiento puede ser ocupado por cualquiera de las tres personas restantes, y así sucesivamente. Observe que después que los primeros cinco asientos han sido ocupados, solamente queda una persona para el último asiento. El número de posibilidades para ocupar cada uno de los asientos se indica como sigue: 1

1

4

1

3

2

1

Aplicando el Principio Fundamental de Conteo el número de posibilidades es: 1.4.1.3.2.1 = 4! = 24 Los otros casos de las dos personas que no aceptan sentarse uno junto al otro, son: 2

3

5

6

8

11 15

17

18

7

9

12

14

4

10

13 16

19

20

Por lo tanto, el número de maneras en que pueden sentarse seis personas en una fila de seis asientos, si dos personas no aceptan sentarse uno junto al otro, es: 20.4! = 20.24 = 480 Ejemplo 2. ¿De cuántas maneras pueden sentarse 4 hombres y 5 mujeres en una fila de 9 sillas, si los hombres y mujeres tienen que alternarse? Universidad Nacional del Santa

4

Análisis Combinatorio

Fidel Vera Obeso

Solución. Si el primer asiento, de izquierda a derecha, es ocupado por una de las cinco mujeres, entonces el tercer asiento puede ser ocupado por cualquiera de las cuatro mujeres restantes y, después de ocupado, el quinto asiento puede ser ocupado por cualquiera de las tres mujeres restantes, y así sucesivamente. Observe que después que el primero, tercero, quinto y séptimo asientos han sido ocupados, solamente queda una mujer para el noveno y último asiento. El número de posibilidades para ocupar cada uno de estos cinco asientos impares por las mujeres es 5! = 120. Luego, si el segundo asiento es ocupado por uno de los cuatro hombres, entonces el cuarto asiento puede ser ocupado por cualquiera de los tres hombres restantes y, después de ser ocupado, el octavo asiento será ocupado por el último hombre restante. El número de posibilidades para ocupar cada uno de estos cuatro asientos pares por los hombres es 4! = 24. El número de ambas posibilidades para ocupar cada uno de los nueve asientos por 4 hombres y 5 mujeres en forma alternada se indica como sigue:

Universidad Nacional del Santa

5

Análisis Combinatorio

Fidel Vera Obeso Hombres

5

4 4

3 3

2

1

2

1

Mujeres Aplicando el principio fundamental de conteo el número de maneras que pueden sentarse cuatro hombres y cinco mujeres en una fila de nueve sillas en forma alternada, es: 5! 4! = 120.34 = 2880

Ejemplo 3. a) b) c)

¿Cuántos números se pueden formar con algunas de las cifras 1, 3, 4, 7, 8, si un número no puede tener dos cifras repetidas? ¿Cuántos de éstos números serán pares? ¿Cuántos serán mayores que 350?

Solución. a) Debemos considerar los números de uno, dos, tres, cuatro y cinco cifras. El número total de posibilidades lo presentamos en el siguiente esquema:

5 5 4 --- --5 4 3 --- --- --5 4 3 2 --- --- --- --5 4 3 2 1 --- --- --- --- ---

Universidad Nacional del Santa

6

=

5

=

20

=

60

=

120

=

120 ----325

Análisis Combinatorio b)

Fidel Vera Obeso

Hay que tener presente que la última posición o cifra de cada número puede ser ocupado solamente por dos números: el 4 y el 8. El número total de posibilidades lo presentamos en el siguiente esquema: 2 4 2 --- --4 3 2 --- --- --4 3 2 2 --- --- --- --4 3 2 1 2 --- --- --- --- ---

c)

=

2

=

8

=

24

=

48

=

48 ----130

Los números mayores que 350 son de tres, cuatro y cinco cifras. Para los números de cuatro y cinco cifras no hay ningún inconveniente; pero para los números de tres cifras hay que considerar aquellos cuya cifra de las centenas es 3 y aquellos cuya cifra de las decenas son 4, 7 y 8. Hay que tener presente que cuando la cifra de las centenas es 3, la cifra de las decenas puede ser ocupado solamente por los números 7 y 8, quedando tres números para ocupar la cifra de las unidades. El número total de posibilidades lo presentamos en el siguiente esquema: [3] [7,8] [4,7,8] 1 2 3 + 3 4 3 --- --- --- --- --- --5 4 3 2 --- --- --- --5 4 3 2 1 --- --- --- --- ---

=

42

=

120

=

120 ----280

Ejemplo 4. ¿Cuántos enteros positivos pares de tres dígitos diferentes cada uno son menores que 400? Solución. Se utilizará los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. La cifra de las centenas de los números menores que 400 puede ser ocupado solamente por los dígitos 1, 2 ó 3. Ya que éstos números son pares hay que tener presente que cuando la cifra de las centenas es ocupado por el 2, la cifra de las unidades puede ser ocupado por los dígitos 0, 2, 4, 6 u 8, quedando ocho dígitos para ocupar la cifra de las decenas. Universidad Nacional del Santa

7

Análisis Combinatorio

Fidel Vera Obeso

Cuando la cifra de las centenas es ocupado por el 1 ó el 3, la cifra de las unidades puede ser ocupado por los dígitos 0, 2, 4, 6 u 8, quedando ocho dígitos para ocupar la cifra de las decenas. El número total de posibilidades lo presentamos en el siguiente esquema:

[2]

[0,4,6,8]

1 8 4 --- --- ---

[1,3]

+

[0,2,4,6,8]

2 8 5 --- --- ---

Universidad Nacional del Santa

=

8

112

Análisis Combinatorio

Fidel Vera Obeso

ACTIVIDAD N° 02

RESUELVA A CONTINUACIÓN LOS SIGUIENTES

PROBLEMAS SOBRE EL PRINCIPIO FUNDAMENTAL DE CONTEO. 1.

¿De cuántas maneras pueden sentarse 7 personas en una fila de 7 asientos: a) b)

si 2 de ellas insisten en sentarse uno junto a otro; si las mismas 2 personas no aceptan sentarse uno junto al otro?

2.

¿De cuántas maneras pueden sentarse 3 hombres y 4 mujeres en una fila de 7 sillas si los hombres y mujeres tienen que alternarse?

3.

Obtener el número de palabras de cuatro letras (no necesariamente pronunciables) que pueden formarse con 7 consonantes diferentes y 3 vocales diferentes, si las consonantes y vocales deben ir alternadas y no se permite la repetición.

4.

Resolver el problema 3 si se permite la repetición.

5.

a) b) c)

¿Cuántos números se pueden formar con algunas de la cifras 2, 4, 5, 8 y 9, si un número no puede tener dos cifras repetidas? ¿Cuántos de éstos números serán impares? ¿Cuántos serán mayores que 460?

6.

¿Cuántos enteros positivos impares de tres dígitos diferentes cada uno son menores que 500?

7.

¿De cuántas maneras diferentes pueden sentarse 5 personas en una fila de 8 sillas?

8.

Resolver el problema 7 si las 5 personas deben sentarse en sillas consecutivas?

9.

¿Cuántos enteros positivos impares de 4 dígitos diferentes cada uno son mayores que 3,540?

Universidad Nacional del Santa

9

Análisis Combinatorio

OBJETIVO N°Fidel 02 Vera Obeso CALCULAR EL NÚMERO DE PERMUTACIONES LINEALES Y CURRICULARES DE n ELEMENTOS DE UN CONJUNTO TOMADO DE r EN r

ACTIVIDAD N° 01 INTERPRETE LOS TEOREMAS Y EJEMPLOS DESARROLLADO SOBRE

3.2.

PERMUTACIONES

LINEALES.

PERMUTACIONES

ANALICE

LINEALES

LOS

CON

REPETICIÓN. PERMUTACIONES LINEALES. Cada uno de los distintos arreglos lineales que pueden hacerse con todos los n elementos de un conjunto en un orden definido se llama PERMUTACIÓN LINEAL. EL número total de permutaciones lineales de n elementos tomados de n en n está dado por P(n,n) = Pn = n(n-1)(n-2)...3.2.1 = n! donde n! es el factorial de n definido como el producto de todos los números enteros positivos consecutivos de 1 a n.

Si se trata de formar los distintos arreglos lineales tomando solamente r de los n elementos, entonces el número total de permutaciones lineales de n elementos tomados de r en r está dado por la fórmula P(n, r) = P nr = n(n - 1)(n - 2)...(n - r + 1) =

n! (n - r)!

,

r ≤ n.

En efecto, el valor de P(n,r) es igual al número total de maneras que puede llenarse r lugares con n elementos diferentes, ya que en este punto todos los n elementos están disponibles. El segundo lugar puede llenarse de n-1 maneras diferentes con los n-1 elementos restantes. Análogamente, el tercer lugar puede llenarse de n-2 maneras diferentes, y así sucesivamente. Para visualizar mejor este proceso lo esquematizamos del modo siguiente: LUGARES A LLENARSE 1 2 3 4 Universidad Nacional del Santa

NÚMERO DE MANERAS n n-(2-1) = n-1 n-(3-1) = n-2 n-(4-1) = n-3 10

Análisis Combinatorio

Fidel Vera Obeso

. . . r -1 r

. . . n-[(r-1)-1]=n-r+2 n-(r-1) = n-r+1

r+1 r+2 . . . n-1 n

n-[(r+1)-1] = n-r n-[(r+2)-1] = n-r-1 . . . n-[(n-1)-1] = 2 n-(n-1) = 1

Se observa que el lugar r puede llenarse de n-(r-1) = n-r+1 maneras diferentes. Entonces por el Principio Fundamental de Conteo el valor de P(n,r) = n (n-1) (n-2) ... (n-r+1) Ahora, si multiplicamos y dividimos P(n,r) por (n-r)(n-r-1) ...2x1, se verifica que P(n,r)=

n(n - 1)(n- 2)...(n- r + 1)(n- r)(n- r - 1)...2 x 1 (n - r)(n - r - 1)...2 x 1

P(n, r) =

n! , (n - r)!

r ≤ n.

Ejemplo 1. Calcular: a) P(10,4) P(10,4) =

Universidad Nacional del Santa

10! 10! 10 x 9 x 8 x 7 x 6! = = = 5,040 (10 - 4)! 6! 6!

11

Análisis Combinatorio b)

Fidel Vera Obeso

P(7,4) / P(5,4) P(7,4) =

7! 7! 7 x 6 x 5 x 4 x 3! = = = 840 (7 - 4)! 3! 3!

P(5,4) =

5! 5! = = 5! = 5 x 4 x 3 x 2 x 1 = 120 (5 - 4)! 1!

Entonces: P(7,4) / p(5,4) = 840 / 120 = 7

Ejemplo 2. a)

Si P(n,5) = 24 P(n,2), hallar n.

P(n,5) = 24 P(n,2) n! 24 n! ------- = -------(n-5)! (n-2)! n (n-1) (n-2) (n-3) (n-4) (n-5)! n (n-1) (n-2)! ---------------------------------- = 24 -------------(n-5)! (n-2)! (n-2) (n-3) (n-4) = 24 (n²-5n+6) (n-4) = 24 n3 - 9n2 + 26n - 48 = 0 1 │ -9 26 -48 │ 6 │ 6 -18 48 ──┼─────────────────── 1 │ -3 8 0 (n - 6) (n2 - 3n + 8) = 0 D = 32 - 4 (1) (8) = 9 No tiene solución en R, por lo tanto: n = 6 b)

Si 12 P(7,r) = 5 P(9,r), hallar r. 7! 9! 12 -------- = 5 -------(7-r)! (9-r)!

Universidad Nacional del Santa

12

Análisis Combinatorio

Fidel Vera Obeso

7! 9 x 8 x 7! 12 -------- = 5 -----------------------(7-r)! (9-r) (9-r-1) (9-r-2)! 12 x (9-r) x (8-r) = 5 x 72 72 - 17r + r2 = 30

r2 - 17r + 42 = 0 r

-14

r

-3

(r - 3) (r - 14) = 0 r=3 y

r = 14

r = 14 se descarta, ya que r ≤ 9 Por tanto, r = 3 Ejemplo 3. Demostrar que P(n,r) - P(n,r-1) = (n-r) P(n,r-1) Solución. Partimos del miembro de la derecha y debemos llegar al miembro de la izquierda. En efecto: n! (n-r) P(n,r-1) = (n-r) -----------[n-(r-1)]! [(n-r+1)-1] n! = ---------------(n-r+1)! (n-r+1) n! n! = ------------ - ---------(n-r+1)! (n-r+1)! (n-r+1) n! n! = ---------------- - ---------(n-r+1) (n-r)! (n-r+1)! Universidad Nacional del Santa

13

Análisis Combinatorio

Fidel Vera Obeso

n! n! = -------- - -----------(n-r)! [n-(r-1)]! = P(n,r) - P(n,r-1).

LQQD

Ejemplo 4. A partir de los dígitos 1, 2, 3, 4 5: a) ¿Cuántos números naturales de tres dígitos pueden formarse si ningún número puede tener un dígito repetido? b) ¿Cuántos números naturales de uno o más dígitos pueden formarse si ningún número puede tener un dígito repetido? Solución. El total de números de tres dígitos es igual al número de permutaciones que pueden hacerse con los cinco dígitos tomados de tres en tres, es decir: P(5,3) =

b)

5! 5! 5 x 4 x 3 x 2! = = = 60 (5 - 3)! 2! 2!

El total será la suma de los números de uno, dos, tres, cuatro y cinco dígitos, es decir: P(5,1) + P(5,2) + P(5,3) + P(5,4) + P(5,5) 5 + 20 + 60 + 120 + 120 = 325 Hay que tener presente que al calcular: P(5,5) =

5! 5! 5! = = = 5! = 120 (5 - 5)! 0! 1!

0! = 1 Ejemplo 5. Un estante tiene espacio para 6 libros. Disponemos de 5 libros diferentes de inglés y 6 libros diferentes de francés. ¿De cuántas maneras podemos colocar en el estante 3 libros en inglés y 3 libros en francés, si los libros escritos en la misma lengua tienen que estar juntos? Solución. De izquierda a derecha los libros de inglés pueden colocarse de P(5,3) maneras y los de Universidad Nacional del Santa

14

Análisis Combinatorio

Fidel Vera Obeso

francés de P(6,3) maneras. Luego, por el Principio Fundamental de Conteo, los libros tanto de inglés como de francés pueden colocarse de 2 P(5,3) P(6,3) = 14,400 maneras. Aquí hemos considerado la otra posibilidad de derecha a izquierda. Esquemáticamente: I=5 F=6 F

2

I

I

1

F

Ejemplo 6. ¿Cuántos números de 5 cifras distintas pueden formarse con las cifras 3, 4, 5, 6 y 7, si a)

los números 4 y 5 tienen que estar juntos?

Solución. Lo calculamos utilizando el siguiente esquema: 1

1

(1)

3

(2)

2

(3)

1

(4)

Es evidente que el total de números de 5 cifras está dado por 4 P(2,2) P(3,3) = 4 x 2 x 3! = 48 Ya que los números 4 y 5 ocupan dos espacios de P(2,2) maneras quedando los números 3, 6 y 7 los cuales ocupan los tres espacios restantes de P(3,3) maneras para cada una de las cuatro posibilidades.

b)

Los números 4 y 5 tienen que estar separados?

Solución. Las posibilidades las presentamos a continuación: 1

2

4 Universidad Nacional del Santa

15

22

3

5

Análisis Combinatorio

Fidel Vera Obeso

6

7

8 10

9 11

12

El número total de números de 5 cifras está dado por 12 P(2,2) P(3,3) = 144.

Ejemplo 7. a)

¿De cuántas maneras pueden sentarse 7 personas en una fila de 7 sillas, si hay 4 personas que tienen que estar uno al lado del otro?

16 Universidad Nacional del Santa

Análisis Combinatorio

Fidel Vera Obeso

Solución. Esquema de posibilidades: (1)

(1) (2) (3) (4) El total de maneras que pueden sentarse 7 personas está dado por 4 P(4,4) P(3,3) = 576

b)

Resolver la parte (a) si se considera una fila de 8 sillas. Solución. Esquema de posibilidades: (1)

(1) (2) (3) (4) (5)

Total de maneras: ** 5 P(4,4) P(4,3) = 2880 **

Aquí cabe aclarar que el número de maneras que pueden sentarse 3 personas en una fila de 4 sillas es igual al número de grupos de 3 sillas que pueden formarse con 4 de ellos

PERMUTACIONES LINEALES CON REPETICIÓN. El número de permutaciones lineales distintas que se pueden formar con los n elementos de un conjunto, en los que en cada arreglo cada elemento puede aparecer n1, n2,..., nk veces en un orden definido, está dado por: Universidad Nacional del Santa

17

Análisis Combinatorio

Fidel Vera Obeso

PR(n, n1 , n 2 ,K , n k ) =

n! n1! n2! Kn k !

donde: k n = Σ ni = n1 + n2 + ... + nk i=1

Ejemplo 8. Calcular el número de permutaciones diferentes que pueden formarse con las letras de la palabra AUTODIDACTA, tomadas todas a la vez. Solución. La palabra contiene 11 letras, de las cuales 3 son A, 2 son T, 2 son D y el resto diferentes. Por tanto, el número de permutaciones diferentes es: 11! PR(11;3,2,2,1,1,1,1) = ---------------------3! 2! 2! 1! 1! 1! 11x10x9x8x7x6x5x4 = ------------------4 = 1'663,200 Ejemplo 9. ¿Cuántos numerales distintos de cinco dígitos pueden formarse en cada caso? a) 3,4 y 7 pueden utilizarse cada uno una vez; 5 puede utilizarse dos veces. b) 6, 7 y 8 pueden utilizarse cada uno una vez, 9 puede utilizarse dos veces.

Universidad Nacional del Santa

18

Análisis Combinatorio c) d)

Fidel Vera Obeso

3 puede utilizarse 3 veces; 5 puede utilizarse 2 veces. 2 y 3 pueden utilizarse cada uno dos veces; 4 pueden utilizarse una sola vez.

Solución.

3.3.

a)

5! PR(5;2,1,1,1) = ------------------ = 5x4x3 = 60 2! 1! 1! 1!

b)

PR(5;2,1,1,1) = 60

c)

5! 5x4 PR(5;3,2) = ------- = -------- = 10 3! 2! 2

d)

5! 5x4x3 PR(5;2,2,1) = ----------- = ----------- = 30 2! 2! 1! 2

PERMUTACIONES CIRCULARES. Cada uno de los distintos arreglos que se pueden hacer alrededor de un círculo con los n elementos de un conjunto dado, se llama permutación circular. ¿De cuántas maneras diferentes pueden colocarse n elementos alrededor de un círculo? Con los elementos del conjunto {x,y,z} pueden formarse P(3,3)=3! = 6 permutaciones lineales diferentes. Pero solamente pueden formarse 2 permutaciones circulares diferentes. ¿Cuál es la razón? Para responder a la pregunta notemos que los arreglos y

x

z

y

x

z

z

y

son los mismos. ¿Por qué? Análogamente los arreglos x

y

y

z

Universidad Nacional del Santa

z

x

19

x z

x

y

Análisis Combinatorio

Fidel Vera Obeso

son también los mismos. Observe que, al formar una permutación circular, es indiferente dónde localizamos el primer objeto sobre el círculo. Después de fijar la posición de uno de los n elementos de un conjunto, se procede a calcular el número de permutaciones de los n-1 elementos restantes como si estuvieran en una línea recta. Hecho que nos permite formular lo siguiente: El número de permutaciones circulares diferentes que se pueden formar con los n elementos de un conjunto es igual a (n-1)!. Ejemplo 10. Un grupo formado por 4 muchachas y 4 muchachos van a sentarse de modo que queden alternados. Calcular de cuántas maneras pueden hacerlo si: a) se sientan en línea recta; b) se sientan alrededor de una mesa circular. Solución. a)

Podemos considerar que las muchachas se sientan en los lugares con número impar y los muchachos en los lugares con número par; esto puede hacerse de 4!x4! maneras diferentes. Un número igual de arreglos diferentes puede obtenerse sentando a los muchachos en los lugares con número impar y a las muchachas en los lugares con número par. Por tanto, el número total de maneras diferentes es igual a 2x4!x4! = 1,152.

b)

Podemos sentar primeramente a las muchachas alrededor de la mesa en 3! maneras. Entonces quedan 4 lugares alternados para sentar a los cuatro muchachos; esto puede hacerse en 4! maneras. Por tanto, el número total de maneras diferentes es igual a 3!4! = 144.

Universidad Nacional del Santa

20

Análisis Combinatorio

Fidel Vera Obeso

ACTIVIDAD N° 02

RESUELVA A CONTINUACIÓN LOS SIGUIENTES

PROBLEMAS SOBRE PERMUTACIONES LINEALES Y CIRCULARES. 1.

Calcular a) b)

P(8,2) + P(9,3) P(6,1) - P(2,1)

2.

a) b)

Si P(n,5) = 42 P(n,3), hallar n. Si 2 P(6,r) = 3 P(5,r), hallar r.

3.

Demostrar que P(n,4) - P(n,3) = (n-4) P(n,3)

4.

Resolver para n, P(n,r) = k P(n-1,r-1).

5.

A partir de los dígitos 5, 6, 7, 8 y 9: a) b)

¿Cuántos números enteros de cuatro dígitos pueden formarse si ningún número puede tener un dígito repetido? ¿Cuántos números naturales de uno o más dígitos pueden formarse si ningún número puede tener un dígito repetido?

6.

Un estante tiene espacio para 7 libros. Si disponemos de 6 libros diferentes de Biología y 7 libros diferentes de Química, ¿De cuántas maneras podemos colocar en el estante 4 libros de Biología y 3 libros de Química, si los libros de la misma especialidad tienen que estar juntos?

7.

¿Cuántos números de 6 cifras distintas pueden formarse con los dígitos 4, 5, 6, 7, 8 y 9, si:

8.

a) b)

los números 7 y 8 tienen que estar juntos? los números 7 y 8 tienen que estar separados?

a)

¿De cuántas maneras pueden sentarse 5 personas en una fila de 5 sillas si hay 3 personas que tienen que estar uno al lado del otro? Resolver la parte a) si se considera una fila de 6 sillas.

b)

Universidad Nacional del Santa

21

Análisis Combinatorio

Fidel Vera Obeso

9.

Calcular el número de permutaciones diferentes que puedan formarse con las letras de la palabra MISSISSIPPI, tomadas todas a la vez.

10.

¿Cuántos numerales distintos de 6 dígitos pueden formarse en cada caso: a) b) c) d)

11.

Un grupo formado por 5 muchachos y 5 muchachas van a sentarse de modo que queden alternados. Calcular de cuántas maneras pueden hacerlo si: a) b)

12.

1, 5 y 6 pueden utilizarse cada uno una vez; 2 puede utilizarse tres veces. 4, 7 y 8 pueden utilizarse cada uno dos veces. 3 puede utilizarse dos veces; 2 puede utilizarse tres veces; 8 puede utilizarse una sola vez. 5 puede utilizarse cuatro veces; 9 puede utilizarse dos veces.

se sientan en línea recta. se sientan alrededor de una mesa circular.

Siete personas van a sentarse alrededor de una mesa circular. Hallar el número de maneras diferentes en que esto puede hacerse si: a) b)

no hay restricciones. dos personas determinadas deben quedar contiguas.

Universidad Nacional del Santa

22

Análisis Combinatorio

Fidel Vera Obeso

OBJETIVO N° 03 CALCULAR EL NÚMERO DE COMBINACIONES DE n ELEMENTOS DE UN CONJUNTO TOMADO DE r EN r

ACTIVIDAD N° 01 INTERPRETE LOS TEOREMAS Y EJEMPLOS DESARROLLADO SOBRE

3.4.

ANALICE

LOS

COMBINACIONES DE n ELEMENTOS TOMADOS DE r EN r. Cada uno de los distintos arreglos que pueden formarse tomando todos o parte de los elementos de un conjunto, con la condición de que dos arreglos serán distintos si y solo si están formados por elementos distintos, es decir, no se tiene en cuenta el orden de los elementos tomados, se llama combinación. Así, mientas que ab y ba son dos permutaciones distintas, ambos representan una sola combinación, a saber, el arreglo formado por las dos letras a y b. El número de combinaciones de n elementos diferentes tomados de r en r está dado por la fórmula: n

P(n,r) n! C(n,r) = ( ) = ---------- = ----------- , r r! r!(n-r)!

r≤n.

Si sustituimos r por n-r obtenemos el resultado: C(n,r) = C(n,n-r) Es decir, para cada combinación de r elementos seleccionados entre n objetos diferentes existe una combinación correspondiente de n-r objetos que no son seleccionados. Tales combinaciones se llaman complementarias.

Universidad Nacional del Santa

23

Análisis Combinatorio

Fidel Vera Obeso

Ejemplo 1. Calcular: a)

C(21,19) Solución. C(21,19) = C(21,21-19)

21! 21! 21x20 C(21,2) = ------------ = -------- = ------- = 210 2!(21-2)! 2! 19! 2 b)

C(7,4) + C(7,5) Solución. C(7,4) + C(7,5)= C(7,7-4) + C(7,7-5) = C(7,3) + C(7,2) 7! 7! = ----------- + ----------3!(7-3)! 2!(7-2)! 7! 7! 7x6x5 7x6 = ------- + ------- = --------- + ------3! 4! 2! 5! 6 2 = 35 + 21 = 56

Los valores de C(n,r) para enteros no negativos r y n, r≤n, forman un modelo interesante cuando están dispuestos en un arreglo triangular como en la Fig. 1 ¿Qué combinaciones pertenecen a la línea punteada? C(0,0) C(1,0) C(1,1) Fig. 1 C(2,0) C(2,1) C(2,2) C(3,0) C(3,1) C(3,2) C(3,3) C(4,0) C(4,1) C(4,2) C(4,3) C(4,4) C(5,0) C(5,1) C(5,2) C(5,3) C(5,4) C(5,5) Universidad Nacional del Santa

24

Análisis Combinatorio ...

Fidel Vera Obeso

...

...

...

...

...

Reemplazando los símbolos de la Fig. 1 por sus valores, obtenemos la siguiente tabla: r

0

1

2

3

4

5

6

n 0

1

1

1

1

2

1

2

1

3

1

3

3

1

4

1

4

6

4

1

5

1

5

10

10

5

1

6

.

.

.

.

.

.

.

¿Qué valores le corresponde a la línea 6 de la tabla? Ahora calcule los valores de: C(6,0) C(6,1) C(6,2) C(6,3) C(6,4) C(6,5) C(6,6) para ver si usted ha descubierto el modelo. Regresando a la Fig. 1, localice las combinaciones C(3,2), C(3,3) y C(4,3). Observe que: C(3,2) + C(3,3) = C(4,3) Examinando la Fig. 1, determine cuáles de los siguientes enunciados son verdaderos: C(2,1) + C(2,2) = C(3,2)

C(3,2) + C(3,3) = C(4,3)

C(4,0) + C(4,1) = C(5,1)

C(4,3) + C(4,4) = C(5,4)

Sobre la base de sus observaciones, ¿piensa usted que el siguiente enunciado es verdadero? C(6,2) + C(6,3) = c(7,3) Calcule y verifique su respuesta. Probablemente, usted ha concluido que para todos los enteros no negativos r y n, r≤n: C(n,r-1) + C(n,r) = C(n+1,r) Esta identidad se llama Regla de Pascal. Pascal (1623-1662) fue uno de los Universidad Nacional del Santa

25

Análisis Combinatorio

Fidel Vera Obeso

hombres que en el siglo XVII estudió esta disposición, dada en la tabla precedente, en relación con el estudio de juegos de azar. Los números en este cuadro reciben el nombre de Triángulo de Pascal. Utilizando esta Regla, extiéndese la Tabla con n y r hasta 10, suponiendo que C(n,0) = C(n,n) = 1. A continuación se demuestra la regla de Pascal. Ejemplo 2.

Demostrar que C(n+1,r) = C(n,r) + C(n,r-1)

Solución. :

Partiendo del primer miembro debemos llegar al segundo miembro.

En efecto: (n+1)! (n+1)n! C(n+1,r) = --------------- = --------------r![n-(r-1)]! r![n-(r-1)]! [n-(r-1)+r]! [n-(r-1)]n! rn! = --------------- = --------------- + --------------r![n-(r-1)]! r![n-(r-1)]! r![n-(r-1)]! [n-(r-1)]n! rn! = --------------------- + --------------------r! r(r-1)![n-(r-1)]! n! n! = ----------- + ------------------r!(n-r)! (r-1)![n-(r-1)]! = C(n,r) + C(n,r-1) Ejemplo 3. a)

Hallar n si C(n+1,4) = 6C(n-1,2)

Solución. C(n+1,4) = 6 C(n-1,2) (n+1)! (n-1)! --------------- = 6 --------------4![(n+1)-4]! 2![(n-1)-2]! (n+1)! (n-1)! ----------- = 6 ----------4!(n-3)! 2!(n-3)! Universidad Nacional del Santa

26

LQQD

Análisis Combinatorio

Fidel Vera Obeso

(n+1)n(n-1)! ---------------- = 3(n-1)! 4.3.2 n2 + n = 72 n2 + n - 72 = 0 (n-8) (n+9) = 0 n=8

y

n = -9

Se descarta (n = -9)

Por tanto: n = 8

b)

Hallar r si 2 C(6,r) = 3 C(5,r)

Universidad Nacional del Santa

27

Análisis Combinatorio

Fidel Vera Obeso

Solución. 2 C(6,r) = 3 C(5,r) 6! 5! 2 ----------- = 3 ----------r!(6-r)! r!(5-r)! 6x5! 5! 2*-------------- = 3-------(6-r) (5-r)! (5-r)! 4=6-r

r=2

Ejemplo 4. ¿Cuántos comités de cinco integrantes se pueden formar con ocho estudiantes de Energía y con cuatro de Agroindustria si cada comité debe tener: a) exactamente tres estudiantes de Energía; b) por lo menos tres estudiantes de Energía. Solución. a)

En este caso debe haber exactamente 2 estudiantes de Agroindustria. Los estudiantes de Energía pueden seleccionarse de C(8,3) = 8!/3!5! = 56 maneras y los de Agroindustria en C(4,2) = 4!/2!2! = 6 maneras. Por tanto, por el Principio Fundamental de Conteo, el número total de comités de 5 integrantes es 56x6 = 336.

b)

En este caso tenemos tres tipos de comités: (1) tres estudiantes de Energía y 2 de Agroindustria; (2) cuatro de Energía y 1 de Agroindustria; (3) cinco de Energía. El número de comités para cada uno de los tres casos es, entonces: (1) (2) (3)

336. C(8,4) C(4,1) = (8!/4!4!)x4 = 280 C(8,5) = 56

Sumando, el número total de comités es 336+280+56 = 672

Universidad Nacional del Santa

28

Análisis Combinatorio

Fidel Vera Obeso

Ejemplo 5. Calcular el número de palabras (no necesariamente pronunciables) que pueden formarse seleccionando 5 consonantes y 3 vocales entre 7 consonantes diferentes y 4 vocales diferentes.

Solución. Primeramente seleccionamos 5 consonantes entre 7 consonantes en C(7,5) maneras, es decir: 7! 7x6 C(7,5) = ------- = ----- = 21 5!x2! 2 Análogamente, podemos seleccionar 3 vocales entre 4 vocales de C(4,3) = C(4,1) = 4 maneras. Entonces, por cada una de las 21 maneras para seleccionar las consonantes, tenemos 4 maneras para seleccionar las vocales. Por tanto, por el Principio Fundamental de Conteo, las ocho letras de cada palabra pueden seleccionarse de 21x4 = 84 maneras. Después de efectuar cada una de estas relaciones, las ocho letras pueden permutarse de 8! maneras diferentes. Por tanto, el número total de palabras que pueden formarse es 84x8! = 3'386,880. Ejemplo 6. En una lotería se sortean 5 artefactos eléctricos. El primero que se acerca a la urna saca 3 billetes. Hallar el número de métodos en que puede sacarlos, de modo que por lo menos uno de ellos sea premiado. En la urna hay 20 billetes. Solución. Como se sortean 5 artefactos eléctricos, en la urna hay 5 billetes premiados y 20-5=15 billetes no premiados. Al sacar los tres billetes se presentan las siguientes posibilidades: (1) que uno de sea premiado y dos no premiados; (2) que dos sean premiados y uno no premiado; (3) que los tres sean premiados. El número de métodos para cada posibilidad es entonces:

(1)

5x15! C(5,1) C(15,2) = ------------ = 525 2!x13!

(2)

C(5,2)C(15,1) = 10x15 = 150

(3)

C(5,3) = 10

Universidad Nacional del Santa

29

Análisis Combinatorio

Fidel Vera Obeso

Sumando, el número total de métodos es 525 + 150 + 10 = 685 Ejemplo 7. Se tienen 15 puntos en el espacio de manera que 4 de ellos no están en un mismo plano. (a) Hallar el número de planos determinados por estos puntos; (b) Calcular el número de estos planos que contienen a un punto prefijado; (c) encontrar el número de estos planos que contienen a dos puntos prefijados. Solución. Decir que 4 puntos no están en un mismo plano significa que solamente 3 puntos están en dicho plano. (a)

Para determinar un plano es necesario 3 puntos de los 15, entonces se debe hallar las combinaciones de 15 tomados de 3 en 3. El número de planos es: C(15,3) = 455

(b)

Si todos los planos contienen un punto prefijado y para determinar un plano es necesario 3 puntos, entonces para calcular el número total de planos debe hallarse las combinaciones de los otros 14 puntos tomados de 2 en 2 y que estos al unirse al punto prefijado determinan planos. Es decir: C(14,2) = 91

(c)

Si todos los planos contienen dos puntos prefijados y para determinar un plano es necesario 3 puntos, entonces para calcular el número total de planos debe hallarse las combinaciones de los otros 13 puntos tomados de 1 en 1 y que este punto al unirse a los dos puntos prefijados forman planos. Es decir: C(13,1) = 13

Universidad Nacional del Santa

30

Análisis Combinatorio

Fidel Vera Obeso

ACTIVIDAD N° 02

RESUELVA A CONTINUACIÓN LOS SIGUIENTES

PROBLEMAS SOBRE COMBINACIONES.

1.

2.

Calcular : a)

C(18,15)

b)

C(8,5) - C(7,5)

Demostrar que : n-r C(n,r+1) = ----- C(n,r) , 0 ≤ r ≤ n. r+1

3.

a)

Hallar n si 2C(n,5) = 3C(n,3)

b)

Hallar n y r si P(n,r) = 120 y C(n,r) = 20.

4.

Se va a seleccionar un comité de 5 miembros entre 6 hombres y 9 mujeres. Calcular el número de tales comités si: (a) deben contener por lo menos dos mujeres; (b) no deben contener más de dos mujeres.

5.

Una bolsa contiene 4 objetos rojos, 6 blancos y 5 azules. De cuántas maneras se pueden escoger 6 objetos: (a) si debe haber dos de cada color; (b) si debe haber exactamente 4 objetos blancos; (c) si no debe haber objetos blancos.

6.

¿Cuántos números de 5 cifras diferentes, tales que contengan 3 cifras impares y 2 pares, pueden formarse con las cifras 1, 2, 3, 4, 5, 6, 7, 8 y 9?

Universidad Nacional del Santa

31

Análisis Combinatorio

Fidel Vera Obeso

7.

En una lotería se sortean 7 artefactos eléctricos. El primero que se acerca a la urna saca 4 billetes. Hallar el número de métodos en que puede sacarlos, de modo que por lo menos uno de ellos sea premiado. En la urna hay 25 billetes.

8.

En un estante hay 12 libros diferentes. (a) Calcular el número de selecciones de 8 libros diferentes que pueden hacerse; (b) Hallar el número de estas selecciones que incluyen a un libro determinado; (c) Encontrar el número de estas selecciones que incluyen a 2 libros determinados.

Universidad Nacional del Santa

32

OBJETIVO N° 04 Análisis Combinatorio

Fidel Vera Obeso DESARROLLAR BINOMIOS Y CALCULAR SU r-ESIMO TÉRMINO UTILIZANDO COMBINACIONES

ACTIVIDAD N° 01 ANALICE LA SIGUIENTE INFORMACIÓN EJEMPLOS DESARROLLADOS SOBRE EL

3.5.

Y

LOS

TEOREMA DEL BINOMIO. El teorema del binomio es una fórmula con la cual se pueden escribir directamente los términos del desarrollo de una potencia entera y positiva de un binomio. Para formarnos una idea de la estructura del desarrollo de (a+b)n, donde n es un número entero y positivo, escribiremos el resultado para los primeros cuatro valores de n. Así, por multiplicación directa, tenemos: (a + b)1 = a + b (a + b)2 = a2 + 2ab + b2 (a + b)3 = a3 + 3a2b + 3ab2 + b3 (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4

Observamos que cada uno de estos desarrollos tienen las siguientes características: 1.

El número de términos es n+1, o sea, una unidad más que el exponente n del binomio.

2.

En el primer término el exponente de a es n y decrece de unidad en unidad en cada uno de los términos siguientes.

3.

La b aparece por primera vez en el segundo término, con exponente 1, y éste aumenta de unidad en unidad en cada uno de los términos siguientes. El exponente de b es siempre una unidad menor que el número de orden del término.

Universidad Nacional del Santa

33

Análisis Combinatorio

Fidel Vera Obeso

4.

La suma de los exponentes de a y b es igual a n en cualquiera de los términos.

5.

Los coeficientes de a y b presentan cierta simetría, que consiste en que los coeficientes de términos equidistantes de los extremos son iguales.

6.

El coeficiente del primer término es la unidad y el del segundo término es n.

7.

Si en cualquiera de los términos el coeficiente se multiplica por el exponente de a y este producto se divide entre el exponente de b aumentado en 1, el resultado es el coeficiente del siguiente término.

Nota: Las primeras seis características se observan inmediatamente, la séptima tal vez no parezca tan evidente, y como es de mucha importancia en la determinación de coeficientes, la explicaremos con más detalle aplicándola al desarrollo de (a+b)4. El coeficiente del tercer término se obtiene del segundo como sigue: se multiplica el coeficiente 4 del segundo término por el exponente 3 de a y este producto se divide entre el exponente 1 de b aumentado en 1. Es decir, (4x3)/(1+1) = 6, que es el coeficiente del tercer término. Análogamente, de este coeficiente obtenemos (6x2)/(2+1) = 4, que es el coeficiente del cuarto término, y así sucesivamente. Ahora, si suponemos que para cualquier valor entero y positivo de n, el desarrollo de (a+b)n tiene las mismas características que observamos para n=1,2,3,4, podemos escribir:

n(n-1) n(n-1)(n-2) n-2 2 (a+b) = a + -a b + --------- a b + --------------an-3b3 + 1 1.2 1.2.3 n

n

n

n-1

n(n-1)(n-2)(n-3) + -----------------------an-4b4 + ... + 1.2.3.4

n(n-1)(n-2)...(n-k+2) + ----------------------------an-k+1bk-1 + 1.2.3..(k-1)

n(n-1)(n-2)...(n-k+1) n + ---------------------------an-kbk + ... +--abn-1 + bn 1.2.3...k 1

(a+b)n = C(n,0)an + C(n,1)an-1b + C(n,2)an-2b2 + C(n,3)an-3b3 + T1 T2 T3 T4

Universidad Nacional del Santa

34

Análisis Combinatorio

Fidel Vera Obeso

+ C(n,4)an-4b4 + ... + C(n,k-1)an-k+1bk-1 + T5 Tk + C(n,k)an-kbk + ... + C(n,n-1)abn-1 + c(n,n)bn Tk+1 Tn Tn+1 n

n

(a+b) = Σ C(n,k)an-kbk k=0 n+1

(a+b)n = Σ C(n,k-1)an-k+1bk-1 k=1

Donde: Término k-ésimo :

Tk = C(n,k-1)an-k+1bk-1

Término (k+1)-ésimo: Tk+1 = C(n,k)an-kbk

Nota: En la quinta característica del desarrollo del binomio observamos cierto tipo de simetría en los coeficientes de los términos. Esta simetría se muestra claramente en el triángulo de Pascal, que da los coeficientes de los términos del desarrollo de (a+b)n para valores enteros y positivos. Estos coeficientes se llaman coeficientes binomiales o binómicos.

Ejemplo 1. Desarrollar (a+2b)6 mediante el teorema del binomio y simplificar el resultado.

Universidad Nacional del Santa

35

Análisis Combinatorio

Fidel Vera Obeso

Solución. Empezaremos escribiendo el primer término a6 y el coeficiente 6 del segundo término, que va multiplicado por a5(2b). De este punto en adelante podemos escribir inmediatamente todos los términos que siguen, incluyendo los coeficientes, de acuerdo a las características del desarrollo binomial. Así tenemos: 6x5 6x5x4 4 2 (a+2b) = a + 6a (2b) + ------a (2b) + ----------a3(2b)3 + 2! 3! 6

6

5

6x5x4x3 + -----------a2(2b)4 + 6a(2b)5 + (2b)6 4!

Nótese que hemos conservado el término 2b encerrado en paréntesis para que no interfiera con la formación correcta de los coeficientes binomiales. Luego podemos efectuar las potencias de 2b y obtener la forma final. (a+2b)6 = a6 + 12a5b + 60a4b2 + 160a3b3 + 240a2b4 + 192ab5 + 64b6

Ejemplo 2. a)

Desarrollar (

y 4 x1/2 ) 1/2 y x

Solución. En este desarrollo es aconsejable encerrar ambos términos en paréntesis, ya que aquí no sólo nos interesa formar correctamente los coeficientes binomiales, sino también obtener correctamente los exponentes finales y los signos de cada término. Por tanto, escribimos el desarrollo en varios pasos, como sigue: [

y x1/2 x1/2 4- k - y k + () ] 4 = ∑4k=0 C(4,0)( ) ( ) y y x1/2 x1/2

x1/2 x1/2 -y = C(4,0)(--------)4 + C(4,1)( --------)3(--------) + y y x1/2 x1/2 -y x1/2 -y 2 2 + C(4,2)( --------) (--------) + C(4,3)( --------)(--------)4 + Universidad Nacional del Santa

36

Análisis Combinatorio

Fidel Vera Obeso y

x1/2

y

x1/2

-y + C(4,4)( --------)4 x1/2 x1/2 x3/2 -y x y2 x1/2 -y y4 = -------- + 4(--------)(--------) + 6--------.-------- + 4-------- (--------) + -------y4 y3 x1/2 y2 x y x3/2 x2 x2 x y2 y4 = -------- - 4--------- + 6 - 4-------- + -------y4 y2 x x2 b)

Desarrollar (a + b - c)3 3

(a+b-c)3 = [(a+b)+(-c)]3 = Σ C(3,k)(a+b)3-k(-c)k k=0

= C(3,0)(a+b)3 + C(3,1)(a+b)2(-c) + C(3,2)(a+b)(-c)2 + + C(3,3)(-c)3 = (a+b)3 + 3(a+b)2(-c) + 3(a+b)(-c)2 + (-c)3 = (a3 + 3a2b + 3ab2 + b3) - 3c(a2 + 2ab + b2) + 3c2(a+b) - c3 = a3 + 3a2b + 3ab2 + b3 - 3a2c - 6abc - 3b2c + 3ac2 + + 3bc2 - c3 3.6.

FORMULA PARA HALLAR UN TERMINO CUALQUIERA DE UN BINOMIO. Ya hemos observado que en el desarrollo de (a+b)n, el término k-ésimo |Tk = C(n,k-1)an-k+1 bk-1

[1]

se llama el término general. Esta es una fórmula muy conveniente para obtener cualquier término del desarrollo de la potencia de un binomio sin calcular los términos anteriores. Universidad Nacional del Santa

37

Análisis Combinatorio

Fidel Vera Obeso

Se sigue de [1] que el término que contiene bk es el término (k+1)-ésimo, o sea: Tk+1 = C(n,k)an-k bk

[2]

Cualquiera de estas fórmulas puede usarse para obtener un término particular del desarrollo binomial. Ejemplo 3. Hallar el séptimo término del desarrollo de

1 (2a - - b4)10 4 3

Solución. Utilizando la fórmula [2]: Tk+1 = C(n,k)an-k bk T6+1 = C(10,6)a10-6 b6 T7 = C(10,6)a4b6 T7 = 210a4b6 Por tanto: 1 1 T7 = 210(2a3)4(---- b4)6 = 210 x 24 x a12 x ---- b24 4 46 24 210 210 T7 = 210. ----.a12b24 = ------.a12.b24 = -------.a12.b24 212 28 256

Ejemplo 4. Hallar el término correspondiente que contiene a x3 en el desarrollo de (x-3x-1)9. Solución. Universidad Nacional del Santa

38

Análisis Combinatorio

Fidel Vera Obeso

Este problema difiere del anterior en que no sabemos el orden del término que se busca. Por tanto, representaremos por k el orden del término. De acuerdo a la forma [2], el término de orden k+1 es: Tk+1 = C(9,k)a9-k bk Tk+1 = C(9,k).x9-k.(-3x-1)k Tk+1 = C(9,k).x9-k.(-3)k.x-k = C(9,k).(-3)k.x9-2k Ya que nos interesa que el exponente de x sea 3, se debe tener 9-2k = 3, ==> k = 3; o sea, que el término buscado es: T3+1 = C(9,3).x9-3.(-3)3.x-3 = c(9,3)(-3)3x3

9x8x7 T4 = ----------- (-27)x3 = -2268x3 3x2 Nota: En los diversos desarrollos de (a+b)n, observamos que los coeficientes aumentan hasta la mitad del desarrollo y luego decrecen en orden inverso. De esto podemos concluir que si n es par, el desarrollo tiene un número impar de términos y el término central es el que tiene mayor coeficiente; y si n es impar, el desarrollo tiene un número par de términos, y los dos términos centrales son los que tienen mayor coeficiente. Esto es consecuencia de lo siguiente: Si n es par, el valor máximo de C(n,k) se obtiene cuando k=½, y si n es impar se obtiene cuando k = (n-1)/2 ó k = (n+1)/2.

Ejemplo. Sin desarrollar directamente, calcular el mayor coeficiente del desarrollo de (a+b)8. Solución. n = 8 es par, entonces el valor máximo de C(8,k) se obtiene cuando k = 8/2 = 4, es decir: 8! 8x7x6x5 C(8,4) = ------ = ------------------- = 70 4!4! 4x3x2

Universidad Nacional del Santa

39

Análisis Combinatorio

Universidad Nacional del Santa

Fidel Vera Obeso

40

Análisis Combinatorio

Fidel Vera Obeso

ACTIVIDAD N° 02

RESUELVA A CONTINUACIÓN LOS SIGUIENTES

PROBLEMAS SOBRE EL TEOREMA DEL BINOMIO. 1.

2.

Desarrollar las siguientes expresiones mediante el teorema del binomio y simplificar el resultado. a)

(5x - y2)4

b)

(ex - e-x)9

c)

(x3/2 - x-3/2)4

d)

(1 + x)4 + (1 - x)4

Escribir y simplificar los primeros cuatro términos del desarrollo de la potencia del binomio. a)

3.

4.

(ex/2 - e-x/2)20

(x2/3 - y2/3)8

b)

Obtener solamente el término o términos indicados en el desarrollo correspondiente: a)

Octavo término de (x1/2 + y1/2)12

b)

Término central de (a/b - b/a)10

c)

Los dos términos centrales de (x2/2 - y)9

d)

Términos en y4 de (2x/3y + 3y/2x)10

e)

Término independiente de x de (x1/2/y2/3 + y1/2/x3/2)16

Hallar el término que contiene a x10 en el desarrollo: (1 + 3x2 + 3x4)7

5.

Los términos T2, T3 y T4 del desarrollo de (a+b)n valen respectivamente 240, 720 y 1080. Hallar los valores de a, b y n.

Universidad Nacional del Santa

41

Análisis Combinatorio

Fidel Vera Obeso

POST - TEST

INSTRUCCIÓN: RESUELVE EL POST-TEST DE ACUERDO A LOS REQUERIMIENTOS DADOS. ────────────────────────────────────────────────────────────

1.

¿Cuántos enteros positivos impares de 4 dígitos diferentes cada uno son mayores que 3540?

2.

¿De cuántas maneras pueden alinearse 6 bolas blancas y 3 negras?

3.

¿De cuántas maneras diferentes pueden sentarse siete personas alrededor de una mesa circular si dos personas determinadas no deben quedarse juntas?

4.

¿De cuántas maneras pueden escogerse un comité de seis personas entre doce personas si dos personas determinadas no pueden aparecer en el mismo comité?

5.

Hallar el término que contiene a X10 en el desarrollo de : (1 + 3x2 + 3x4)7

NOMBRE : ...................................... FECHA : ...................................... TIEMPO : 1 hora 30 minutos.

Universidad Nacional del Santa

42

Análisis Combinatorio

Fidel Vera Obeso

ÍNDICE PÁG ♦ PRÓLOGO ♦ INDICE ♦ PRE TEST ♦ OBJETIVOS ♦ PRINCIPIO FUNDAMENTAL DEL CONTEO ------------------------------ 01 ♦ PROBLEMAS SOBRE EL PRINCIPIO FUNDAMENTAL DE CONTEO 09 ♦ PERMUTACIONES LINEALES ----------------------------------------------- 10 ♦ PERMUTACIONES LINEALES CON REPETICION --------------------- 18 ♦ PERMUTACIONES CIRCULARES ------------------------------------------ 19 ♦ PROBLEMAS SOBRE PERMUTACIONES LINEALES Y CIRCULARES 21 ♦ COMBINACIONES DE n ELEMENTOS TOMADOS DE r en r --------- 23 ♦ PROBLEMAS SOBRE COMBINACIONES --------------------------------- 31 ♦ TEOREMA DEL BINOMIO ---------------------------------------------------- 33 ♦ FORMULA PARA HALLAR UN TERMINO CUALQUIERA DE UN BINOMIO ------------------------------------------------------------------------- 38 ♦ PROBLEMAS SOBRE EL TEOREMA DEL BINOMIO ------------------ 41 ♦ POS-TEST -------------------------------------------------------------------------- 42 ♦ BIBLIOGRAFÍA

Universidad Nacional del Santa

43

Análisis Combinatorio

Fidel Vera Obeso

PRÓLOG

En el presente módulo autoinstructivo se estudia el Análisis Combinatorio y se abordan problemas específicos sobre permutaciones y combinación a partir del Teorema Fundamental de Conteo, y también se abarca el Teorema del Binomio, el cual nos permite desarrollar un binomio cualquiera y calcular cualquiera de sus términos. Está destinado a los postulantes de las Universidades, estudiantes de los primero s ciclos de las Universidades. También puede ser útil para los profesores que enseñan estos temas. Los objetivos específicos se logran siempre y cuando los grupos de ejercicios se resuelvan con una eficacia del 80%, en caso contrario deberán volver a estudiar los cuadros correspondientes y resolver nuevamente los ejercicios incorrectos o no resueltos. Resuelva los problemas propuestos del modo siguiente: primero en forma individual, luego en forma grupal y por último preséntelos en un grupo de un máximo de cinco (05) integrantes. Cumpla también con las actividades de retroalimentación antes de presentarse al Examen de Verificación... Te deseo buena suerte!

El Autor

Universidad Nacional del Santa

44

Análisis Combinatorio

Fidel Vera Obeso

OBJETIVOS

OBJETIVO TERMINAL. Describir y calcular los diversos arreglos y selecciones que es posible hacer con los elementos de un conjunto dado, y utilizar los resultados en la solución de problemas prácticos.

OBJETIVOS ESPECÍFICOS. 1.

Interpretar el Principio Fundamental de Conteo y aplicarlo en la solución de problemas.

2.

Calcular el número de permutaciones lineales y circulares de n elementos de un conjunto tomados de r en r.

3.

Calcular el número de combinaciones de n elementos de un conjunto tomados de r en r.

4.

Desarrollar binomios y calcular su r-ésimo término utilizando combinaciones.

CONTENIDO. 3.1. Principio Fundamental de Conteo. 3.2. Permutaciones Lineales. Permutaciones lineales con repetición. 3.3. Permutaciones circulares. 3.4. Combinaciones de n elementos tomados de r en r. 3.5. Teorema del binomio. 3.6. Fórmula para hallar un término cualquiera de un binomio.

Universidad Nacional del Santa

45

Análisis Combinatorio

Fidel Vera Obeso

PRE - TEST

INSTRUCCIÓN: RESUELVE EL PRE-TEST DE ACUERDO A LOS REQUERIMIENTOS DADOS. ────────────────────────────────────────────────────────────

1.

¿Cuántos enteros positivos impares de 4 dígitos diferentes cada uno son mayores que 3540?

2.

¿De cuántas maneras pueden alinearse 6 bolas blancas y 3 negras?

3.

¿De cuántas maneras diferentes pueden sentarse siete personas alrededor de una mesa circular si dos personas determinadas no deben quedarse juntas?

4.

¿De cuántas maneras pueden escogerse un comité de seis personas entre doce personas si dos personas determinadas no pueden aparecer en el mismo comité?

5.

Hallar el término que contiene a X10 en el desarrollo de : (1 + 3x2 + 3x4)7

NOMBRE : ...................................... FECHA : ...................................... TIEMPO : 1 hora 30 minutos.

Universidad Nacional del Santa

46