COMBINATORIA Por Análisis Combinatorio o Combinatoria, se entiende aquella parte del álgebra que se ocupa del estudio y propiedades de los grupos que pueden formarse con elementos dados, distinguiéndose entre sí: • por el número de elementos que entran en cada grupo, • por la clase de elementos • por el orden de colocación. El número de elementos de que se dispone para formar las distintas agrupaciones se llama base y el número de elementos que intervienen en cada agrupación se denomina orden Las agrupaciones de orden 1 se denominan monarias, las de orden 2 binarias, las de orden 3, ternarias, etc. Los m elementos de que se dispone para formar los grupos pueden ser distintos o bien puede haber algunos iguales. En el primer caso, las agrupaciones formadas se llaman ordinarias, las formadas en el segundo supuesto se denominan agrupaciones con repetición Según los criterios empleados para la formación, las agrupaciones pueden ser de tres tipos: Variaciones Permutaciones Combinaciones VARIACIONES: 1. VARIACIONES ORDINARIAS: Se denominan variaciones ordinarias de m elementos tomados n a n, a las diferentes agrupaciones que con ellos pueden formase, de tal modo que en cada grupo entren n elementos, diferenciándose un grupo de otro al menos en el orden de colocación de dichos elementos Las variaciones ordinarias se representan por el símbolo Vm,n o por Vmn . El número de variaciones ordinarias de m elementos, tomados n a n , es igual al producto de n factores consecutivos y decrecientes, siendo m el primer factor y (m-n+1) el último: Vm,n = m·(m-1)·(m-2)·(m-3)· .... (m-n+1) 2. VARIACIONES CON REPETICIÓN: Se llaman variaciones con repetición tomados de n en n, a los diferentes grupos que con ellos pueden formarse, de tal modo que en cada grupo entren n elementos, pudiendo alguno repetirse una o varias veces y considerando dos grupos distintos si se diferencian en algún elementos o en el orden en que están calculados. El número de variaciones con repetición de orden, que se pueden formar con m elementos, se indica con los símbolos: VR nm o Vm' ,n . El número de variaciones con repetición de m elementos, tomados de n en n, es igual a una potencia de base m y exponente n: VR nm = Vm,' n = m n PERMUTACIONES: 1. PERMUTACIONES ORDINARIAS: Dados m objetos, llamaremos permutaciones ordinarias de esos m elementos a las variaciones ordinarias de los mismos tomados m a m, es decir, a los diferentes grupos que con ellos pueden formarse, de modo que entrando todos ellos en cada grupo, se diferencie un 1

grupo de otro solamente en el orden de colocación de los elementos. Por tratarse de una caso particular de las variaciones, la fórmula que nos de el número de permutaciones con m elementos Pm será: Pm = Vmm = m·(m - 1)·(m - 2)·....(m - m + 1) = n·(m - 1)·(m - 2)·...3·2·1 e invirtiendo el orden de los factores: Pm = 1·2·3· .... (m-2)·(m-1)·m Factorial de un número natural.- Factorial de un número natural, es el producto de n factores consecutivos, que comienzan en la unidad y terminan en n. Se representa por n!

2.

PERMUTACIONES CON REPETICIÓN: Dado un conjunto M con m elementos, entre los cuales hay un cierto número a de elementos de una clase, otro número b de elementos de otra clase y un tercer número c de elementos de otra clase, y así sucesivamente, se llaman permutaciones con repetición a las diferentes formas en que se pueden ordenar esos m elementos. Una ordenación se distingue de otra por el lugar que ocupan dos elementos distintos En general, si entre los m elementos que figuran en una permutación, un elemento aparece repetido a veces, otro b veces, otro c veces, el número de permutaciones con repetición se expresa así: Pm m! Pma ,b ,c = = Pa ·Pb ·Pc a!·b!·c! La suma de los índices superiores nunca puede ser mayor que el índice inferior.

COMBINACIONES: Se llaman combinaciones sin repetición de m elementos, tomados de n en n, a las diferentes agrupaciones que se pueden formar con esos m elementos, de modo que en cada grupo entren n de ellos, diferenciándose un grupo de otro al menos en uno de sus elementos. Para determinar el número de las combinaciones, hemos de suponer formadas todas las combinaciones posibles de m elementos, tomados n a n, número que representaremos por C nm . Si variamos el orden de colocación de los n elementos que forman cada combinación, cada combinación dará origen a Pn permutaciones, y el conjunto de todos estos grupos de permutaciones constituirán las variaciones de los m elementos tomados n a n, luego: Vn C nm x Pn = Vmn de donde se deduce : C nm = m Pn teniendo en cuenta los valores deducidos anteriormente para variaciones y permutaciones ordinarias, resulta: m·(m - 1)·(m - 2)· ... (m - n + 1) C nm = n! NÚMEROS COMBINATORIOS O COEFICIENTES BINÓMICOS: El número de combinaciones ordinarias de m elementos, tomados n a n, se llama número m combinatorio o coeficiente binómico y se indica por el símbolo   , que se lee m sobre n, n siendo m y n números naturales. Los números m y n se llaman, respectivamente, índice superior e índice inferior del número combinatorio.  m  m·(m - 1)·(m - 2)·(m - 3)· ... (m - n + 1) C nm =   = (I) 1·2·3· ......(n - 1)·n n 2

Expresión factorial de un número combinatorio: Si en la expresión (I) multiplicamos los dos términos de la fracción por (m-n)!, se obtiene la siguiente expresión factorial: m m!   =  n  n!·(m - n)! Habida cuenta que por convenio: 0! = 1 y que 1! = 1, podemos considerar los siguientes casos particulares: m m! m!   = = =1  0  0!·(m - 0)! 1·m! 0 1 0!   = = =1  0  0!·0! 1 m m! (m - 1)!·m   = = =m  1  1!·(m - 1)! 1·(m - 1)! Propiedades de los números combinatorios: 1.- Dos números combinatorios son iguales si sus índices superiores son iguales y la suma de los inferiores es igual al índice superior: m  m     =   n  m - n 2.- La suma de dos números combinatorios cuyos índices superiores son iguales y los inferiores difieren en una unidad es igual a otro número combinatorio cuyo índice inferior es el mayor de los dos índices inferiores y cuyo índice superior supera en una unidad al índice superior de los sumandos.  m   m   m + 1   +   =    n   n + 1  n + 1  Triángulo de Tartaglia.- Una aplicación de las propiedades de los números combinatorios es el llamado triángulo de Tartaglia:

3

Desarrollando los números combinatorios resulta:

En el segundo triángulo se observa, a partir de la tercera fila, que un número cualquiera de una fila, salvo el primero y el último que son 1, es igual a la suma de los dos números que están encima de él (uno a la izquierda y otro a la derecha) en la fila inmediata superior: esto es consecuencia de la segunda propiedad de los números combinatorios, como puede comprobarse en el primero de los triángulos. Potencia n-ésima del binomio. Binomio de Newton.- Si calculamos por medio de multiplicaciones las sucesivas las primeras potencias del binomio x + a, obtendremos los siguientes resultados, en los que se observa que los coeficientes coinciden con las filas del triángulos de Tartaglia: ( x + a) 0 = 1

(x + a )1 = x + a

0 =   0 1 1 =  ·x +  ·a 1 0

 2  2  2 =  ·x 2 +  ·xa +  ·a 2 0 1  2  3  3  3  3 (x + a )3 = x 3 + 3x 2 a + 3xa 2 + a 3 =  ·x 3 +  ·x 2 a +  ·xa 2 +  ·a 3  3  2 1  0 Se observa, además, que los exponentes de x van disminuyendo de unidad en unidad, desde la potencia dada hasta cero, mientras que los de a van aumentando en sentido inverso a los de x, a partir de cero. La intuición nos hace pensar que esta ley de formación de las potencias de un binomio se cumple siempre, es decir, que cualquiera que sea el valor de m, podría escribirse: m m m m m  m −1  m  m ·xa +  ·a (II) (x + a )m =  ·x m +  ·x m−1a +  ·x m−2 a 2 +  ·x m −3 a 3 + ...... +  0 1 2 3 m 1 m           ( x + a) 2 = x 2 + 2xa + a 2

4

Desarrollo de (x – a)m . m  m −1  m  m m m m m ·xa ( x - a) m =  ·x m -  ·x m −1 a +  ·x m − 2 a 2 -  ·x m − 3 a 3 + ...... ±  m  ·a (III)  m - 1 m 2 3 0 1 Relaciones entre los coeficientes binómicos.- Si hacemos x = a = 1 en las expresiones (II) y (III), se tendrá:  m  m m m m m  +   a.- (1 + 1) = 2 m =   +   +   + ..... +   m - 1  m  0 1 2 Es decir: La suma de los coeficientes del desarrollo de la potencia n-ésima de un binomio es igual a 2m.  m  m m m m m m  m   b.- (1 - 1) = 0 m =   -   +   -   - .... ±   m - 1  m  0 1 2 3 o sea: La suma de los coeficientes de lugar par es igual a la suma de los que ocupan lugar impar.

5