Pascal

Los coeficientes binomiales, números combinatorios o combinaciones[nota 1] son números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado. Sin embargo, dependiendo del enfoque que tenga la exposición, se pueden usar otras definiciones equivalentes.
Contenido
[ocultar]

* 1 Definición combinatoria
* 2Definición algebraica
* 3 El teorema de binomio y coeficientes binomiales
* 4 El teorema de Pascal
o 4.1 Prueba del teorema de Pascal
* 5 Identidades que involucran coeficientes binomiales
o 5.1 Identidad de simetría
o 5.2 Número total de subconjuntos posibles
* 6 Multiconjuntos y combinaciones con repetición
* 7 Véase también
* 8 Notasal pie
* 9 Referencias
* 10 Bibliografía
* 11 Enlaces externos

[editar] Definición combinatoria
{5\choose 3}=10, pues hay 10 formas de escoger (en rojo) 3 objetos a partir de un conjunto con 5 elementos

Se tiene un conjunto con 6 objetos diferentes {A,B,C,D,E,F}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección:A,B A,C A,D A,E A,F
B,C B,D B,E B,F
C,D C,E C,F
D,E D,F
E,F

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas:[nota 2] C(n,k)\, , n\, C\, k\,, C^n_k\, , o {n\choose k}. Así, en el ejemplo anterior se tiene entonces que C(6,2)=15, puesto que hay 15 formas de escoger 2 objetos a partir de un conjunto con 6 elementos.Los números C(n,k) se conocen como «coeficientes binomiales», pero es frecuente referirse a ellos como «combinaciones de n en k», o simplemente «n en k». Por tanto, la primera definición es:


El coeficiente binomial {n\choose k} es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Es importante notar que la definición asume implícitamente que n y kson naturales, y que además k no excede a n. Podemos definir C(n,k)=0 si k>n, puesto que no es posible escoger más elementos que los que tiene el conjunto dado (por tanto hay cero formas de hacer la elección). Estas precisiones cobrarán relevancia más adelante cuando se discutan generalizaciones del concepto (por ejemplo, cuando n o k sean negativos o cuando no sean números enteros).
[editar]Definición algebraica
Hay 5×4×3 formas de escoger ordenadamente 3 objetos de un conjunto con 5.

La definición no permite calcular el valor de los coeficientes binomiales, salvo listando los subconjuntos y contándolos. Sin embargo, existe una fórmula explícita que nos proporciona el valor de C(n,k).

Supongamos que el conjunto original tiene 5 elementos, de los cuales se deben escoger 3. Almomento de escoger el primero, se tiene 5 opciones disponibles, pero una vez fijo el primero, sólo hay 4 opciones para el segundo, y por tanto sólo 3 opciones para el último (pues no se puede repetir los escogidos en los primeros 2 pasos). De este modo, la selección puede hacerse de 5×4×3=60 formas.

Sin embargo, en tal conteo, el orden en que se escogen los elementos hace diferencia. Por ejemplo,tomar C, luego B, luego E, es una selección diferente de tomar B, luego C y luego E. Pero en la definición de coeficiente binomial, no importa el orden en que se eligen los objetos, únicamente cuáles se escogen. Por tanto, las elecciones BCE, BEC, CEB, CBE, ECB y EBC son todas equivalentes. Del mismo modo, las elecciones ABC, ACB, BCA, BAC, CAB y CBA son equivalentes, y así para cualquier terna deletras.

De esta forma, el resultado obtenido (60) no es la cantidad de subconjuntos de 3 elementos de {A,B,C,D,E}, sino que cada subconjunto está contado 6 veces, por lo que la cantidad de subconjuntos es realmente 60/6 = 10.

El argumento presentado para el ejemplo puede generalizarse de la siguiente forma. Si se tiene un conjunto con n elementos, de los cuales se van a escoger k de ellos,...