Trabajo

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 pueden serobtenidas 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 tomando algunos delos 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 de resultadosposibles 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 devivienda 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 2Dado 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 distinto orden. Al número de arreglos de n de ordenk lo notaremos como An . Para calcular k 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) elementos restantes, ya que los k elementos deben serdiferentes. 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: An = n (n k 1) (n 2)::: (n k + 1)

Recordando lade…nición de factorial de un número natural: n! = n (n 1) (n 2)::: (1) 0! = 1 puede obtenerse otra fórmula para el cálculo del número de arreglos: An = n (n k = n! (n k)! 1) ::: (n k + 1) (n (n k) (n k) (n k k 1) ::: (1) = 1) ::: (1) 8n 2 N; n 6= 0

Obsérvese que si de un conjunto de n elementos diferentes se extraen k sucesivamente sin reposición, e interesa el orden de extracción, se tendránexactamente An k 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 posibilidades son todos los arreglos de 4 de orden 2, es decir todos los pares ordenados posibles: (1,2), (1,3),...