Anlisis combinatorio

Introduccin
El anlisis combinatorio estudia las distintas formas de agrupar y
ordenar los elementos de un conjunto, sin tener en cuenta la naturaleza
de estos elementos.
Los problemas de arreglos y combinaciones pueden parecer aburridos y
quiz se piense que no tienen utilidad pero los teoremas del anlisis
combinatorio son la base del clculo de la probabilidad.
La probabilidad se encarga de los arreglos y las combinaciones que
determinan el nmero de formas diferentes en que un acontecimiento
puede suceder.
El anlisis combinatorio tiene aplicaciones en el diseo y funcionamiento
de la tecnologa computacional as como tambin en las ciencias. La
teora combinatoria se aplica en las reas en donde tengan relevancia
las distintas formas de agrupar elementos.
Resumiendo, El objeto del Anlisis combinatorio o Combinatoria es el
estudio de las distintas ordenaciones que pueden formularse con los
elementos de un conjunto, de los distintos grupos que pueden formarse
con aquellos elementos y de las relaciones entre unos y otros grupos.
Desarrollo
Principio Fundamental del Anlisis Combinatorio
Una persona tiene 2 formas de ir de una ciudad A a otra ciudad B; y una
vez llegada a B, tiene 3 maneras de llegar a otra ciudad C, De cuntas
maneras podr realizar el viaje de A a C pasando por B?
Si empez a pie, podr tomar luego avin, carro o trasatlntico, y si
empez en bicicleta, tambin podr tomar avin, carro o trasatlntico.
La persona tuvo 6 formas diferentes de realizar el viaje que son:
(iniciales) pa, pc, pt, ba, bc, bt. (2 x 3 = 6).
Por lo que el principio fundamental del anlisis combinatorio, puede
expresarse as: Si una primera decisin, operacin o accin puede
efectuarse de a formas diferentes, una segunda accin puede efectuarse

de b formas diferentes, una tercera accin puede efectuarse de c formas

diferentes y as sucesivamente hasta la ensima accin que puede
efectuarse de z formas diferentes, entonces el nmero total de formas
diferentes que pueden efectuarse estas n acciones es igual con: a x b x c
x ... x z. Este principio tambin se llama principio de conteo o principio
multiplicativo.
Principio de adicin:
Si un evento E puede ocurrir en m formas y un segundo evento F puede
ocurrir en n formas y ambos eventos no pueden ocurrir en forma
simultnea entonces E o F pueden ocurrir en m + n formas.
Ejemplos:
a) Existen 3 profesores y 2 profesoras que imparten la materia de
clculo. Un estudiante puede escoger un profesor de 3 + 2 = 5 formas.
b) En una biblioteca hay 3 libros de novelas de misterio diferentes, 5
novelas de romance y 4 novelas de aventura diferentes. Existen 3 + 5 +
4 = 12 formas de escoger una novela.
c) Cinco empresas de transporte terrestre tienen servicio diario entre
Mrida y Mxico. Tres empresas de aviacin tienen vuelo diario entre
Mrida y Mxico. En consecuencia, hay 5+3 maneras de ir de Mrida a
Mxico en avin o en autobs. En los problemas de conteo, la palabra
"o" se traduce en suma.
d) Si tengo un billete de $50, uno de $100, uno de $200 y un billete de
$1000, Cul es el nmero total de precios que puedo pagar usando
algn o todos mis billetes?
Este es un buen ejemplo de una situacin en la que se necesita un
listado sistemtico. Como tenemos 4 billetes de denominacin diferente,
debemos considerar 4 casos. stos son, los precios que podemos cubrir
con un billete, con 2 billetes, con 3 billetes y con 4 billetes. Se debe de
examinar cada uno de estos casos y luego aplicar el principio de adicin.
Con 1 billete podemos tener 4 precios: $50, $100, $200 y $1000.
Con 2 billetes, podemos listar sistemticamente las combinaciones:
i. Las que tienen $50 son: $50 + $100 = $150, $50+$200 = $250, $50
+ $1000 = $1050
ii. Las que tienen $100 y no hemos listado an: $100 + $200 = $300,
$100+$1000 = 1100
iii. Y las que tienen $200 y tampoco hemos listado: $200 + $100 =
$1200 Con 3 billetes, las combinaciones son(una para cada billete que
falta):

i. $50 + $100 + $200 = $350 (falta la de $1000)

ii. $100 + $200 + $1000 = $1300 (falta la de $50)
iii. $50 + $200 + $1000 = $1250 (falta la de $100)
iv. $50 + $100 + $1000 = $1150 (falta la de $200) Con las cuatro
billetes: $ 50 + $100 + $200 + $1000 = $1350
Principio de multiplicacin:
Si un evento puede efectuarse de n1 formas diferentes y si continuando
el procedimiento, un segundo evento puede realizarse de n2 formas
diferentes y si despus de efectuados, un tercer elemento puede
realizarse de n3 formas diferentes, entonces el nmero de formas en
que los eventos puede realizarse ser n1 n2 n3maneras diferentes
Ejemplos:
1. El men de un restaurante ofrece 3 platos calientes y 4 postres. De
cuntas maneras se puede elegir un almuerzo de 1 plato caliente y 1
postre?
Se puede hacer una lista de todas las posibilidades, pero es mucho ms
cmodo aplicar el principio de la multiplicacin:
Hay 3 maneras de elegir el plato caliente y para cada una de ellas hay 4
maneras de elegir el postre. Por lo tanto, hay 3 4 =12 comidas posibles.
2. Cuntos cdigos de una letra y un nmero de un dgito se pueden
formar con las 26 letras del alfabeto y los nmeros 0, 1, 2,...,9?
Listando todas las posibilidades:
A0 A1 .... A9
B0 B1 .... B9
MM
Z0 Z1 .... Z9
hasta obtener 26 filas de 10 cdigos en cada una: 26 10 = 260.
Es ms simple utilizar el principio de multiplicacin: hay 26 maneras de
elegir la letra y para cada una de ellas hay 10 maneras de elegir el
nmero, de modo que son 26 10 = 260 cdigos.
Nota que en los 2 ejemplos hay total libertad de elegir el segundo
elemento, no importa cmo se eligi el primero. Es decir, el segundo
elemento es independiente del primero. Elegido el plato caliente,
podemos elegir cualquiera de los 4 postres. Elegida la letra podemos
agregarle cualquiera de los 10 nmeros. Este principio es til cuando se
puede descomponer el proceso de recuento en pasos independientes.

Del problema de los 10 comensales, posiblemente parece increble que

10 personas puedan colocarse en un nmero tan elevado de posiciones
diferentes.
Comprobemos el clculo. Ante todo, hay que aprender a determinar el
nmero de combinaciones distintas, posibles. Para mayor sencillez
empecemos calculando un nmero pequeo de objetos, por ejemplo,
tres. Llammosles A, B y C.
Deseamos saber de cuntos modos diferentes pueden disponerse,
cambiando
mutuamente
su posicin. Hagamos
el siguiente
razonamiento. Si se separa de momento el objeto C, los dos restantes, A
y B, pueden colocarse solamente en dos formas.
Ahora agreguemos el objeto C a cada una de las parejas obtenidas.
Podemos realizar esta operacin tres veces:
Colocar C detrs de la pareja,
Colocar C delante de la pareja,
Colocar C entre los dos objetos de la pareja.
Es evidente que no son posibles otras posiciones distintas para el objeto
C, a excepcin de las tres mencionadas. Como tenemos dos parejas, AB
y BA, el nmero total de formas posibles de colocacin de los tres
objetos ser: 23 = 6
Ahora hagamos el clculo para 4 objetos, llammosles A, B, C y D, y
separemos de momento uno de ellos, por ejemplo, el objeto D.
Efectuemos con los otros tres todos los cambios posibles de posicin. Ya
sabemos que para tres, el nmero de cambios posibles es 6. En cuntas
formas diferentes podemos disponer el cuarto objeto en cada una de las
6 posiciones que resultan con tres objetos?
Evidentemente, sern cuatro. Podemos:
Colocar D detrs del tro,
Colocar D delante del tro,
Colocar D entre el 1 y de 2 objetos,
Colocar D entre el 2 y 3.
Obtenemos en total: 6 4 = 24 posiciones, pero teniendo en cuenta que
6 = 2 3 y que 2 = 1 2 , entonces podemos calcular el nmero de
cambios posibles de posicin haciendo la siguiente multiplicacin: 1
2 3 4 = 24
Permutaciones
CASO 1.- NO PODEMOS REPETIR (PERMUTACIN SIMPLE U
ORDINARIA)

Se llama permutacin simple de n elementos tomados de k en k (k < n)

a los distintos grupos formados por k elementos de forma que:
Los k elementos que forman el grupo son distintos (no se repiten)
Dos grupos son distintos si se diferencian en algn elemento o en el
orden en que estn colocados (influye el orden).
No se utilizan todos los elementos.
Al elegir un primer elemento, lo podemos hacer de n formas. Quitamos
el elemento elegido y elegimos otro de entre los n-1 que quedan. Esto
podr hacerse de n-1 formas. Quitamos tambin este elemento y nos
quedamos con n-2, de entre los que elegimos el tercero. Esto lo
podremos hacer de n-2 formas...
Segn la regla del producto, las maneras de escoger k elementos de
entre un total de n segn un determinado orden, ser igual al producto
de: n (n 1) (n 2)... (n k +1)
Notacin. n k P , , n k P y P(n, k ) denotan el nmero de permutaciones
de n elementos distintos tomados de k en k.
Para llegar a una versin simplificada se opera as:
n ( n1 )( n2 )( n3 )
P ( n , k )=

( n ( k1 ) )( nk ) ( n( k +1 ) ( 3 )( 2 ) ( 1 ) )
n!
=
=P ( n ,k )
( nk ) !
( nk ) ( n ( k +1 ) (3 )( 2 ) ( 1 ) )

n!
( nk ) !

Combinaciones
Caso 1.- EL ORDEN NO IMPORTA PERO NO SE PUEDEN REPETIR
ELEMENTOS.
Tomamos las n (n 1) (n 2)... (n k +1) posibilidades y las
partimos en clases, de forma que en cada clase estn aquellas
elecciones que sean la misma salvo el orden.
Para k elementos, la forma de ordenarlos ser k! y, as, en cada tipo se
tienen exactamente k! casos.
Por tanto, el nmero de tipos, es decir, el nmero de posibilidades de
escoger k elementos sin importar el orden y sin repetir es
n( n1 )( nk +1 )
n!
=
k!
k ! ( nk ) !

Este nmero suele conocerse como el nmero de combinaciones de n

elementos tomadas de k en k y se denota por:
n!
Cnk = n =
k k ! ( nk ) !

()

Se llama combinaciones de n elementos tomados de k en k (k n)

a todas las clases posibles que pueden hacerse con los n elementos de
forma que:
Cada agrupacin est formada por n elementos distintos entre s
Dos agrupaciones distintas se diferencian al menos en un elemento,
sin tener en cuenta el orden.