Download Análisis Combinatorio Archivo

Document related concepts

Permutación wikipedia, lookup

Coeficiente binomial wikipedia, lookup

Conjunto wikipedia, lookup

Grupo simétrico wikipedia, lookup

MinHash wikipedia, lookup

Transcript
03. CONTEOS, METODOS COMBINATORIOS Y CONJUNTOS
ANALISIS COMBINATORIO
Combinaciones, Variaciones y Permutaciones. Para aplicar la Regla de Laplace, el
cálculo de los sucesos favorables y de los sucesos posibles a veces no plantea ningún
problema, ya que son un número reducido y se pueden calcular con facilidad:
a) Combinaciones, determina el número de subgrupos de 1, 2, 3, etc. elementos que
se pueden formar con los n elementos de una nuestra. Cada subgrupo se
diferencia del resto en los elementos que lo componen, sin que influya el orden.
Para calcular el número de combinaciones se aplica
m!
Cm,n 
n!(m  n)!
El termino n! se denomina factorial de n y es la multiplicación de todos los
números que van desde n hasta 1. Ejemplo, 4! = 4*3*2*1 = 24
La expresión Cm,n representa las combinaciones de m elementos, formando
subgrupos de n elementos. Ejemplo, C10,4 son las combinaciones de 10 elementos
agrupándolos en subgrupos de 4 elementos,
C10,4 
10!
 210
4!(10  4)!
Es decir, podríamos formar 210 subgrupos diferentes de 4 elementos, a partir de
los 10 elementos.
b) Variaciones, calcula el número de subgrupos de 1, 2, 3, etc. elementos que se
pueden establecer con los n elementos de una muestra. Cada subgrupo se
diferencia del resto en los elementos que lo componen o en el orden de dichos
elementos (es lo que le diferencia de las combinaciones). Para calcular el número
de variaciones se aplica,
m!
Vm,n 
(m  n)!
La expresión Vm,n representa las variaciones de m elementos, formando
subgrupos de n elementos. En este caso, como vimos en la anterior, un subgrupo
se diferenciará del resto, bien por los elementos que lo forman, o bien por el orden
de dichos elementos. Ejemplo V10,4 son las variaciones de 10 elementos
agrupándolos en subgrupos de 4 elementos,
1
10!
 5.040
(10  4)!
Vm,n 
Es decir, podríamos formar 5.040 subgrupos diferentes de 4 elementos, a partir de
los 10 elementos.
c) Permutaciones, calcula las posibles agrupaciones que se pueden establecer con
todos los elementos de un grupo, por lo tanto, lo que diferencia a cada subgrupo
del resto es el orden de los elementos. Para calcular el número de permutaciones
se aplica,
Pm  n!
La expresión Pm representa las permutaciones de m elementos, tomando todos los
elementos. Los subgrupos se diferenciaran únicamente por el orden de los
elementos. Ejemplo, P10 son las permutaciones de 10 elementos,
Pm  10!  3.628.800
Es decir, tendríamos 3.628.800 formas diferentes de agrupar 10 elementos.
Vamos a analizar ahora que ocurriría con el cálculo de las combinaciones, de las
variaciones o de las permutaciones en el supuesto de que al formar los subgrupos
los elementos pudieran repetirse. Por ejemplo, tenemos bolas de 6 colores
diferentes y queremos formar subgrupos en los que pudiera darse el caso de que 2,
3, 4 o todas las bolas del subgrupo tuvieran el mismo color. En este caso no
podríamos utilizar las fórmulas que vimos en la anterior.
a) Combinaciones con repetición. Para calcular el número de combinaciones con
repetición se aplica,
Cm,n 
(m  n  1)!
n!(m  1)!
Ejemplo, C'10,4 son las combinaciones de 10 elementos con repetición,
agrupándolos en subgrupos de 4, en los que 2, 3 o los 4 elementos podrían estar
repetidos,
C10,4 `
13!
 715
4!9!
Es decir, podríamos formar 715 subgrupos diferentes de 4 elementos.
b) Variaciones con repetición. Para calcular el número de variaciones con
repetición se aplica,
Vm ,n  mn
2
Ejemplo, V'10,4 son las variaciones de 10 elementos con repetición, agrupándolos
en subgrupos de 4 elementos,
 ,4  10 4  10.000
V10
Es decir, podríamos formar 10.000 subgrupos diferentes de 4 elementos.
c) Permutaciones con repetición. Para calcular el número de permutaciones con
repetición se aplica,
Pm ,x1,,xk 
m!
x 1!  x k !
Son permutaciones de m elementos, en los que uno de ellos se repite x 1 veces,
otro x2 veces y así sucesivamente hasta uno que se repite xk veces. Ejemplo,
Calcular las permutaciones de 10 elementos, en los que uno de ellos se repite en 2
ocasiones y otro se repite en 3 ocasiones,
 ,2,3 
P10
10!
 302.400
2!3!
Es decir, tendríamos 302,400 formas diferentes de agrupar estos 10 elementos.
Resumen. En resumen y usando otra nomenclatura para que el lector se habitué a los
demás libros que circulan en el medio.
Combinaciones, variaciones y permutaciones. Se llaman variaciones de n
elementos tomados de m en m a los grupos de m elementos escogidos de los n
elementos de un conjunto, teniendo en cuenta que dos grupos son distintos si difieren
en algún elemento o en el orden de colocación de ellos.
Si los elementos se pueden repetir se llaman variaciones con repetición.
Si m = n se llaman permutaciones de n elementos.
Si el orden no importa se llaman combinaciones.
Variaciones con repetición:
m
son los distintos grupos de m
VRm
n  n
elementos, repetidos o no, que se pueden
formar con n elementos, teniendo en
cuenta el orden.
Combinaciones con repetición:
n!
Combinaciones: Cmn   n  
m
m
son
los
distintos
 m  m!(n  m)! CRn  Cnm1
son los distintos subconjuntos de m subconjuntos de m elementos, repetidos
elementos distintos que se pueden formar o no, que se pueden formar con n
elementos.
con n elementos.
Variaciones:
Vnm  n  (n  1)    (n  m  1) son los
distintos grupos de m elementos distintos
que se pueden formar con n elementos,
teniendo en cuenta el orden.
3
Permutaciones: Pn  Vnn  n! son todas Permutaciones con repetición:
n!
las distintas ordenaciones que se pueden Pnx ,,x 
son las distintas
x 1!  x k !
formar con n elementos, todos distintos.
ordenaciones que se pueden formar con
n elementos, teniendo en cuenta que un
elemento se repite x1 veces, otro x2
veces, ...., etc., siendo x1+x2+......+xk=n.
1
k
4
Muestra A de N elementos
Existen en A elementos
repetidos?
A  y1, y 2 ,, yN 
Si
n objetos de los cuales hay n1 de la clase
1, n2 de la clase 2, …, nk de la clase k,
k
tal que
No
n<N
N   ni
Interesan los subgrupos de tamaño n
i 1
Se toman todos los elementos
En el subgrupo
interesa el orden
de colocación
Si
No
Permutaciones con repetición
Se repite extracción
con devolución?
Si
PxN1,x k 
Muestreo con Reemplazo
No
Muestreo sin Reemplazo
En particular, si
Variación con repetición de n elementos
tomados a la vez
V N
N
n
Interesa el orden
de agrupamiento?
n
x1  x 2    x k
PN  N !
entonces,
Si
Permutación Circular
No
N!
x 1!x 2 !  x k !
PN  (N  1)!
Combinaciones sin repetir
Combinación con repetición de N
elementos tomados de a n
 N  1
(N  1)!
 
C  
 n  n!(N  n)!
N
n
N
N!
CNn    
 n  n!(N  n)!
Combinaciones con repetición
 N  n  1

C  
 n

N
n
N elementos con n repetidos
VnN  N! / n!
Variación simple de N elementos
tomados de a n sin repetir
V nN 
N!
( N  n )!
5
Existen en A elementos
repetidos?
EJERCICIOS DE APLICACIÓN
Si
No
n<N
Interesan los subgrupos de tamaño n
Se tienen en una bolsa el siguiente número de
bolas: 4 rojas, 3 blancas y 2 amarillas. Cuán-tas
permutaciones con repetición se pueden hacer?
k
N  ni  4  3  2  9 bolas
i 1
Si
En el subgrupo
interesa el orden
de colocación
P xN1 , x k 
Se repite extracción
con devolución?
Si
Muestreo con Reemplazo
Interesa el orden
de agrupamiento?
Cuántas palabras se pueden formar con la
palabra BOOK de a dos letras, considreando
que las O no repetidas y si repetidas?
V nN  N n  4 2  16
Tomar 2 boletos CON repetir dentro de 20
que hay en una bolsa CON Orden
En particular, si se clasifican las bolas
PN  N !  9!
No
Muestreo sin Reemplazo
No
No
De cuántas formas sentar 4 personas en una
silla?
PN  N !  4!
Si
Se tienen 5 personas jugando bridge en una
mes. De cuántas formas se puede repartir?
PN  (N  1)!  4!
Tomar 2 boletos sin repetir dentro de 20 que
hay en una bolsa SIN Orden
N
N!
20!
CNn    

n
n
!

(
N

n
)!
2
!*
18!
 
N  1
(N  1)!
21!
 
CNn  

n
n
!

(
N

n
)!
2
!*
18!


Cuántos comités de 2 quimicos y 1 físico se
forman con 4 quimicos y 3 físicos?
 N  n  1  6 
   Circularmente o
CNn  
 n
 2
también,
 4  3 
  no circularmente
 2 1 
9!
4 ! 3 ! 2!
Cuántas palabras se pueden formar con la
palabra BOOK de a dos letras, considreando
que las O no repetidas y si repetidas?
V nN  N! / n!  4! / 2!  12
V nN  4 2  16
Tomar dos boletos entre 20 que existen en una
bolsa sin repetir CON orden
VnN 
N!
20!

 20*19
(Nn)! 18!
6
TÉCNICAS DE CONTEO
Listas. Una lista es una sucesión ordenada de objetos, se escriben entre paréntesis y
separando los elementos por comas. Por ejemplo la lista (1,2,3,Ζ) es una lista cuyo
primer elemento es el 1, el segundo el 2, el tercer elemento es el 3 y el cuarto
elemento es el conjunto de los números enteros. El orden en que aparecen los
elementos en una lista es de suma importancia, así la lista (2,4,6) es diferente de la
lista (6,4,2) y de la lista (4,2,6) sin importar que los elementos sean los mismos. Los
elementos en una lista pueden repetirse como en (2,2,3). La longitud de una lista es
la cantidad de elementos que tiene la lista, así en todos los ejemplos anteriores la
longitud es de tres, mientras que la lista (2,4,6,8) tiene una longitud de cuatro. Una
lista de longitud dos tiene el nombre especial de par ordenado.
Ejemplo. Se desea hacer una lista de dos elementos, en los lugares de la lista pueden
estar cualquiera de los dígitos 2, 4, 6 o 8. ¿Cuántas listas con estas características son
posibles?. La forma más directa de responder es escribiendo todas las posibilidades:
(2,2)
(2,4)
(2,6)
(2,8)
(4,2)
(4,4)
(4,6)
(4,8)
(6,2)
(6,4)
(6,6)
(6,8)
(8,2)
(8,4)
(8,6)
(8,8)
Hay 16 elementos posibles.
Supongamos que los elementos posibles en la primera posición de la lista son los
enteros del 1 al n y los posibles para la segunda posición son los enteros del 1 al m.
Como antes tenemos la siguiente tabla con las diferentes posibilidades:
(1,1)
(1,2)
(1,3) ... (1,m)
(2,1)
(2,2)
(2,3) ... (2,m)
(3,1)
(3,2)
(3,3) ... (3,m)
.
.
. .
:
:
: :
(n,1)
(n,2)
(n,3) ... (n,m)
Hay n filas o renglones (con el primer elemento igual en cada una de las listas), y
cada fila contiene m listas. Por consiguiente la cantidad de listas posibles es:
m + m + m +...+ m = m * n
n veces
Principio de Multiplicación. Si una operación se puede realizar en n1 formas, y sí
por cada una de estas formas una segunda operación se puede realizar de n 2 formas,
entonces, las dos operaciones se pueden realizar juntas de n1*n2 formas.
Consideremos listas de dos elementos en las que hay n opciones para la primera
7
posición, y cada opción del primer elemento tiene m opciones para el segundo
elemento. Entonces la cantidad de estas listas es de nm.
Ejemplo. Una persona tiene disponible 4 camisas y 3 pantalones. Al levantarse en la
mañana esta selecciona una camisa y un pantalón cualquiera para vestirse. ¿De
cuántas formas puede resultar vestida la persona? Aquí la actividad que se efectúa es
que la persona se viste. Esta actividad consiste de dos partes, la primera en
seleccionar el pantalón y la segunda en seleccionar la camisa. Como puede
seleccionar el pantalón en una de n=3 formas y por cada pantalón seleccionado puede
escoger una de m=4 camisas este puede resultar vestido en una de nm = 4*3 = 12
formas diferentes.
Ejemplo, Las iniciales de una persona (suponiendo que sólo nos interesa el primer
nombre así tenga segundo nombre) son las listas formadas por las iniciales de su
nombre y su apellido (primer apellido).
- ¿De cuántas formas se pueden escribir las iniciales de las personas?
- ¿De cuántas formas se pueden escribir las iniciales en las que las dos letras que no
se repitan? (Por ejemplo CC de Carmen Cardona no se permitiría).
El alfabeto es de 26 letras tendremos estos 26 elementos para la primera posición de
cada lista y así mismo 26 opciones para la segunda posición, luego hay 262 = 676
listas posibles.
b. La segunda pregunta pide la cantidad de listas de dos elementos, habiendo 26
opciones para el primer elemento (n=26) y para cada una de ellas, 25 opciones para el
segundo (m=25). Por consiguiente hay 26 * 25 listas.
Ejemplo, Un club tiene 15 miembros. Desean elegir un presidente y alguien más
como vicepresidente. ¿De cuántas formas pueden llenarse esos cargos?. Al reformular
la pregunta como una de conteo de listas, tenemos: ¿Cuántas listas de dos elementos
se pueden formar en las que dos elementos sean personas seleccionadas de un total de
15 candidatos y que la misma persona no se seleccione dos veces (no esté repetida)?.
Hay 15 opciones para el primer elemento de la lista (primera posición, n=15) y para
cada una de estas (para cada presidente) hay 14 opciones (m=14) para el segundo
elemento de la lista (el vicepresidente). Según el principio de la multiplicación, hay
15 X 14 (nm) posibilidades.
Listas de más de dos elementos. El principio de la multiplicación se puede aplicar a
listas más largas. Pensemos en las listas de tres elementos o longitud tres.
Supongamos que hay a opciones para el primer elemento, para cada uno de estos hay
b opciones para el segundo elemento y para cada opción del par formado por el
primer y segundo elemento hay c opciones para el tercer elemento. De esta forma hay
en total abc listas posibles. Una forma provechosa de imaginar problemas de conteo
de listas es hacer un diagrama con cuadros.
8
Cada cuadro representa una posición en la lista. Escribimos la cantidad de elementos
posibles en cada cuadro. El total de listas posibles se calcula multiplicando entre sí
esas cantidades.
Ejemplo, Hay un club con 15 socios. Se desea elegir una mesa directiva formada por
un presidente, un vicepresidente, un secretario y un tesorero. ¿De cuántas maneras se
puede hacer la elección, suponiendo que un socio puede ocupar sólo un cargo?.
Trazamos el siguiente diagrama:
15
14
13
12
Esto nos muestra que hay 15 socios para elegir el presidente. Una vez seleccionado el
presidente quedan 14 socios para ser elegidos como vicepresidente y en consecuencia
hay 15*14 formas de elegir al presidente y al vicepresidente. Una vez elegidos, hay
13 formas de elegir al tercer elemento (el secretario). Una vez elegidos los tres
primeros cargos quedarán 12 socios para elegir entre estos al tesorero. En
consecuencia hay 15*14*13*12 formas de seleccionar la mesa directiva.
Principio Básico de Conteo Generalizado. Supongamos que vamos a efectuar una
actividad que se compone de k partes. La primera parte puede resultar en uno de n1
resultados posibles. Para cada uno de los posibles resultados de la primera parte, la
segunda parte puede resultar en uno de n2 resultados posibles. En general, para cada
una de los posibles resultados de las partes anteriores, la i-ésima parte puede resultar
en uno de ni resultados distintos. Entonces el total de resultados de la actividad es
n1n2n3...nk .
Principio del palomar. El principio del palomar establece que si n palomas se
distribuyen en m palomares, y si n > m, entonces al menos habrá un palomar con más
de una paloma. Otra forma de decirlo es que m huecos pueden albergar como mucho
m objetos si cada uno de los objetos está en un hueco distinto, así que el hecho de
añadir otro objeto fuerza a volver a utilizar alguno de los huecos. De otra manera: si
se toman trece personas, al menos dos habrán nacido el mismo mes. Aunque el
principio del palomar puede parecer una observación trivial, se puede utilizar para
demostrar resultados inesperados. Por ejemplo, tiene que haber por lo menos dos
personas en Medellín con el mismo número de pelos en la cabeza.
Demostración: la cabeza de una persona tiene en torno a 150.000 cabellos. Es
razonable suponer que nadie tiene más de un millón de pelos en la cabeza. Hay más
de un millón de personas en Medellín. Si asignamos un palomar por cada número de
0 a 1.000.000, y asignamos una paloma a cada persona que irá al palomar
correspondiente al número de pelos que tiene en la cabeza, al menos habrá dos
personas con el mismo número de pelos en la cabeza.
9
Una versión generalizada de este principio dice que, si n objetos discretos deben
guardarse en m cajas, al menos una caja debe contener no menos de n/m objetos. En
el ejemplo anterior, si suponemos que Medellín tiene 3.100.000 habitantes, entonces
habrá al menos 4 personas que tengan el mismo número de pelos en la cabeza.
Coeficientes Binomiales. Dado un conjunto X con n elementos, el número de
subconjuntos de X que tienen k elementos es el coeficiente binomial de n en k y se
n
denota como C(n,k) o como  
k
El número C(n,k) es también llamado combinaciones de n en k. Otra notación común
es Cnk. Dado que un conjunto de k elementos se puede permutar en k! posibles
formas, se tiene la siguiente identidad que relaciona permutaciones y combinaciones,
C(n, k )  k! P(n, k )
de la cual se puede deducir la expresión para calcular directamente C(n,k),
n
n!
  
 k  k!(n  k )!
en donde k≤2n.
El nombre de coeficiente binomial proviene del hecho que las combinaciones de n en
k son los coeficientes que aparecen al desarrollar un binomio a la n-ésima potencia,
resultado que fue establecido por Isaac Newton:
n
n
a  bn    a n k b k
i 1  k 
Ejemplo,
 4
 4
 4
 4
 4
(a  b) 4   a 4 b 0   a 3 b1   a 2 b 2   a 1 b 3   a 0 b 4 
0
1 
 2
3 
 4
 a 4  4a 3 b  6a 2 b 2  4ab 3  b 4
Es el coeficiente numérico del (b + 1)-ésimo término de la expansión de un binomio a
través del teorema del binomio, y de ahí su nombre. Los coeficientes binomiales
cumplen una gran variedad de identidades combinatorias. Algunas de ellas son
n n
n n

      1
   

0  n
k n  k
El significado combinatorio de la identidad anterior, es que determinar un
subconjunto con k elementos equivale a determinar el complemento de n-k elementos
10
y por tanto hay la misma cantidad de subconjuntos con k elementos que subconjuntos
con n-k elementos.
 n   n   n  1
   
  

 k   k  1  k  1
La identidad anterior se conoce como Teorema de Pascal y es también la regla que
permite la construcción del Triángulo de Tartaglia, en donde se obtienen los
coeficientes del binomio
n
n n n
n
            2 n

k 0  k 
 0  1 
n
La identidad se puede obtener por el Teorema del Binomio al desarrollar (1+1)n, pero
el significado combinatorio es que el conjunto potencia de un conjunto con n
elementos tiene 2n elementos.
Principio de Adición. Si una operación se puede realizar en n1 formas, y sí por cada
una de estas formas una segunda operación se puede realizar de n2 formas, sin que las
primeras tengan que darse para la ocurrencia de las segundas, entonces, las dos
operaciones se pueden realizar juntas de n1+n2 formas.
Principio fundamental de conteo. Si un suceso A presenta n1 maneras diferentes y
una vez este suceso ha ocurrido un segundo suceso B se puede presentar en n 2
maneras diferentes y así cuando ha ocurrido este, sucede un tercer suceso C que se
puede presentar en n3 maneras diferentes y así diferentes sucesos en nk formas,
entonces el número total de maneras diferentes como pueden darse simultáneamente
los sucesos es,
n1  n 2  n3    nk
11
Coeficientes Multinomiales. Supongamos que 20 miembros de una organización se
dividirán en tres comités: Reglamento, Presupuesto, Actividades. Los comités de
Reglamento y de Presupuesto tendrán 8 miembros cada uno y el comité de
Actividades tendrá 4. ¿De cuántas maneras se pueden asignar los miembros a esos
comités?
Dividimos esta tarea en tres partes. Primero seleccionamos los miembros del comité
de Reglamento. Esto puede hacerse de 20C8 formas distintas. Una vez seleccionados
los miembros de ese comité, procedemos a seleccionar miembros del comité de
Presupuesto. Ahora sólo quedan 12 miembros de la organización disponibles, por lo
cual el número de formas de seleccionar los miembros del comité de Presupuesto es
12C8. De paso hemos seleccionado los miembros del comité de Actividades, pues lo
constituyen las 4 personas que quedan. Usando el coeficiente binomial, esto se puede
hacer de 4C4 formas distintas. Usamos el principio básico de conteo para obtener el
resultado. Entonces el número de maneras de asignar los miembros a los comités es
 20 12  4 
20 C 8 *12 C 8 *4 C 4  
 8  8  4   62.355.150 
   
En general, tenemos n elementos distintos que deben ser divididos en k 2 grupos de
manera tal que para j = 1, 2 ,…k, el j-ésimo grupo tiene exactamento nj elementos,
donde n1 + n2 +…+ nk = n.
Deseamos determinar el número de formas en que los n elementos pueden dividirse
en los k grupos. Para lograr esto hacemos uso del principio básico de conteo. Los nj
n 
elementos del primer grupo pueden seleccionarse de los n disponibles en  
 n1 
formas. Luego de esto quedan n - n1 elementos disponibles. De éstos se seleccionan
 n  n1 
 formas distintas,
los n2 miembros del segundo grupo, lo cual se puede hacer 
 n2 
quedando entonces n - n1- n2 elementos disponibles. Continuamos seleccionando el
tercer grupo de esta misma manera y así sucesivamente. Finalmente, el número de
maneras de seleccionar los k grupos es:
n
 n  n  n 1  n  n 1  n 2  n  n 1  n k 1 


n!


 
 

 
n3
nk
 n 1  n 2 
 n 1!n 2 ! n k !  n 1 , n 2 ,, n k 

Esta última expresión se conoce como un coeficiente multinomial, ya que aparece en
el teorema multinomial¨Para cualquier números reales x1, x2, … xk y un número
n

 n1 n 2
x 1 x 2  x nk k ,
entero positivo n, tenemos ( x 1  x 2    x k ) n   
 n 1 , n 2 , , n k 
12
donde la sumatoria se extiende sobre todas los enteros no negativos n1, n2, … nk tal
que n1 + n2 +…+ nk = n.
Variaciones sin repetición. En una carrera de carros participan 20 corredores.
Teniendo en cuenta que no es posible llegar la mismo tiempo, de cuántas maneras
podrán llegar a la meta los tres primeros?
Los veinte corredores son m1,m2,...,m20. Para la primera posición (campeón) hay 20
posibilidades; para la segunda posición (subcampeón) hay 19 posibilidades, y para el
tercer puesto hay 18 posibilidades. Observamos el diagrama de árbol del margen, por
tanto, hay 20*19*18=6840 formas distintas de quedar los tres primeros clasificados.
A estos distintos grupos ordenados de tres corredores, elegidos de entre los 20 que
tenemos, lo llamaremos variaciones de 20 elementos tomando de a tres cada vez
Variaciones ordinarias o variaciones sin repetición. de n elementos tomados m cada
vez (m≤n) son los distintos grupos o listas que se pueden formar con los n elementos,
de manera que en cada grupo entren m elementos distintos, y dos grupos son distintos
si se diferencian en algún elemento o en el orden de colocación de éstos. El número
de variaciones ordinarias de n elementos tomando m cada vez se representa por Vn,m
Número de variaciones ordinarias. Hemos obtenido el número de formas de
clasificarse 20 corredores para obtener los tres primeros puestos: 20*19*18. En
general, si hallamos el número de variaciones sin repetición que se pueden formar
con n elementos tomados m a m, obtendremos, Vn,m = n*(n-1)*(n-2)*...*(n-m+1)
Ejemplo, V3,2= 3*2 = 6 que podría ser un grupo de tres socios, por ejemplo Abe (A),
Diego (D) y Ver (V) entre los cuales se van a designar dos cargos importantes:
13
Representante Legal y tesorero. Si la primera posición es para el Representante legal
y la segunda para el tesorero tenemos las siguientes posibilidades:
(A,D), (A,V) (D,A), (D,V) (V,A),(V,D)
Para este caso siempre quedaría uno de ellos sin un cargo, porque son 3 elementos
(n=3) tomados 2 cada vez (m=2). Si todos quieren quedar con un cargo, digamos
ahora que entre los 3 socios (n=3) se van a elegir como Presidente de la Mesa
directiva y los cargos de Representante Legal y tesorero. En este caso tenemos V3,3
así, V3,3 = 3·2·1=6 también 6 posibilidades, pero ahora tenemos:
(A,D,V), (A,V,D)
(D,A,V), (D,V,A)
(V,A,D), (V,D,A)
y así cada uno de los socios tiene un cargo y estarán felices.
¿Cuántos números de tres cifras se pueden formar con los dígitos 1,2, 3, 4, 5, 6, 7, 8 y
9 sin que se repita ninguna cifra?. Como el número 123 es diferente del número 321,
luego influye el orden y además no se puede repetir ninguna cifra. Por lo tanto
debemos calcular el número de variaciones de nueve elementos (n=9) tomando tres
cada vez (m=3), V9,3 = 9·8·7 = 504 números distintos.
Variaciones con repetición. Lanzamos cuatro veces consecutivas una moneda
obteniendo en cada caso una Cara (C) o Sello (S). Cuántos resultados distintos
podremos obtener?
UNO
LANZAMIENTO
DOS
TRES
C
C
S
C
C
S
S
C
C
S
S
C
S
S
CUATRO
C
S
C
S
C
S
C
S
C
S
C
S
C
S
C
S
RESULTADO
CCCC
CCCS
CCSC
CCSS
CSCC
CSCS
CSSC
CSSS
SCCC
SCCS
SCSC
SCSS
SSCC
SSCS
SSSC
SSSS
Las distintas ordenaciones que acabamos de obtener se llaman variaciones con
repetición de dos elementos tomados de a cuatro cada vez. Observamos que ahora
sigue influyendo el orden, como en el caso anterior, pero además los elementos se
pueden repetir
14
Variaciones con repetición de n elementos tomados m cada vez (m≤n) son los
distintos grupos o listas que se pueden formar con los n elementos, de manera que en
cada grupo entren m elementos, repetidos o no, y dos grupos son distintos si se
diferencian en algún elemento o en el orden de colocación de éstos.
El número de variaciones con repetición de n elementos tomando m cada vez se
representa por VRn,m.
Número de Variaciones con Repetición. Hemos hallado el número de resultados
distintos que se obtienen al lanzar cuatro veces una moneda: 2 · 2 · 2 · 2 = 2 4 = 16.
De la misma forma, podemos hallar el número de resultados distintos que se obtienen
al lanzar:
- Una vez una moneda
2
- Dos veces una moneda
2 · 2 = 22 = 4
- Tres veces una moneda
2 · 2 · 2 = 23 = 8
- Cinco veces una moneda 2 · 2 · 2 · 2 = 25.= 32
- En n veces una moneda
2 · 2 · 2... · 2 = 2n.
En general si queremos hallar el número de variaciones con repetición que se pueden
formar con n elementos tomados de a m cada vez, obtendremos
VRn,m = n · n · n ·... n = nm
m factores
¿Cuántos números de tres cifras se pueden formar con los dígitos 0, 1, 2, 3, 4, 5, 6, 7,
8 y 9 si se pueden repetir las cifras?. Tenemos que hallar el número de variaciones
con repetición de 10 elementos tomados de a tres, es decir, VR10,3 = 103 = 1000
Ahora bien, de estos 1000 números habrá muchos que inicien con cero como por
ejemplo 035, 099, 001 por lo cual no se pueden considerar de tres cifras. Por esto
debemos descontar estos números, y tendremos:
VR10,3 - VR10,2 = 103 - 102 = 1000 - 100 = 900
Ejemplo, Se lanzan tres dados de distintos colores una vez. ¿Cuántos resultados
distintos se pueden obtener?. Son VR6,3 = 63 = 216 resultados diferentes.
Algunas veces queremos saber cuántos arreglos podemos obtener con un grupo de
elementos, para ello podemos utilizar la técnica conocida como permutación que
veremos a continuación en el siguiente tema.
Permutación. Hasta aquí hemos contado listas de elementos de diversas longitudes,
en las que permitimos o prohibimos la repetición de los elementos. Un caso especial
de este problema es contar las listas de longitud n formadas por un conjunto de n
15
objetos, en las que se prohíbe la repetición. En otras palabras, se desea tener n objetos
en listas, usando cada objeto exactamente una vez en cada lista. Según el principio de
la multiplicación, la cantidad de listas posibles es de:
(n)n = n*(n-1)*(n-2)*...*2*1
Arreglos que se puedan distinguir, Si se quieren arreglar objetos, donde todos los
objetos sean diferentes entre sí, la permutación (el número de arreglos que se pueden
obtener) es n!
Ejemplo, Cinco amigos que están en una piscina, después de haberse lanzado por el
deslizadero gigante, observan que cada vez que llegan a la parte superior para el
nuevo lanzamiento hacen cola en distinto orden. ¿De cuántas formas podrán hacer
cola para arrojarse de nuevo?
Observe que para la primera posición hay cinco personas, cuatro para la segunda, etc.
De esta forma tenemos que el número de formas distintas de hacer cola es, V5,5 = 5! =
5·4·3·2·1 = 120
Como observamos, en este caso intervienen a la vez todos los elementos y
únicamente varía el orden de colocación.
Ejemplo, Queremos permutar (arreglar) las letras abc. Cuáles arreglos se obtienen?
abc, acb, bac, bca, cab y cba. Son 6 permutaciones diferentes. También hubiéramos
podido decir son 3 letras diferentes a, b y c por lo tanto son 3! permutaciones, o sea
3*2*1=6
Vemos que hay efectivamente 3 opciones para la primera posición (cualquiera de las
letras a, b o c, luego quedan sólo dos opciones para la segunda posición (por ejemplo
si se escogió a para la primera posición, quedarían b o c para la segunda posición), y
quedaría una sola letra para la tercera posición.
16
Permutaciones ordinarias de n elementos son los distintos grupos que se pueden
formar de manera que:
- En cada grupo (o lista) están los n elementos.
- Un grupo se diferencia de otro únicamente en el orden de colocación de los
elementos.
El número de permutaciones ordinarias de n elementos se representa por Pn y es igual
a n!
Ejemplo, En un campeonato suramericano de Fútbol llegan a un cuadrangular final
los cuatro seleccionados de Brasil, Argentina, Colombia y Uruguay. Formar las
diferentes clasificaciones para los cuatro primeros puestos del torneo. ¿Cuántas hay?
Representamos por sus iniciales a cada seleccionado y mediante un diagrama de árbol
se obtiene:
De aquí vemos que hay P4 = 4! = 4·3·2·1 = 24 clasificaciones distintas.
Las variaciones sin repetición también se pueden representar con factoriales, según:
Si se quieren arreglar n objetos diferentes, pero se van a tomar r objetos de ellos los
cuales son distinguibles entre sí, entonces:
m
VRm
n  n
Ejemplo, De cuántas formas puede cespro.com colocar a 3 programadores de
sistemas en 3 diferentes ciudades. Si los programadores están disponibles para
cualquiera de 5 ciudades.
17
Entonces se tienen 3 programadores disponibles pero hay 5 posibles ciudades a donde
ellos pueden ir. ¿De cuántas formas podríamos ubicarlos?. Tenemos 60 formas
posibles de ubicarlos en las 5 ciudades. Parece que de todos modos va tocar pensar
bien dónde ubicarlos...
Ejemplo, ¿Cuántas palabras se pueden formar con ocho letras de forma que dos de
ellas estén siempre juntas y guardando el mismo orden?
Como las dos letras siempre van a estar juntas y en el mismo orden, las podemos
considerar como si fuera una sola letra. Por esta razón es una permutación realmente
de sólo siete elementos:
P7 = 7! = 7·6·5·4·3·2·1 = 5040 palabras diferentes
Ejemplo: ¿De cuántas formas se pueden sentar nueve personas en una mesa circular?
Hay que tener en cuenta que una vez sentadas, si trasladamos a cada persona un
asiento a la izquierda obtendremos una posición idéntica a la anterior. Por ello
dejamos fija una persona y permutamos todas las demás:
P8 = 8! = 8·7·6·5·4·3·2·1 = 40320 formas distintas
A estas permutaciones se las denomina permutaciones circulares de n elementos y se
representan por PCn.
Permutaciones con repetición. Si se quiere permutar (arreglar) objetos, dentro de los
cuales hay varios repetidos, entonces se pueden contar las posibilidades de arreglos
diferentes,
Pnx1,,xk 
n!
x 1!  x k !
Ejemplo, Supongamos que queremos hacer un arreglo de luces, con 4 bombillas
amarillas, 3 bombillas azules y 3 rojas. En total se tienen 10 bombillas. Pero, ¿qué
arreglos de colores puedo tener?.
Ejemplo, Imaginemos que tenemos 5 monedas de 100 centavos, de las cuales dos
están en posición de cara y tres en posición de Sello. ¿Cuántas ordenaciones
diferentes podremos formar en las que siempre estén dos en posición de cara y tres en
posición de Sello?
Las ordenaciones posibles son: (CCSSS, CSCSS, CSSCS, CSSSC, SCCSS, SCSCS,
SCSSC, SSCCS, SSCSC, SSSCC)
CONJUNTOS
La palabra conjunto generalmente la asociamos con la idea de agrupar objetos, por ejemplo
un conjunto de discos, de libros, de plantas de cultivo y en otras ocasiones en palabras como
18
hato, rebaño, piara, parcelas, campesinado, familia, etc., es decir la palabra conjunto denota
una colección de elementos claramente entre sí, que guardan alguna característica en
común. Ya sean números, personas, figuras, ideas y conceptos.
En matemáticas el concepto de conjunto es considerado primitivo y ni se da una definición
de este, sino que se trabaja con la notación de colección y agrupamiento de objetos, lo
mismo puede decirse que se consideren primitivas las ideas de elemento y pertenencia.
La característica esencial de un conjunto es la de estar bien definido, es decir que dado un
objeto particular, determinar si este pertenece o no al conjunto. Por ejemplo si se considera
el conjunto de los números dígitos, sabemos que el 3 pertenece al conjunto, pero el 19 no.
Por otro lado el conjunto de las bellas obras musicales no es un conjunto bien definido,
puesto que diferentes personas puedan incluir distintas obras en el conjunto.
Los objetos que forman un conjunto son llamados miembros o elementos. Por ejemplo el
conjunto de las letras de alfabeto; a, b, c, ..., x, y, z. que se puede escribir así: { a, b, c, ..., x,
y, z}
Como se muestra el conjunto se escribe entre llaves ({}) , o separados por comas (,).
El detallar a todos los elementos de un conjunto entre las llaves, se denomina forma tabular,
extensión o enumeración de los elementos.
Dos conjuntos son iguales si tienen los mismos elementos, por ejemplo:
El conjunto { a, b, c } también puede escribirse:
{ a, c, b }, { b, a, c }, { b, c, a }, { c, a, b }, { c, b, a }
En teoría de conjuntos se acostumbra no repetir a los elementos por ejemplo:
El conjunto { b, b, b, d, d } simplemente será { b, d }.
Denotación. Los conjuntos se denotan por letras mayúsculas : A, B, C,... por ejemplo: A={ a,
c, b }
B={ primavera, verano, otoño, invierno }
El símbolo  indicará que un elemento pertenece o es miembro de un conjunto. Por el
contrario para indicar que un elemento no pertenece al conjunto de referencia, bastará
cancelarlo con una raya inclinada / quedando el símbolo como  .
Ejemplo: Sea B={ a, e, i, o, u }, a B y c  B
SUBCONJUNTO
Sean los conjuntos A={ 0, 1, 2, 3, 5, 8 } y B={ 1, 2, 5 }
19
En este caso decimos que B esta contenido en A, o que B es subconjunto de A. En general
si A y B son dos conjuntos cualesquiera, decimos que B es un subconjunto de A si todo
elemento de B lo es de A también.
Por lo tanto si B es un subconjunto de A se escribe B  A. Si B no es subconjunto de A se
indicará con una diagonal  .
Note que  se utiliza solo para elementos de un conjunto y  solo para conjuntos.
UNIVERSO O CONJUNTO UNIVERSAL El conjunto que contiene a todos los elementos a
los que se hace referencia recibe el nombre de conjunto Universal, este conjunto depende
del problema que se estudia, se denota con la letra U y algunas veces con la letra S (espacio
muestral).
Por ejemplo si solo queremos referirnos a los 5 primeros números naturales el conjunto
queda:
U={ 1, 2, 3, 4, 5 }
Forma alternativa para indicar conjuntos de gran importancia:
 Conjunto de números naturales (enteros mayores que cero) representados por la letra N donde




N={ 1, 2, 3, .... }
Conjunto de números enteros positivos y negativos representados por la letra Z donde
Z={..., -2, -1, 0, 1, 2, ... }
Conjunto de números racionales (números que se representan como el cociente de dos números
enteros {fracciones }). Estos números se representan por una Q
Conjunto de números irracionales (números que no puedan representarse como el cociente de dos
números enteros) representados por la letra I.
Conjunto de los números reales que son los números racionales e irracionales es decir todos,
representados por R.
Todos estos conjuntos tienen un número infinito de elementos, la forma de simbolizarlos por
extensión o por enumeración es de gran utilidad cuando los conjuntos a los que se hace
referencia tienen pocos elementos para poder trabajar con ellos se emplean la notación
llamada comprehensión.
Por ejemplo, la denotar el conjunto de los números naturales menores que 60. Aquí U es el
conjunto N y se tiene una propiedad que caracteriza a los elementos del conjunto: ser
menores que 60.
Para indicar esta situación empleamos la simbología del álgebra de conjuntos: { x/x  N ;
x<60 }
20
En esta expresión se maneja un conjunto de x que pertenece a los números naturales (N) y
además que los valores de x son menores que 60. Ahora si se desea trabajar con conjuntos
que manejen intervalos estos pueden ser representados por medio de una expresión
algebraica; supongamos que se desea expresar los números enteros (Z) entre -20 y 30 el
conjunto quedaría de la manera siguiente:
{ x/x  Z ; -20  x  30 }
También se puede expresar el valor de un conjunto indicando la pertenencia o no
pertenencia a uno diferente, por ejemplo
L={ 1, 3, 4, 6, 9 }
P={ x/x  N ; X  L }
En el conjunto P se indica que los elementos x de un conjunto pertenecen a los números
naturales y además x no pertenece al conjunto L.
OPERACIONES CON CONJUNTOS
UNION. La unión de dos conjuntos A y B la denotaremos por A  B y es el conjunto formado
por los elementos que pertenecen al menos a uno de ellos ó a los dos. Lo que se denota por:
A  B = { x/x  A ó x  B }
Ejemplo: Sean los conjuntos A={ 1, 3, 5, 7, 9 } y B={ 10, 11, 12 }
A  B ={ 1, 3, 5, 7, 9, 10, 11, 12 }
INTERSECCION Sean A={ 1, 2, 3, 4, 5, 6, 8, 9 } y B={ 2, 4, 8, 12 } Los elementos comunes a
los dos conjuntos son: { 2, 4, 8 }. A este conjunto se le llama intersección de A y B; y se
denota por A  B, algebraicamente se escribe así: A  B = { x/x  A y x  B } Y se lee el
conjunto de elementos x que están en A y están en B.
Ejemplo: Sean Q={ a, n, p, y, q, s, r, o, b, k } y P={ l, u, a, o, s, r, b, v, y, z } entonces, Q 
P={ a, b, o, r, s, y }
CONJUNTO VACIO Un conjunto que no tiene elementos es llamado conjunto vacío ó
conjunto nulo lo que denotamos por el símbolo  .
Por ejemplo: Sean A={ 2, 4, 6 } y B={ 1, 3, 5, 7 } encontrar A  B. Entonces, A  B= { }
El resultado de A  B= { } muestra que no hay elementos entre las llaves, si este es el caso
se le llamará conjunto vacío ó nulo y se puede representar como:
A  B=
21
COMPLEMENTO. El complemento de un conjunto respecto al universo U es el conjunto de
elementos de U que no pertenecen a A y se denota como A' y que se representa por
comprehensión como: A'={ x  U/x y x  A }
Ejemplo: Sea U = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } A= { 1, 3, 5, 7, 9 } donde A  U. El complemento
de A estará dado por: A'= { 2, 4, 6, 8 }
DIFERENCIA. Sean A y B dos conjuntos. La diferencia de A y B se denota por A-B y es el
conjunto de los elementos de A que no están en B y se representa por comprehensión como:
A - B={ x/x  A ; X  B }
Ejemplo: Sea A= { a, b, c, d } y B= { a, b, c, g, h, i } ENTONCES, A - B= { d }
En el ejemplo anterior se observa que solo interesan los elementos del conjunto A que no
estén en B. Si la operación fuera B - A el resultado es B – A = { g, h, i }
E indica los elementos que están en B y no en A.
DIAGRAMAS DE VENN. Los diagramas de Venn que de deben al filósofo inglés John Venn
(1834-1883) sirven para encontrar relaciones entre conjuntos de manera gráfica mediante
dibujos ó diagramas. La manera de representar el conjunto Universal es un rectángulo, ó
bien la hoja de papel con que se trabaje.
Los conjuntos se representan por medio de dibujos dentro del rectángulo, los aspectos de
interés se resaltan sombreando las áreas respectivas.
Gráficamente,
22
Algunas normas operacionales entre conjuntos
CONJUNTOS
Intercepcion: A  B  {x / x  A  x  B}
Union: A  B  {x / x  A  x  B  ( A  B )}
A B  B  A
A B  B  A
A  A
A  
 A
AU
A B  B  A
A  ( B  C )  ( A  B)  C
Complemento: A  {x / x  A}
A A  U
A  ( B  C )  ( A  B)  C
A B  B  A
A  ( B  C )  ( A  B)  ( A  C )
A  ( B  C )  ( A  B)  ( A  C )
23