Números combinatorios
Las agrupaciones combinatorias que sólo consideran la esencia de los grupos formados y no su orden, llamadas combinaciones, han constituido una rama específica dentro de la especialidad del análisis combinatorio, con múltiples usos en diversos campos. La expresión numérica de tales combinaciones recibe el nombre de número combinatorio o coeficiente binómico.
Coeficientes binómicos
Se define número combinatorio o coeficiente binómico como el valor numérico de las combinaciones ordinarias (sin repetición) de un conjunto de n elementos tomados en grupos de r, siendo n y r dos números enteros y positivos tales que n ³ r. Matemáticamente, un número combinatorio se expresa como:
Los números combinatorios se leen «n sobre r».
Propiedades de los números combinatorios
Entre las propiedades generales de los números combinatorios encontramos las siguientes que permiten un estudio mas detallado de lo mismo:
Cualquier número sobre 0 es igual a 1.
Todo número sobre sí mismo es igual a 1.
Un número sobre 1 es siempre igual al número.
Triángulo de Tartaglia
En el siglo XVI, el italiano Niccolò Tartaglia propuso un triángulo regular de números tales que:
Todas las filas del triángulo comienzan y terminan por la unidad, y son simétricas con respecto al valor central. Cada número del triángulo es igual a la suma de los dos situados encima de él.
La suma de todos los elementos de cada fila coincide con el valor 2n, siendo n el orden de la fila.
Esta disposición es de tipo combinatorio y se conoce como triángulo de Tartaglia o de Pascal.
Binomio de Newton
El uso de números combinatorios simplifica enormemente la expresión del llamado binomio de Newton, que desarrolla el valor de la potencia n-sima de un binomio:
Particularizando este binomio para el caso a = b = 1, se obtiene una explicación del hecho de que la suma de cada fila del triángulo de Tartaglia sea igual a 2n, ya que resulta:
El Principio de Inclusion y Exclusion
Es un elemental e importante principio de Combinatoria que puede ser usado para resolver una variedad de interesantes problemas. Este principio es conocido con varios nombres, los m´as comunes son: el principio del palomar, el principio de los cajones de Dirichlet.
Una forma simple del Principio de Inclusion y Exclusion dice:
Si n+1 objetos son colocados en n cajas, entonces al menos una caja contiene dos o mas objetos.
Ejemplo: Si en una habitacion hay 8 personas, entonces necesariamente existen dos de ellas que este año
celebran su cumpleaños el mismo dia de la semana. Las 8 personas las podemos modelar como el conjunto
P = {0, 1, . . . , 7} y los dias de la semana como el conjunto S = {0, 1, 2 . . . , 6}. El diıa de la semana que se celebra el cumplea˜nos de cada unas resulta ser una funci´on de P en S, por el principio de los cajones, esta funcion no puede ser inyectiva, luego al menos dos personas distintas celebraran su cumpleaños el mismo dia de la semana.
Este principio es sumamente intuitivo, sin embargo resulta de gran utilidad cuando se trabaja con conjuntos finitos, en el contexto de computacion cuando se trabaja por ejemplo con estructuras de datos como arreglos, tablas de hash, grafos, etc.
No hay comentarios:
Publicar un comentario