combinatoria

Teoría combinatoria
Introducción
La Teoría Combinatoria estudia las agrupaciones que pueden ser formadas cuando se toman todos, o algunos, de los elementos de un conjunto …nito. Los elementos del conjunto pueden ser de cualquier naturaleza: números, personas, empresas,
artículos producidos por una fábrica, etc. La Teoría Combinatoria estudia especialmente el número de agrupaciones que puedenser obtenidas bajo algún modo
de composición de los elementos. Para ello, distingue básicamente tres conceptos:
arreglos, permutaciones y combinaciones.
Para calcular probabilidades, muchas veces es necesario determinar la cantidad de
elementos de un conjunto dado (cardinal del conjunto), o la cantidad de elementos del
conjunto integrado por las agrupaciones que podemos realizar tomandoalgunos de
los elementos. A menudo, la tarea de contarlos uno a uno resulta tediosa. En cambio,
para poder contar resulta de mucha utilidad el llamado Principio Fundamental de
Conteo y los aportes realizados por la Teoría Combinatoria.
Principio Fundamental de Conteo
De…nición 1 (Principio fundamental de conteo) Sea un proceso que involucra
k niveles, siendo n1 ; n2; n3; :::; nk el número deresultados posibles de cada uno de ellos.
Entonces, el número total de resultados posibles de los k niveles es:
n1

n2

n3

:::

nk

Este principio es también conocido como Regla de la Multiplicación.
Ejemplo 1 Una familia desea adquirir una vivienda en un balneario y se le presentan las siguientes posibilidades: casa o apartamento. A su vez, cada una puede ser
de 1, 2 o 3 dormitorios.¿Cuántos tipos posibles de vivienda tiene a disposición?
Como existen dos niveles, y se tienen 2 opciones para el primer nivel (casa o
apartamento) y 3 opciones para el segundo (número de dormitorios), se puede aplicar
el principio fundamental de conteo para obtener la respuesta: 2 3 = 6 tipos de
vivienda.
Este resultado puede ser visualizado claramente con la ayuda de un diagrama de
árbol:
iii

Arreglos
De…nición 2 Dado un conjunto de n elementos, se de…ne como arreglo de n de
orden k (k n ) a cada k-upla ordenada que puede formarse tomando k elementos
diferentes entre los n dados.
Como una k-upla está constituida por k elementos dispuestos en determinado
orden, dos arreglos serán diferentes, aún conteniendo los mismos elementos, si los
mismos se encuentran en distintoorden.
Al número de arreglos de n de orden k lo notaremos como Ank . Para calcular
dicho número, es posible utilizar el principio fundamental de conteo. El primer lugar
de la k-upla puede estar ocupado por uno cualquiera de los n elementos, mientras
el segundo lugar puede estar ocupado por cualquiera de los elementos que no están
en el primer lugar, es decir por uno de los (n 1) elementosrestantes, ya que los k
elementos deben ser diferentes. El tercer lugar puede estar ocupado por cualquiera
de los elementos que no están ni en el primer lugar ni en el segundo, es decir por
uno cualquiera de los (n 2) elementos restantes. Si se continúa el razonamiento,
para ocupar el k-ésimo lugar se tendrán (n k + 1) elementos posibles. Entonces,
el número de arreglos de n de orden k es:
Ank =n (n

1) (n

2)::: (n

k + 1)

Recordando la de…nición de factorial de un número natural:
n! = n (n

1) (n

2)::: (1)

8n 2 N; n 6= 0

0! = 1
puede obtenerse otra fórmula para el cálculo del número de arreglos:
Ank = n (n
=

1) ::: (n

k + 1)

(n
(n

k) (n
k) (n

k
k

1) ::: (1)
=
1) ::: (1)

n!
(n

k)!

Obsérvese que si de un conjunto de n elementosdiferentes se extraen k sucesivamente sin reposición, e interesa el orden de extracción, se tendrán exactamente Ank
extracciones diferentes posibles.

iii
Ejemplo 2 De una caja que contiene cuatro bolillas numeradas del 1 al 4 se extraen
sucesivamente 2 sin reposición. ¿Cuántas extracciones diferentes pueden resultar si
se supone que interesa el orden de extracción?
Las diferentes...