5_08COMBINACIONES_2008

GUSTAVO A. DUFFOUR 146

Actualmente, el análisis combinatorio tiene por objeto el estudio de las distintas formas de agrupar y ordenar los elementos de un conjunto, sin tener en cuenta la naturaleza de estos elementos.

Los problemas típicos de arreglos y combinaciones tienen un aspecto árido y monótono. Al principio, cuesta creer que los conocimientos que se adquieren al resolver problemas de este tipo puedan servir de mucho en otros estudios. Sin embargo, los teoremas del análisis combinatorio son la base del cálculo de la probabilidad.

La probabilidad es una de las ramas de la matemática que se ocupa de los arreglos y las combinaciones que determinan el número de formas diferentes en que un acontecimiento puede suceder.

También el análisis combinatorio tiene importantes aplicaciones en el diseño y funcionamiento de ordenadores o computadoras, así como en las ciencias físicas y sociales.

De hecho, la teoría combinatoria es de gran utilidad en todas aquellas áreas en donde tengan relevancia las distintas maneras de agrupar un número finito de elementos.

En el estudio de la evolución del pensamiento matemático, se considera un gran logro de la época medieval la suma de progresiones desarrollada por Yang Hui (s. XIII). Junto a estas sumas de progresiones se establecieron los elementos básicos en la rama de la combinatoria, construyendo el llamado espejo precioso, de manera similar a lo que hoy conocemos como triángulo de Pascal.

Pero el origen de la combinatoria se remonta a los trabajos de Pascal (1596-1650) y Fermat (1601-1665), que fundamentaron el cálculo de probabilidades.

También se ocupó del análisis combinatorio el alemán Gottfried. W. Leibniz (1646-1716) en su obra Disertatio de Arte Combinatoria, publicada en 1666.

Sin embargo, el mayor impulsor de esta rama durante el siglo XVII fue Jacques Bernoulli, quien en su obra Ars Conjectandi –publicada en 1713, ocho años después de su muerte, aunque el trabajo estaba incompleto– incluye una teoría general de permutaciones y combinaciones.

Jacques Bernoulli

G.W. Leibniz

MATEMÁTICA DE QUINTO 147

(Véase página 174)

A lo largo de una avenida hay tres semáforos cuyas luces encendidas nunca coinciden. 1) ¿Cuántas secuencias distintas de colores podemos ver? R V A R A V A V R A R V V R A V A R 2) ¿En cuántas de las secuencias los semáforos extremos no están en verde? R V A A V R 3) ¿En cuántas el semáforo central está en rojo?

V R A A R V 4) ¿En cuántas el semáforo central no está en verde? R A V A R V V R A V A R

Total de secuencias

6

En 2 secuencias

En 2 secuencias

En 4 secuencias

8

ANÁLISIS

COMBINATORIO

1 – INTRODUCCIÓN En la teoría del análisis combinatorio se estudia la manera de tomar los elementos de un conjunto según varios métodos, a los cuales llamaremos arreglos, combinaciones o permutaciones. Nos proponemos, en cada caso, establecer fórmulas numéricas que permitan calcular el número de subconjuntos que pueden formarse con los elementos del conjunto dado. 2 – NOTACIÓN Para referirse a los arreglos se usará la letra A cuando se quiera indicar cuántos son los arreglos (un número); y se usará la letra A cuando se quiera indicar los subconjuntos ordenados formados. Para referirse a los números combinatorios se usará la letra C que indica cuántas combinaciones hay (un número); y se usará la letra C cuando se quiera indicar los subconjuntos formados. En ambos casos se usarán otras dos letras: la m indica cuántos elementos tiene el conjunto dado. Se acostumbra a escribirla como índice superior. La k indica cuántos elementos se toman del conjunto dado. Se acostumbra a escribirla como índice inferior.


Los arreglos son subconjuntos ordenados. En el capítulo 3 se definió un nombre para los conjuntos ordenados.

CUPLAS para 2 elementos. N-UPLAS para n elementos.

Y se anotaron entre paréntesis curvos. La comodidad, quizás la costumbre, no respeta esta notación, indicando simplemente los arreglos como:

ab, ac, ba, …

3 – CONDICIONES DE EXISTENCIA DEL ANÁLISIS COMBINATORIO (sin elementos repetidos) En este tema se trabaja con los elementos de un conjunto, por lo que se debe tener siempre presente que el número de elementos del conjunto dado m y el número de elementos de los subconjuntos k que se formen son números naturales. Además, k debe ser menor o igual a m, pues no es posible tomar más elementos de los que se dispone.

m e k e k < m 4 – ARREGLOS (Sin elementos repetidos)

4.1. DEFINICIÓN

Dado un conjunto de m elementos, llamaremos arreglos de m elementos tomados de a k, a todos los subconjuntos ordenados formados por k elementos cualesquiera, elegidos de entre los m elementos dados.

Dos arreglos serán distintos cuando difieran en algún elemento o, si constan de los mismos elementos, cuando difieren en el orden (los arreglos son subconjuntos ordenados). Dos arreglos son iguales cuando tienen los mismos elementos, en el mismo orden. NOTACIÓN

mkA ? Un conjunto de k-uplas

(La enumeración de los subconjuntos ordenados de k elementos tomados de entre los m elementos dados)

mkA ? Un número

(Cuántos arreglos de orden k hay, tomados de entre los m elementos dados).

( )mk #A =

mkA


NOTA El estudiante debe empezar a diferenciar muy bien dos conceptos básicos en este tema. Dado el conjunto {a, b, c}

¿Cuáles son los arreglos de orden dos? UN CONJUNTO

32A = {(a, b), (a, c), (b, a), (b, c), (c, a), (c, b)}

¿Cuántos son dichos arreglos? UN NÚMERO 36

2A =

EJEMPLO: Hallar el mayor natural h para que 2h 6

3 hA+

− sea un arreglo válido.

Se deben considerar las tres condiciones de existencia. 2h + 6 > 0 ? h > – 3 h debe estar entre – 1 y 3

En: 2h 6

3 hA+

− 3 – h > 0 ? h < 3

2h + 6 > 3 – h ? h > – 1 El mayor natural es: h = 3

NOTA Considerar las condiciones de existencia es de fundamental importancia en la resolución de problemas. Frente a varias soluciones se podrá decir si ellas son posibles o no.

Téngase en cuenta que con los arreglos se usa la misma palabra para indicar al conjunto y a la cantidad de sus elementos. No sucede así con las combinaciones y el número combinatorio.


4.2. CÁLCULO DE ARREGLOS, MÉTODO DE RECURRENCIA El método de recurrencia para calcular el número de arreglos consiste en, calcular el número de arreglos de un determinado orden k, a partir de los arreglos del orden anterior (k – 1).

De modo que, dados los arreglos de orden uno, se calculan los arreglos de orden dos. Y, a partir de estos, los de orden tres, y así sucesivamente, hasta k.

Un concepto de uso reiterado es el de «los restantes elementos del conjunto». Sea un conjunto de cinco elementos {a, b, c, d, e}. Si se toman dos elementos a y b, los restantes elementos del conjunto son c, d y e.

En el caso general de un conjunto de m elementos de los que se toman 3, los restantes elementos del conjunto que no fueron tomados son (m – 3).

4.2.1. EJEMPLO NUMÉRICO Sea un conjunto de cuatro elementos {a, b, c, d}. Los arreglos de orden uno son los subconjuntos de un solo elemento.

4 41A =

41A

Si se reúne a cada arreglo de orden uno (por ejemplo, el b) con los restantes elementos del conjunto (o sea, b con a, b con c, b con d), se forman los arreglos de orden dos. De este modo, por cada arreglo unitario resultarán tres arreglos de orden dos. a ? ab ac ad

4 4 3 4 3 122 1A A= × = × = b ? ba bc bd c ? ca cb cd

d ? da db dc A 42

A partir de los arreglos de orden dos se forman los arreglos de orden tres, siguiendo el mismo procedimiento. Se reúne cada arreglo de orden dos con los restantes elementos del conjunto. ab ? abc abd ac ? acb acd

4 4 2 4 3 2 243 2A A= × = × × = ad ? adb adc

. . . . . . . . . . . .

dc ? dca dcb A 43

a

b

c

d

Tomados de a dos.


Una forma cómoda de plantear el método de recurrencia es en forma de árbol. Se denomina árbol secuencial y se parte de los arreglos de orden cero. Luego vienen los arreglos de orden uno. Para construir los arreglos de orden dos, se reúne cada arreglo de orden uno con los restantes elementos del conjunto que no se tomaron.

A 40 4

1A A 42 A 4

3 A 44

abc abcd ab abd abdc acb acbd a ac acd acdb adb adbc ad adc adcb bac bacd ba bad badc bca bcad b bc bcd bcda bda bdac bd bdc bdca ∅ cab cabd ca cad cadb cba cbad c cb cbd cbda cda cdab cd cdb cdba dab dabc da dac dacb dba dbac d db dbc dbca dca dcab dc dcb dcba

4.2.2. CASO GENERAL Para un conjunto de m elementos

m m1A =

m m (m 1) m(m 1)2 1A A= × − = −

m m (m 2) m(m 1)(m 2)3 2A A= × − = − −

Cada uno de los m elementos del conjunto dado constituye un arreglo unitario o de orden uno. Si a la derecha de estos arreglos unitarios colocamos sucesivamente los (m – 1) elementos restantes, se tendrá que por cada arreglo de orden uno, hay (m – 1) arreglos de orden dos. Si a la derecha de estos arreglos de orden dos, colocamos sucesivamente los (m – 2) elementos restantes, se tendrá que, por cada arreglo de orden dos, hay (m – 2) arreglos de orden tres.

Tomados de a tres.


( )m m(m 1)(m 2)... m (k 1)

kA = − − − −

( )mm

m (k 1)k k 1AA = × − −−

Si se siguen formando por este método los arreglos de cuarto, quinto,..., orden, se

obtendrá que los arreglos de orden k son iguales a los arreglos de orden anterior mk 1A −

por los restantes elementos del conjunto los (m – (k – 1)). Al sustituir los arreglos de orden anterior por la expresión que se fue formando al considerar los arreglos de orden 1, 2, 3,..., se obtiene la fórmula de recurrencia para calcular el número de arreglos de orden k.

La cantidad de arreglos de m elementos tomados de a k está dado por el producto de k factores consecutivos y decrecientes que comienzan en m.

EJEMPLO: Calcular: i) 12 3A ii) 232A iii) h 1

3A −

i) 123A = 12 * 11 * 10 = 1320 ii) 23

2A = 23 * 22 = 506

iii) h 13A − = (h – 1)(h – 2)(h – 3)

Se deja expresado como tres factores decrecientes a partir de (h – 1).

Es fácil calcular la cantidad de arreglos o combinaciones que se pueden formar, usando alguno de los últimos modelos de calculadoras científicas, pues ellas traen una tecla dedicada a estos cálculos, aunque la notación es diferente.

Para arreglos y permutaciones se usa la letra P y como índices se usan la n y la r. Se escribe: nPr.

Para números combinatorios se usa la letra C y como índices se usan la n y la r. Se escribe: nCr.

5 = 5 3 = 60

3PA

5 = 5 3 = 10

3CC


La simplificación por factores dependientes de la incógnita elimina soluciones: aquellos valores que anulan la expresión simplificada.

En el caso del análisis combinatorio debemos simplificar, pues es más fácil para la resolución del problema. Y los valores que se eliminan no pueden ser soluciones, por las condiciones de existencia vistas anteriormente.

EJEMPLO:

Calcular n para que n 1 n2 3 3A A− =

Primero se desarrolla la igualdad aplicando la fórmula de recurrencia para cada uno de los arreglos, para luego simplificar y despejar el valor de n.

n 1 n2 3 3A A− =

2 (n 1)− (n 2)− (n 3) n (n 1)− = − (n 2)− 2(n – 3) = n 2n – 6 = n n=6 Antes de continuar, es conveniente hacer los ejercicios 150 al 155, de la página 180.

4.3. ARREGLOS DE ORDEN CERO El único arreglo de orden cero (que no tiene ningún elemento) es el conjunto vacío. Entonces se cumple que para cualquier m:

m 10A = Recordar que:

{ } = ∅Am0

5 – FACTORIAL DE UN NÚMERO

5.1. DEFINICIÓN El producto de todos los números naturales, desde m hasta uno, se llama factorial de m. NOTACIÓN: Factorial de m ? m! m! = m(m – 1)(m – 2)(m – 3)... 3 * 2 * 1 Ejemplo: 5! = 5 * 4 * 3 * 2 * 1 = 120 Por convención, se establece que: 0! = 1

Cumple existencia.Véase p.148.


El cálculo del factorial de un número es inmediato en cualquier calculadora científica. Incluso se emplea la misma notación. Un detalle interesante es que, debido a que las calculadoras científicas muestran resultados entre 10-99 y 1099, el máximo valor que pueden calcular es 69! Por lo tanto, si se plantea: 100! =98!

Aunque el resultado final de la operación es 9900, la calculadora no puede realizarlo y primero se debe simplificar.

5.2. OPERACIONES CON FACTORIALES

Frecuentemente es necesario simplificar factoriales. Para ello se opera con aquellos factoriales que difieren en solo algunas unidades. Se identifica siempre cuál es el factorial más grande, para expresarlo como factores decrecientes hasta el factorial más chico. EJEMPLO: Simplificar:

i) 15!17!

ii) (m 1)!(m 3)!

−−

i) Se desarrolla el factorial más grande 17! hasta el más chico 15! para luego simplificar los factoriales que quedan.

15! 15! 17!

=17 16 15!* *

1 1 17 16 272

= =*

ii) Se desarrolla el factorial más grande (m – 1)! hasta el más chico (m – 3)! para luego simplificar los factoriales que quedan.

(m 1)(m 2)(m 3)!(m 1)!

(m 3)!− − −−

=− (m 3)!−

2 (m 1)(m 2) m 3m 2= − − = − +

Antes de continuar, es conveniente hacer

el ejercicio 156, de la página 180.

6 – FÓRMULA DE ARREGLOS EN FUNCIÓN DE FACTORIALES Si a la fórmula hallada por el método de recurrencia se la multiplica y se la divide por todos los factores decrecientes que faltan hasta llegar a uno, no se altera el resultado.

( )m!

m (m k)(m k 1) ... 3 2 1 m(m 1)(m 2) ... (m k 1) .k (m k)(m k 1) ... 3 2 1(m k)!

A − − −= − − − +

− − −

−

* ** *


NOTA Desde el punto de vista práctico es necesario usar la fórmula de factoriales cuando no se conozca el número de elementos que se toman.

En mkA (k desconocido)

me ke k < m

m m! k (m k)!A =

−

Y al cumplirse que 0! = 1 la fórmula anterior se cumple para todos los valores de k, incluidos el cero y el uno.

EJEMPLO: Calcular h en la siguiente ecuación: h 1h = 2 h 2 h 3A A +− −

h 1h = 2 h 2 h 3A A +− −

( )h (h +1) 2

h +1 (h 3)h h 2! !

!!=

− −⎡ ⎤− − ⎡ ⎤⎣ ⎦⎣ ⎦

( ) ( )

h (h +1) 2 h h 2 h +1 h + 3

! !! !=

− + −

( ) ( )h (h +1) 2 2 4! !! !=

h! 4! 22! (h 1)!

=+

**

h! 4 3 2!* * *2! (h 1) (h)!+*

2=

4 3 2h 1

=+*

? 12 = 2h + 2 ? Solución: h = 5

Antes de continuar, es conveniente hacer los ejercicios 157 al 163, de la página 180,

y contestar las preguntas 1 y 2, de la página 179

En el numerador se obtienen todos los factores decrecientes desde m hasta uno, o sea, m! En el denominador, todos los factores decrecientes desde (m – k) hasta uno, o sea, (m – k)!

Se desarrollan cada uno de los arreglos por factoriales. Se pasan todos al primer miembro para simplificar más fácilmente, luego se despeja h.

Cumple existencia.

Véase p. 148.


m 1 m 1m k k k 1 kA A A− −= +−

7 – FÓRMULA PARA SUMAR ARREGLOS Demostración por conjuntos Para demostrar la fórmula se formarán todos los arreglos de m elementos tomados de a k, considerando en primer término todos los arreglos que tienen un elemento en particular, el a. Dado que son arreglos el elemento a al ubicarse en primer lugar, segundo lugar,... enésimo lugar, da forma a los siguientes subconjuntos ordenados. a a a ........................................ a a a a ........................................ a ..................... .................... .................... ........................................ ...................... a a a ........................................ a

k elementos

m 1

k 1A−

−

m 1

k 1A−

−

m 1

k 1A−

−

m 1

k 1A−

−

m 1k 1k A −−

Dado que a es un elemento del conjunto principal y ocupa un lugar, el número de arreglos que contienen al elemento a en cada subconjunto ordenado son: arreglos tomados de entre los m elementos menos el a, ((m – 1) elementos), y contienen (k – 1) elementos,

por no tomarse en cuenta el a. Son m 1k 1A−− . Pero el elemento a puede estar en k

lugares distintos, pues son arreglos: m 1k k 1A −−

Los restantes arreglos que no contienen al elemento a serán: m 1kA − pues son

arreglos de k elementos tomados de entre los (m – 1) (los m menos el a).

Por lo cual, dado un conjunto de m elementos se cumple:

+ =

m 1k k 1A −− + m 1

kA − = mkA

Arreglos que contienen un elemento

determinado

Arreglos que no contienen un elemento

determinado

Total de arreglos


Pm = m!

Los arreglos se conocen con diversos nombres: variaciones, disposiciones, ordenaciones, distribuciones, etc. Los autores ingleses suelen llamar también permutaciones a las variaciones en general (por ejemplo, en las calculadoras). En este texto se llama permutaciones a un caso especial de arreglos.

8 – PERMUTACIONES (Sin elementos repetidos)

Se llaman permutaciones a todas las diferentes ordenaciones que se pueden hacer con todos los elementos de un conjunto dado. Resultan ser los arreglos de m elementos tomados de a m (o de orden m). Por lo cual, la única diferencia entre dos permutaciones radica en el orden de sus elementos, ya que cada permutación está integrada con todos los elementos del conjunto. Notación Pm

Cálculo

m!m m! m(m 1)(m 2)...3 2 1mm (m m)!

0! 1

P A= = = = − −−

=

* *

EJEMPLO: ¿De cuántas maneras diferentes se pueden ordenar cinco libros en un estante?

Una forma fácil de contestar es: 55A , pero es mejor contestar

5P

Ambas respuestas son correctas:

5P = 5 * 4 * 3 * 2 * 1 = 120


Las combinaciones son subconjuntos. En el capítulo 2ya se dio una notación para los subconjuntos, entre llaves. Pero esta notación no es siempre respetada, por comodidad, costumbre, o quizás,porque no es tan fácil, en lascombinaciones con repetición, diferenciar subconjuntos con o sin elementos repetidos. Por ello, muchas veces se indican simplemente las combinacionescomo:

ab, ac, bd, …

9 – COMBINACIONES (Sin elementos repetidos)

9.1. DEFINICIÓN

Dado un conjunto con m elementos, se llaman combinaciones de m elementos tomados de a k, a todos los subconjuntos que se pueden formar con k elementos elegidos entre los m elementos dados.

De la definición anterior surge que dos combinaciones son distintas si difieren en, por lo menos, un elemento.

Tener en cuenta que: me ke k < m NOTACIÓN

Cmk ? Un conjunto de subconjuntos

(La enumeración de los subconjuntos de k elementos tomados de entre los m elementos dados)

mkC ? Un número

(Cuántas combinaciones hay de orden k, tomadas de entre los m elementos dados)

( )mk #C = C

mk


mkC

NOTA

En las combinaciones es importante que el estudiante diferencie perfectamente cuándo se habla del número combinatorio o cuándo se habla de las combinaciones. número combinatorio (cuántas combinaciones hay de k elementos elegidos de entre los m dados). Dado que los números combinatorios son de gran importancia, en algunas ramas de la matemática es usual ver la notación de Euler.

m m

k kC ⎛ ⎞= ⎜ ⎟⎝ ⎠

9.2. EL ÁRBOL DE LAS COMBINACIONES El método más sencillo para hallar las combinaciones, o sea, hacerlas una por una, es construir un árbol. Dado el conjunto {a, e, i, o, u} se formarán las diferentes combinaciones construyendo el árbol de las combinaciones. Para hallar las combinaciones del siguiente orden, se agregan de uno en uno los elementos que siguen al último que figura en cada combinación del orden anterior.

C50 C5

1 C52 C5

3 C54 5

5C

aei aeio aeiou ae aeiu aeo aeou a aeu aio aiou ai aiu ao aou au e ei eio eiou ∅ eiu eo eou eu i io iou iu o ou u

Se indica entre paréntesis tan solo m, el número de elementos del conjunto dado y k, el número de elementos que se toman.


52A

NOTA Obsérvese que se cumple:

5 10C = En general, se cumplirá: m 10C = t me

La combinación correspondiente es el conjunto vacío.

5 15C = En general, se cumplirá: m 1mC = t me

La combinación correspondiente es el conjunto dado.

9.3. DEDUCCIÓN DE LA FÓRMULA PARA NÚMEROS COMBINATORIOS

Sea un conjunto de cinco elementos, las vocales {a,e,i,o,u}. Se formará un cuadro donde en las filas se pondrán las distintas combinaciones de esos cinco elementos tomados de dos en dos, y a lo largo de cada fila se formarán las permutaciones de los elementos de cada combinación.

ae eaai iaao oaau uaei ieeo oeeu ueio oiiu uiou uo

→→→→→→→→→→

52

P

C

2

El cuadro construido de esta manera constituye el conjunto de todos los arreglos de cinco elementos tomados de dos en dos, pues se cumple que: a) Todos los subconjuntos del cuadro son

arreglos, pues se diferencian en un elemento o en el orden.

b) No hay en el cuadro arreglos repetidos,

puesto que dos arreglos de la misma fila difieren en el orden de sus elementos, y dos de distinta fila, por lo menos en un elemento, por provenir de combinaciones distintas.

c) Están todos los arreglos, debido a la manera

de construir el cuadro, uno por uno.


m e k e k < m

Si se toma ahora el número de subconjuntos y se tiene en cuenta su disposición rectangular, se cumple que:

5 5 2 22C P A=* de donde se deduce, al despejar, que: 5 5 2 22

AC P=

9.4. CASO GENERAL

mm kk

k=

AC P

Esta fórmula es de importancia básica para el resto del capítulo.

9.5. EXPRESIÓN NUMÉRICA DEL NÚMERO DE COMBINACIONES Según se expresen arreglos y permutaciones en forma de factores decrecientes o en forma de factoriales, se obtendrán dos fórmulas para el cálculo de un número combinatorio.

m m(m 1)(m 2)... (m k 1) k k(k 1)(k 2)... 3 2 1C − − − +

=− − * *

m m! k (m k)! k!C =−

EJEMPLO: Calcular i) 103C ii) h 3

2C −

i) 10 9 810 120 3 3 2 1C = =* ** * ii) (h 3)(h 2)h 3 = 2 2 1C − −−

×

Para subconjuntos de k elementos,tomados de entre los m, se cumple que:


Se consideran los conjuntos M = { , , } P = { ( , ) , ( , ) , ( , ) , ( , ) , ( , ) , ( , ) } Responder «verdadero» o «falso», y justificar la respuesta. a) Los elementos de P son combinaciones simples de los elementos de M. b) Los elementos de P son arreglos simples tomados de a 3. c) Los elementos de P son arreglos simples tomados de a 2.

d) El cardinal de P es: 32C

e) El cardinal de P es: 32A

Véanse los resultados en la página 478.

EJEMPLO: Calcular h, si: h 3

21 2C+

=

h 3 21 2C + =

(h 3)(h 2) 212 1

+ +=*

(h + 3)(h + 2) = 42 ? h2+ 5h + 6 = 42 ? h2 + 5h – 36 = 0 ? h = 4 h = – 9 Dado que (h + 3) debe ser un número natural: Solución: h = 4

Antes de continuar, es conveniente hacer los ejercicios 164 al 166, de la página 180,

y contestar las preguntas 3, 4 y 5 de la página 179.

Se desarrollan los números combinatoriosaplicando la fórmula de factores decrecientes. Para luego hacer cuentas y despejar la incógnita h.

Cumple existencia.

Véase p. 148.


10 – COMBINACIONES COMPLEMENTARIAS

10.1. CASO PARTICULAR

aei ouaeo iuaeu ioaio euaiu eo

aou eieio aueiu aoeou aiiou ae

→→→→→→→→→→

5523C C

10.2. DEFINICIÓN

Dado un conjunto de m elementos, cada vez que se toman k elementos para formar una combinación, se dejan de tomar los (m – k) elementos restantes, con los cuales se puede formar otra combinación de (m – k) elementos, llamada combinación complementaria de la anterior.

10.3. TEOREMA

Los números combinatorios de orden complementario son iguales.

mm

= k m kC C −

¿Qué significa este teorema? Véase el ejemplo anterior, en 10.1. Caso particular. ¿Puede significar que la combinación oeu es igual a la ai? ? NO ¿Puede significar que la combinación aei es igual a la ou? ? NO ¿Puede significar que la combinación aou es igual a la ei? ? NO El teorema significa que la cantidad de combinaciones tomadas de a k es igual a la cantidad de combinaciones complementarias, de orden (m – k). O sea que se han formado igual número de conjuntos eligiendo k elementos, que eligiendo los (m – k) elementos restantes del total de los m elementos dados.

Dado un conjunto de cinco elementos, las vocales {a, e, i, o, u}, se formarán a la izquierda del dibujo las combinaciones de tres elementos. Cada vez que se toman tres elementos del conjunto de las cinco vocales, quedan sin tomar dos vocales, con las cuales se puede hacer otra combinación que se llamará complementaria de la primera. Téngase en cuenta que, cuando se eligen algunos elementos para formar con ellos un subconjunto, también se están eligiendo los que no se van a usar.


Responder «verdadero» o «falso»,

y justificar la respuesta.

1) m m = 0 0C A t me

2) =C Am m0 0 t me

3) x x . = yyxP A C t xe ye

4) 2m

pC

5) t me m m m mA C≤ 6)

5P 7) (x–1) x! (x+1) = (x+1)! t xe


existe si me pe m2 > p

Es el conjunto de todas las permutaciones de orden 5.

10.3.1 DEMOSTRACIÓN POR CONJUNTOS

El número de combinaciones de orden k es igual al de las complementarias, ya que: 1) Cada combinación tiene una complementaria. 2) La relación de complementaria es recíproca. 3) Si dos combinaciones son distintas, sus complementarias también los son.

10.3.2. DEMOSTRACIÓN POR FACTORIAL

La demostración se puede hacer por aplicación directa de la fórmula.

m m

= k m kC C −

m! m! = (m k)! k! (m m+k)! (m k)!

=k!− − −

10.4. CÁLCULO DEL COMPLEMENTARIO

Debe recordarse que como índice superior se deja el mismo (es el número de elementos del conjunto dado) y como índice inferior se pone al complementario.

20 20complementario 3 17C C⎯⎯⎯⎯⎯⎯⎯⎯⎯→

complementario32 32 20 12C C⎯⎯⎯⎯⎯⎯⎯⎯⎯→

a+b+1 complementario a+b+1 3a+b 2C C⎯⎯⎯⎯⎯⎯⎯⎯⎯→

−

Cuando en el cálculo con números combinatorios se tiene un número combinatorio en cuyo número de elementos del conjunto dado existe la misma incógnita (letra o letras) que en el número de elementos que se toman, es obligatorio, para resolver el problema, poner en lugar de éste el número combinatorio complementario. El objetivo es eliminar la o las letras que se repiten en el número de elementos que se toman, lo que conduce a cálculos más sencillos.

Se resta: 20 – 3 = 17

Se resta: 32 – 20 = 12


10.5. USO OBLIGADO EN LA RESOLUCIÓN DE EJERCICIOS DE LOS NÚMEROS COMBINATORIOS COMPLEMENTARIOS

Cuando se titula uso obligado de los números combinatorios complementarios significa que, frente al siguiente caso, se debe proceder obligatoriamente como se indica. Ya que, por lo general, no es posible resolver el ejercicio de otra manera (por ejemplo, por factorial).

m m = a bC C

a) Si son idénticos, se cumple que: a = b b) Si son complementarios, se cumple que: a+b = m

EJEMPLO: Calcular p en 10+p 10+p

= p+4 2p 10C C −

Como ya se indicó, cuando se tiene o se llega por cálculo a una igualdad de este tipo, el único camino a seguir es plantearse la posibilidad de que los números combinatorios sean idénticos o complementarios. Si son idénticos, se cumple: p + 4 = 2p – 10 (despejando p se obtiene) p = 14

Al sustituir el valor encontrado: 24 24 = 18 18C C

Si son complementarios, se cumple: p + 4 + 2p – 10 = 10 + p (se despeja p) p = 8

Al sustituir el valor encontrado: 18 18 = 12 6C C


los ejercicios 167 al 171, de la página 180, y contestar las preguntas 6 y 7 de la página 179

Cuando se plantea o se llega a una igualdad entre dos números combinatorios que se refieren a igual número de elementos m, se dirá que dichos números combinatorios son idénticos o complementarios.

Las soluciones sirven si se cumplen las condiciones de existencia de los números combinatorios sin elementos repetidos. Véase página 148.

Ambos resultados son correctos, por cumplir las condiciones de existencia del análisis combinatorio (véase página 148). En este ejemplo, además, se verificó en cada caso. Algunas veces uno de los resultados puede no servir, por no cumplir las condiciones de existencia o por llegar a una ecuación imposible.


(m – 1)e(k – 1)e m ≥ (k + 1)

mm 1m 1 + = k k 1 kC C C−−−

Michael Stifel (Alemania, 1487–1567)

Teólogo y matemático alemán, cursó sus estudios superiores en la Universidad de Wittenger, pero se dedicó a una vida religiosa. Se ordenó en 1511 como sacerdote católico en el monasterio de Esslingen, el cual abandonó en 1522. En 1523 se convirtió en pastor luterano. Luego de pasar por varios lugares perseguido por diferentes motivos, en 1549 llegó como pastor a Haberstroh, cerca de la Universidad de Königsber, donde disertó en matemática y teología. En 1557 llegó a ser el más importante profesor de matemática en la recién fundada Universidad de Jena, donde falleció a la edad de 80 años. Stifel investigó en aritmética y álgebra. Inventó los logaritmos, independientemente de Napier, usando un método totalmente diferente. Su trabajo más famoso fue Arithmetica integra, que fue publicado en 1544, y contiene coeficientes binomiales.

11 – FÓRMULA DE STIFEL

La fórmula de Stifel es útil para sumar números combinatorios.

Obsérvese que para poder usar la fórmula, ambos sumandos son números combinatorios cuyo índice superior es igual y el índice inferior difiere en una unidad.

En algunos casos, también es posible usar la fórmula para restar, si se despeja convenientemente, (véase punto 11.3).

EJEMPLO: Hallar a si: a a+1 a a+2 a+3 + + + = 1 3 2 4 10C C C C C

a a+1 a a+2 a+3 + + + = 1 3 2 4 10C C C C C

a+1 a+1 a+2 a+3 + + = 2 3 4 10C C C C

a+2 a+2 a+3 + = 3 4 10C C C

a+3 a+3 = 4 10C C

Antes de continuar, es conveniente hacer los ejercicios 172 al 177, de la página 180.

Se suman el primer y el tercer sumando, pues tienen el mismo índice superior y el inferior difiere en una unidad. Se sigue sumando hasta que queda una igualdad entre dos números combinatorios. Se investiga la posibilidad de que sean idénticos o complementarios. Si son idénticos: 4$10 (no son idénticos) Si son complementarios: 4 + 10 = a + 3 a = 11

Cumple existencia.

Véase p. 148.


11.1. DEMOSTRACIÓN DE LA FORMULA DE STIFEL POR CONJUNTOS

Caso particular

53C

e i e o e u Pr imer i o subconjunto

i u

o u

e i oe i u Segundoe o u subconjunto

i o u

aaaa

a

a

42

43

C

C

Caso general

a_______a_______ Pr imera_______ subconjunto

.................

a _______(k 1)

________________ Segundo________ subconjunto

................

________(k)

−−

−

−

m 1k 1

m 1k

C

C

Lo que interesa es contar cuántas combinaciones hay en el primer y en el segundo subconjunto. Si en el primer subconjunto no se toma en cuenta el primer elemento a, el número de combinaciones no cambia, pero serán combinaciones de m elementos menos el a, o sea, de (m – 1) y estarán tomadas de (k – 1) (k elementos excepto el a). El segundo conjunto está formado por combinaciones de m elementos excepto el a, o sea, de (m – 1) y están tomadas de k elementos.

Se generaliza el caso anterior, y en lugar de cinco elementos se considera un conjunto de m elementos. Para la demostración de la fórmula de Stifel se forman todas las combinaciones de melementos tomadas de a k. Primero se colocan todas las combinaciones que tienen un elemento en particular. Sea a el elemento que se ubica en primer lugar. Y en el segundo subconjunto, las restantes combinaciones que no tienen el elemento a.

Sea A un conjunto de cinco elementos A= {a, e, i, o, u}. Se formarán todas las combinaciones de estos cinco elementos tomadas de tres en tres. Luego se agrupan en dos conjuntos: Las

que incluyen a, que son: C 42 pues al estar fijo

el a, quedan cuatro letras para cualquiera de los otros dos lugares;

Y las que no incluyen el a, que son: C 43

mkC


Examen 5º Humanístico

Diciembre 1990, Los Vascos

Se da la igualdad: ⎛ ⎞−⎜ ⎟⎝ ⎠∑

=n +2 +1 = an +b

+1=0C C

i i i

iii

i) Hallar a y b si la igualdad se verifica para n = 2 y n = 3. ii) Para los valores de a y b hallados, demostrar t ne n > 0. iii) Empleando la fórmula demostrada en ii), resolver:

x x

x

2= =+1+2 +2 +1 6 = 0

+1+1=0 =0C C C C

⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟− − −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠

⎝ ⎠ ⎝ ⎠∑ ∑

i iii i i

ii iii i


Por lo cual, dado un conjunto de m elementos se cumple:

+ =

m 1k 1C−− + m 1

kC − = mkC

11.2. DEMOSTRACIÓN POR FACTORIAL Si se aplica la fórmula de factorial a cada uno de los números combinatorios de la fórmula de Stifel, es posible efectuar una demostración numérica.

m 1 m 1

+ k 1 kC C− −−

( )(m 1)! (m 1)! k(m 1)! + (m k)(m 1)! (m 1)! (k + m k) + = =

(m k 1)! k! (m k)! k! (m k)! k!m 1 (k 1) ! (k 1)!− − − − − − −

− − − −− − − −

= ( )

m(m 1)! × m m! = = km k ! k! (m k)! k! C−− −

Los pasos para la demostración anterior usando factorial son: a) plantear cada número combinatorio en la suma, en forma de factorial. b) hacer común denominador (m – k)! k! c) sacar de factor común en el numerador a (m – 1)! d) hacer cuentas.

Cantidad de combinaciones que

contienen un elemento determinado

Cantidad de combinaciones que NO

contienen dicho elemento determinado

Cantidad

total de combinaciones


(m – 1) e

(k – 1) e m ≥ (k + 1)

11.3. USO DE STIFEL EN LA RESTA DE COMBINACIONES

Despejando convenientemente, se puede usar Stifel para restar números combinatorios. Para aplicar las fórmulas, téngase en cuenta la relación entre los índices.

m 1mm 1

= kk k 1C C C− −

− − m m 1m 1 = kk 1 kC C C

−−−−

EJEMPLO: Resolver x x x x8 9 11 8 10 1 1 7 2C C C C C+ = − −− + +

NOTA El estudiante debe entender que la mejor manera de sumar o restar números combinatorios es, siempre que se pueda, aplicar la fórmula de Stifel. Para ello se debe preparar la ecuación recordando que:

1) Si es necesario, se deben pasar los números combinatorios de un miembro a otro de la ecuación, para cumplir con las condiciones de la fórmula de Stifel. 2) Recordar siempre el uso de los números combinatorios complementarios (página 164), para tener el número de elementos que se toman en correspondencia con la fórmula de Stifel.

x x x x8 9 11 8 10 1 1 7 2C C C C C+ = − −− + + ? se pasa x

8C al primer miembro.

x x x x8 8 9 11 10 1 1 7 2C C C C C+ + = −− + + ? se suma por Stifel.

x x x9 9 11 10 1 7 2C C C C+ = −+ + ? se pasa x

102C + al primer miembro.

x x10 10 11 + 1 2 7C C C=+ +

x1111

2 7C C=+

Si son idénticas: x + 2 = 7 ? x = 5 Si son complementarias: x + 2 + 7 = 11 ? x = 2

Cumplen existencia.

Véase p. 148.


Obsérvese que las dos soluciones obtenidas cumplen las condiciones de existencia del análisis combinatorio (no siempre es así).

En todos los casos, se resta o se suma aplicando la fórmula de Stifel.

EJEMPLO: Calcular a y b a 3 a 2 a 2 a 3 a 4 + + = b 1 a b 2 b 2 b 3 5

a 4a 4 b bb 3

C C C C CCA P

+ + + + +−+ − + + +++ = + *

La gran mayoría de los sistemas de ecuaciones con números combinatorios se resuelven aplicando la fórmula de Stifel y números combinatorios complementarios. Antes de empezar a sumar o restar por Stifel se debe preparar la ecuación, si es necesario usando las combinaciones complementarias. En la primera ecuación

En lugar del número combinatorio a 2a b 2C +− + se debe poner el complementario a 2

bC +

a 3 a 2 a 2 a 3 a 4 + + = b 1 b b 2 b 3 5C C C C C+ + + + +−+ + +

a 2 a 2 a 3 a 4 + + = b 1 b 2 b 3 5C C C C+ + + ++ + +

a 3 a 3 a 4 + = b 2 b 3 5C C C+ + ++ +

a 4 a 4 = b+3 5C C+ +

En la segunda ecuación En la segunda ecuación del sistema, se obtiene al pasar las permutaciones al primer miembro la fórmula básica para calcular números combinatorios.

a 4a 4 a 4 a 4b b b b 3

b

A C C CP

++ + += → = +

Sistemas a resolver b = 2 –b + a=4 K Solución b = 2 a = 3 K Solución b = 5 a = 9 2b – a = 1 L 2b – a=1


los ejercicios 178 al 191, de la página 181, y contestar las preguntas 8 a 10 de la página 179.

Si son idénticos: b + 3 = 5 ? b = 2 Si son complementarios: b + 3 + 5 = a + 4 ? a – b = 4

SSi son idénticos: b $ b + 3 (no puede ser) KLSi son complementarios: b + b + 3 = a + 4 2b – a = 1


Blaise Pascal. Físico y matemático francés. Nació en Clermont, el 19 de junio de 1623, y falleció de cáncer el 19 de agosto de 1662, a la edad de 39 años, en París. Pascal fue un auténtico niño prodigio que, según se cuenta, siendo muy joven, fue capaz de descubrir por sí solo los treinta y dos teoremas de Euclides y, además, en el orden correcto. Él fue quien divulgó el siguiente triángulo de números combinatorios, a pesar de que ya se encontraba en trabajos de matemáticos chinos del siglo XIII.

12 – TRIÁNGULO DE PASCAL 0

0C

10C 1

1C

20C 2

1C 22C

30C 3

1C 32C 3

3C

40C 4

1C 42C 4

3C 44C

50C 5

1C 52C 5

3C 54C 5

5C

60C 6

1C 62C 6

3C 64C 6

5C 66C

… ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

Cuando se efectúa la potencia enésima de un binomio, es posible comprobar que los coeficientes de cada término siguen el patrón del triángulo de Pascal.

(a + b)0 = 1 (a + b)1 = 1a + 1b

(a + b)2 = 1a2 + 2ab + 1b2 (a + b)3 = 1a3 + 3a2 b + 3ab2 + 1b3

(a + b)4 = 1a4 + 4a3 b + 6a2 b2 + 4ab3 + 1b4 (a + b)5 = 1a5 + 5a4 b + 10a3 b2 + 10a2b3 + 5ab4 + 1b5

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

( ) ∑= n n nna + b = a b= 0

C −ii i

ii


Se suma por Stifel

Se suma por Stifel

Son iguales valen 1

Son iguales valen 1

Se suma por Stifel Demostración

12.1. PROPIEDADES DEL TRIÁNGULO DE PASCAL 1) En cada fila existe una simetría central. Dos números combinatorios de una misma

línea horizontal equidistantes de los extremos son iguales, por ser números combinatorios complementarios.

2) Cada número combinatorio es igual a la suma de los dos que tiene arriba, en la línea anterior, por la fórmula de Stifel.

3) La suma de los números combinatorios de una línea es 2n donde n es el número de elementos del conjunto.

EJEMPLO: para n = 5

50C + 5

1C + 52C + 5

3C + 54C + 5

5C = 25

El caso general se demuestra en la siguiente zona gris, usando inducción completa. Demostrar usando inducción completa que:

t n e nn n n n+ + + ... + = 20 1 2 nC C C C

BASE INDUCTIVA Se debe verificar que la propiedad es cierta para el primer elemento del conjunto.

Para n = 0 00 = 20

=1=1C

PASO INDUCTIVO Hipótesis: La propiedad es cierta para n = h.

hh h h h+ + + ... + = 20 1 2 hC C C C

Tesis: Se debe demostrar que es cierta para el siguiente de h, n = h + 1. h+1h+1 h+1 h+1 h+1 h+1+ + + ... + + = 20 1 2 h h+1C C C C C

−h+1h h h h h h h h+ + + + + ... + + + = 20 0 1 1 2 h 1 h hC C C C C C C C

La anterior igualdad se puede escribir como:

( ) h+1h h h h2 + + + ... + = 20 1 2 hh

por hipótesis = 2

C C C C 2 * 2h = 2h + 1 2h + 1 = 2h + 1


13 – TABLA DE NÚMEROS COMBINATORIOS Resulta ser también una manera de expresar el triángulo de Pascal.

mkC k = 0 k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9

m = 0 1 m = 1 1 1 m = 2 1 2 1 m = 3 1 3 3 1 m = 4 1 4 6 4 1 m = 5 1 5 10 10 5 1 m = 6 1 6 15 20 15 6 1 m = 7 1 7 21 35 35 21 7 1 m = 8 1 8 28 56 70 56 28 8 1 m = 9 1 9 36 84 126 126 84 36 9 1 m = 10 1 10 45 120 210 252 210 120 45 10 m = 11 1 11 55 165 330 462 462 330 165 55 m = 12 1 12 66 220 495 792 924 792 495 220 m = 13 1 13 78 286 715 1287 1716 1716 1287 715 m = 14 1 14 91 364 1001 2002 3003 3432 3003 2002 m = 15 1 15 105 455 1365 3003 5005 6435 6435 5005 m = 16 1 16 120 560 1820 4368 8008 11440 12870 11440 m = 17 1 17 136 680 2380 6188 12376 19448 24310 24310 m = 18 1 18 153 816 3060 8568 18564 31824 43758 48620 m = 19 1 19 171 969 3876 11628 27132 50388 75582 92378 m = 20 1 20 190 1140 4845 15504 38760 77520 125970 167960 m = 21 1 21 210 1330 5985 20349 54264 116280 203490 293930 m = 22 1 22 231 1540 7315 26334 74613 170544 319770 497420 m = 23 1 23 253 1771 8855 33649 100947 245157 490314 817190 m = 24 1 24 276 2024 10626 42504 134596 346104 735471 1307504 m = 25 1 25 300 2300 12650 53130 177100 480700 1081575 2042975 m = 26 1 26 325 2600 14950 65780 230230 657800 1562275 3124550 m = 27 1 27 351 2925 17550 80730 296010 888030 2220075 4686825 m = 28 1 28 378 3276 20475 98280 376740 1184040 3108105 6906900

Examen 5º Humanístico Febrero 1989, Liceo de Solymar

Dado: ≡ 4 3 2a a a+1 a+2 a+3P( ) + + + + b b+1 b b bC C C C Cx x x x x

i) Verificar que el resto de dividir P(x) entre (x – 1) es a+4b+1C

ii) Hallar a y b sabiendo que son números consecutivos y que el resto de la división anterior es igual al doble del término independiente de P(x).

iii) Hallar P(x).



14 – PROBLEMAS DE CONTEO (sin elementos repetidos) Primer paso. El primer paso, y el más difícil, para resolver aquellos problemas en que se pide calcular el número de grupos que se pueden formar con elementos cualesquiera (números, letras, personas, etc) es determinar si se trata de arreglos o de combinaciones. Se debe comprobar si el orden en que se toman los elementos importa o no. Para ello se verá si al tomar algunos elementos del conjunto dado y cambiar el orden, resulta un subconjunto diferente o no.

Caso A. Cuando se trata de palabras o números, es fácil ver que son arreglos, pues al cambiar el orden de las mismas letras o cifras se forman palabras o números diferentes.

lado $ aldo $ dola... 1234 $ 2134 $ 3241...

Caso B. Cuando se trata de personas, libros u otros elementos en los que la importancia del orden es más difícil de detectar, se debe leer la letra del problema con mucha atención. Por ejemplo, cuando se habla de una fila de personas, se indica un orden: hay un primer lugar, un segundo lugar...entonces son arreglos. En cambio, si se habla de un grupo de personas, no se indica ningún orden; tan solo un subconjunto del conjunto principal: son combinaciones.

ALGUNOS EJEMPLOS SIEMPRE SON ARREGLOS: SIEMPRE SON COMBINACIONES: Números Palabras Grupos de personas Fracciones Libros en una valija Vectores Caminos entre dos lugares Personas en fila Productos de cifras Libros en un estante Figuras geométricas Banderas

Segundo paso. Auxiliarse con una representación gráfica del subconjunto a encontrar, colocando una rayita por cada elemento que se toma. Esto ayuda a visualizar cómo se reparten los elementos.

Responder «verdadero» o «falso», y justificar la respuesta.

La cantidad de palabras distintas de cuatro letras que se pueden formar con las letras de la palabra PAPA es 4! Se consideran todas las palabras, tengan o no significado.

Véase el resultado en la página 478.


0

0

02 2

04 4

1

2 0

2 1

EJEMPLO: Con las cifras 0, 1, 2, 3, 4, 5 a) ¿Cuántos números de tres cifras sin repetir se pueden formar? b) De los anteriores, ¿cuántos son pares? c) Si se ordenan de menor a mayor, ¿qué lugar ocupa el 234? a) Son todos los números de tres cifras sin repetir tomados del conjunto dado, menos los que empiezan con cero. Por ejemplo el 045 no es un número de tres cifras; se lee 45. Por ser números importa el orden; son arreglos.

63A 5

2A

63A – 5

2A = 120 – 20 = 100

b) Para que un número sea par debe terminar con una cifra par. Pero deben restarse aquellos números pares que empiezan con cero, ya que no tienen tres cifras significativas.

52A

Los que terminan en cero: ? ? 52A = 20

? 52A 4

1A ? 52A – 4

1A = 16

? 52A 4

1A ? 52A – 4

1A = 16 Resultado = 52 c) ¿Qué lugar ocupa el 234? Significa: cuántos hay antes que el 234 más un lugar. Los menores que 234 son los que empiezan con 1, los que empiezan con 2, y en segundo lugar tienen el 0 o el 1.

52A

Los que empiezan en 1: ? ? 52A = 20

41A


41A


28 +1 por el 234 Resultado: el 234 ocupa el lugar 29

Los que terminan en 2 pero que no comienzan con cero:

Todos Los que empiezan en cero.

Los que terminan en 4 pero que no comienzan con cero:


En un parque nacional hay dispersos varios refugios para guardias, cada uno de los cuales está unido a los restantes por un camino diferente. Calcular el número de refugios, sabiendo que el número de caminos es 36.

Véase el resultado en la página 478. EJEMPLO: ¿Cuántos grupos de tres personas pueden formarse con cinco hombres y siete mujeres, si en cada grupo debe haber, por lo menos, una mujer? Son grupos de personas en donde no se da ningún criterio de orden, por tanto son combinaciones. El significado de «al menos una mujer», se debe tomar como que existen las posibilidades de que los subconjuntos tengan una mujer, dos mujeres o tres mujeres.

mujer hombre hombre Por las mujeres: 71C Por los hombres: 5

2C

mujer mujer hombre Por las mujeres: 72C Por los hombres: 5

1C

mujer mujer mujer Por las mujeres: 73C

Cuando en una misma opción se colocan dos tipos de elementos diferentes, se multiplican y luego se suman las diferentes opciones.

RESULTADO ( 71C * 5

2C ) + ( 72C * 5

1C ) + 73C = 210

Antes de continuar, es conveniente hacer los ejercicios 192 al 208, de la página 182.


Las condiciones de existencia, en el caso de considerar elementos repetidos, son sólo que:

m e k e Pero k puede ser menor, igual o mayor que m. O sea, que se pueden hacer arreglos con repetición, de cualquier orden por grande que sea.

15 – ARREGLOS con repeticiones

15.1. DEFINICIÓN

Dado un conjunto de m elementos, se llamarán arreglos con repetición a los subconjuntos ordenados de k elementos distintos o repetidos, elegidos entre los m dados, considerando como iguales los formados por los mismos objetos repetidos, igual número de veces y en el mismo orden.

NOTACIÓN: mkAR

15.2. FÓRMULA DE CÁLCULO Para comprender mejor los diferentes casos se dará un ejemplo. Dado el conjunto A = {a, b}

20AR 2

1AR 22AR 2

3AR

aa aaa a aab φ ab aba abb ba baa b bab bb bba bbb

m kk mAR =

EJEMPLO: La clave de un candado de combinación tiene 3 dígitos. ¿Cuántas claves distintas hay? Las claves que se pueden formar son arreglos, pues importa el orden de los números. Además, son arreglos con repetición pues, por ejemplo, la clave 666 es válida.

103AR = 103 = 1000 Existen 1000 posibles claves.


Las condiciones de existencia, en el caso de considerar elementos repetidos, son sólo que:

m e k e Pero k puede ser menor, igual o mayor que m. O sea que se pueden hacer combinaciones con repetición, de cualquier orden por grande que sea.

16 – COMBINACIONES con repeticiones

16.1. DEFINICIÓN

Dado un conjunto de m elementos, se llamarán combinaciones con repetición a los subconjuntos de k elementos distintos o repetidos elegidos entre los m dados, considerando como iguales los formados por los mismos objetos, repetidos igual número de veces.

NOTACIÓN mkCR

16.2. FÓRMULA DE CÁLCULO Para comprender mejor los diferentes casos se hará un ejemplo. Dado el conjunto A = {a, b}

20CR 2

1CR 22CR 2

3CR 24CR

aaa aaaa a aa aaab φ aab aabb ab abb abbb b bb bbb bbbb

m m k 1k kCR C + −=

EJEMPLO: ¿De cuántas maneras se pueden comprar cinco pantalones de un mismo modelo, si sólo hay tres colores para elegir? En este caso no existe ningún criterio de orden, por lo tanto son combinaciones. Se desean comprar cinco pantalones, pero se tiene sólo tres colores para elegir, por lo tanto se deberá repetir algún color.

3 5 3 155CR C + −= = 21 De 21 maneras distintas.


17 – ALGUNAS PREGUNTAS SOBRE EL TEÓRICO

1) a) Definir arreglos. b) Deducir la fórmula de arreglos por recurrencia.

c) Calcular: 104A sin usar factorial.

2) a) Determinar los valores de x, para los cuales existe xx

1215A −

−

b) Resolver: y 3 603A + = 3) a) Definir combinaciones de orden 3

b) Explicar: qué es, qué indica y condiciones de existencia de abC

c) Estudiar existencia de a 15C +

4) a) Indicar (sin calcular) si existen los siguientes números:

8 3C 0P 24A 6

2C− 20A 0 0C

b) Investigar en qué condiciones existen: m8C

2n 3n2n 4C

−−

2kP

5) a) Sea A = {2, 3, a, b}. Formar todos los subconjuntos de 2 elementos. b) Determinar el subconjunto complementario de cada uno de los de la parte a). c) Definir combinaciones complementarias de una de orden k.

d) Demostrar m m k m kC C= −

e) Calcular el número combinatorio complementario de: xx

1202C +

6) a) Definir combinaciones complementarias. b) Sean A, B, C, D, y E cinco estudiantes que forman equipos de estudio de

tres estudiantes cada uno. 1) ¿Cuántos equipos se pueden formar? 2) Formar todos los equipos de tres estudiantes y deducir la fórmula general para el número de combinaciones. c) Formar las combinaciones complementarias de las combinaciones de orden tres,

obtenidas en la parte anterior. 7) a) Definir combinaciones. b) Demostrar la fórmula de Stifel.

c) Resolver: x x6 6 7 + 1 2 2C C C=− −

8) a) Completar: 524 = 36 35A A * b) Completar: m m = k 1 kA A+ *

c) En la parte b) dividir ambos miembros por k+1P y obtener una relación entre:

m k 1C + y m kC (recurrencia de los números combinatorios).


18 – EJERCICIOS PROPUESTOS Véanse los resultados en la página 478. Resolver las siguientes ecuaciones en condiciones de existencia:

150) n = 122A 151) n 1 = 562A − 152) n n = 12 67A A

153) p p 14 = 5 3 3A A − 154) n n 22 = 21 23A A − 155) xx 110 = 42A A−

156) Simplificar los siguientes factoriales:

a) 18! 15!

b) 4! 7!

c) 150! 152!

d) n! (n 2)!−

e) (2n)! (2n 3)!−

f) m! (h 1)! h! (m 2)!

−−

** g) 37! (h 1)!

h! 38!−*

* h) (2n 3)! (2n 2)!(2n 1)! (2n 1)!

+ −− +

**

Resolver las siguientes ecuaciones y sistemas de ecuaciones, en condiciones de existencia:

157) 12 105 = 66 n 3n 2A A −− 158) 56 54 = 30800 n 9n 6A A −− 159) x.x x7 7 0

1A A− =−

160) m m(m 5) = m 1m 2A A− −− 161) 1p p 1(p 13) = p 15 p 1345A A +− − −

162)

k 1 k2 = 3 p 1p 1

k k = 7 p 1p

A A

A A

+++

−

163)

m p m p 12 = 5 3 3

12 m 12 m = 4 p 1p

A A

A A

− − −

− −−

164) x3 1 = 212C − 165) n+ 2n n = 35 6C A 166) 2a a 1 = 22 23C C −

167) x x10 10 = 2 3C C+ 168) p p = 7 8C C 169) 20 20 = p 10pC C −

170)

x xy y

x xyy

14 = 1

3 3 = 12 13 1

C C

C C

++

−+

171)

x y x yyy

x xy

= 6

1 = ( 100)1 5

CA

C P

+ +

+ − +−

172) 6 6 7 + = m 1 m 2 2C C C− − 173) x x xx 1 2 + + = 7 8 26C C C C+ +

174) p p p 1 p + + = 11 42 3 2C C C C+ 175) x xx + + 2 = 126 4 2 3C C C


176)

a 7 a 73 = 4 b 1b

a a a+1 + a 11 2a 12

C C

C C C

− −−

=−−

177)

m 2 m 2 m 2 m 2 + = h 4 h 3h h 1

3h m 16

C C C C+ + + ++ +−

+ =

+

178)

p 5 p 3 p 3 p 4 = m2m 1 m 1 2m

2p 2p 6 mm 1

C C C C

A A

+ + + +− ++ +

=+

179)

b 3 b 3 = 4 p 3p 2

p 4 p 4p 4 p+4 + + 7b 3 b 4 p-b+7

C C

C C C C

+ +++

+ ++ =− −

180)

15 15 + = 16a a 1

12n n 1 n-2 = a aa 1 (a +1)!

C C

- - C C C

−

−+

181)

a 7 a 8 a 7 a 7 = 2 a b b 7b 6 b

2b 2b 3 2 3

C C C C

A A P

+ + + +− +− ++

= *

182)

( )

a a a a 12 + = b b 1b b 1

a 1 a 1a 6 + b 3 2

C C C C

C CA

++ −+

− −=

183)

184) n

n 1n 2 3 = 10n + 4 4 9

AC C++

− 185) p 11

p 11p 12 1 7 2 = 87 6 7!

AC C+

++−

186)

3m 1 3m 1 3m 1 3m 3m 12 + = + 2m 1n 4 3m n 2 n 4 3m n 2

4(n 1)(2m + 3)n 2 15

C C C C C

C

− − − +− +− − + − − +

−=

187)

2b 2b = 23

p 8p 7 p 7 b + = p b 1 b 7 b!

C A

A C C+

+ +− − +

188)

a b 21 a b 22a b 21a 20 b 39 + = a 19

a 20 b 39

a b 1310 20

A ACP P

+ + + ++ +− −−

− −

+ =

m mk2m m 1k k + = k 1k 1kk

m k 14

)(A .A C C P P−

− +−

+ =

+


5 b = 10 a > 0 a 3 2C C −+190)

189)

3x 5 3x 5 3x 6 3x 7 3x 8 + + + = y 16 7 3x 2 7

3x 3x y y y 1 16 = 9y

C C C C C

A ACP

+ + + + +−−

+ −

191)

2t 2 2t 1 2t 2t 3 2t + + = 2 2 2 2 22x 1 x x 1 10 2t 3x x 2

2t 1 2t 1 = 2 2x 2x 1

C C C C C

C C

+ + + −+ − + − −

+ +

+

19 – PROBLEMAS PROPUESTOS Véanse los resultados en la página 479. 192) Con los elementos del conjunto {2, 3, 5, 7, 8} a) ¿Cuántos números de cuatro cifras sin repetir se pueden formar? b) ¿De éstos cuántos son pares y cuántos impares? c) ¿Cuántos son menores que 5000? d) ¿Cuántos comienzan con 1? 193) Con las letras de la palabra CUADERNO. a) ¿Cuántas palabras (con o sin sentido) de 5 letras sin repetir, se pueden formar? b) ¿De las anteriores cuántas comienzan con la C y terminan con la O? c) ¿Cuántas terminan con vocal? 194) Se tienen siete cartones numerados del 1 al 7. a) ¿Cuántos números pares de cuatro cifras diferentes se pueden formar? b) ¿Cuántos números de cifras diferentes se pueden formar? c) ¿De cuántas maneras se pueden seleccionar dos cartones diferentes de los siete? 195) a) ¿Cuántos números de cuatro cifras sin repetir se pueden formar con las cifras

0, 2, 3, 4, 5, 6, 7? b) ¿Cuántos de ellos están comprendidos entre 5000 y 6000? c) ¿Cuántos de ellos son múltiplos de 5? d) ¿Cuántos de ellos son múltiplos de 2? 196) En una reunión de 6 personas, ¿cuántos saludos de mano pueden intercambiarse, si

entre cada 2 personas se dan la mano una sola vez? 197) Con las cifras: 0, 2, 3, 5 y 7 a) ¿Cuántos números de 5 cifras sin repetir se pueden formar? b) ¿Cuántos números de 3 cifras sin repetir se pueden formar? 198) Con 6 médicos, ¿cuántas guardias diferentes de 2 médicos cada una se pueden

formar?


199) Dado el conjunto: {2, 3, 5, 7, 11} a) ¿Cuántos productos de dos factores diferentes se pueden formar? b) ¿Y cuántos de tres factores?

c) ¿Cuántas fracciones de la forma ab

a ≠ b, se pueden hacer?

200) Una persona que sale de vacaciones desea llevarse cuatro libros para leer. Dispone de cuatro novelas policiales y seis libros de cuentos cortos.

¿De cuántas formas puede hacer la elección si quiere llevar al menos una novela? 201) Cuatro nadadores van a disputar la final del campeonato mundial. Los premios son: 1.º medalla de oro, 2.º medalla de plata y 3.º medalla de bronce. ¿De cuántas maneras pueden ser distribuidas esas medallas? 202) Cinco chicas y tres muchachos formaron un equipo de cuatro personas. ¿De

cuántas maneras podrán hacerlo, si en cada equipo debe haber por lo menos un muchacho?

203) Un pintor tiene tres colores básicos. a) ¿Cuántos colores distintos obtiene si los mezcla de a dos, en partes iguales?

b) ¿Cuántos obtiene si los mezcla de a dos, pero tomando 23

de un color y 13

de otro color? 204) Dados cinco puntos en el plano no alineados. a) ¿Cuántos segmentos se pueden formar que tengan esos puntos como extremos? b) ¿Cuántos vectores se pueden formar? 205) Se consideran todos los productos de tres factores distintos elegidos entre los

números del conjunto D = {1, 2, 3, – 4, – 5, – 7, – 11} a) ¿Cuántos de ellos son pares y cuántos impares? b) ¿Cuántos son positivos y cuántos negativos? 206) Un equipo deportivo se compone de cuatro mujeres y cuatro varones, de los cuales

una mujer y un varón son hermanos. De cuántas maneras diferentes puede realizarse una presentación en una fila, si…

a) el más alto debe estar en un extremo y el más bajo en el otro. b) el hermano y la hermana deben estar juntos y en ese orden. c) deben aparecer varones y mujeres alternadamente. 207) Una madre que tiene ocho niños desea enviar tres niños a la tienda, dos niños a que

laven los platos y los otros tres niños a jugar. ¿De cuántas maneras puede dividir los niños?

208) Un lago contiene 60 peces. Se sabe que la mitad son rojos, un tercio dorados y un

sexto azules. Dentro del agua se introduce un virus. Una tercera parte de los peces rojos, la mitad de los peces dorados y los cuatro quintos de los peces azules sufren cierta reacción.

a) ¿Cuántos grupos de tres peces se pueden formar? b) ¿Cuántos en que solamente dos peces hayan sufrido la reacción? c) ¿Cuántos que estén formados por mayoría de rojos?

Date post:	08-Aug-2015
Category:	Documents
Upload:	ricardo-lustt
View:	19 times
Download:	0 times

5_08COMBINACIONES_2008

Documents