En matemáticas, los coeficientes binomiales, números combinatorios o combinaciones son números estudiados en combinatoria que corresponden al número de combinaciones: 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.
Definición combinatoria thumb| . Hay por tanto 10 formas de escoger (en rojo) tres objetos a partir de un conjunto con cinco elementos.
Se tiene un conjunto con seis objetos diferentes }, de los cuales se desea escoger dos (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 (es decir, de k-combinaciones de un conjunto de n elementos), puede denotarse de varias formas:La forma se prefiere cuando no se dispone de medios para representar índices o no se dispone de símbolos matemáticos (por ejemplo, en el texto de un e-mail); sin embargo, la tercera forma es la más común en entornos académicos y textos sobre el tema. , , , , o . 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 seis 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:
Es importante notar que la definición asume implícitamente que n y k son 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).
Definición algebraica thumb|Hay 5×4×3 formas de escoger ordenadamente tres objetos de un conjunto con cinco.
La definición combinatoria 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 cinco elementos, de los cuales se deben escoger tres. Al momento de escoger el primero, se tiene cinco opciones disponibles, pero una vez fijo el primero, solo hay cuatro opciones para el segundo, y por tanto solo tres opciones para el último (pues no se puede repetir los escogidos en los primeros dos 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 de letras.
De esta forma, el resultado obtenido (60) no es la cantidad de subconjuntos de 3 elementos de }, sino que cada subconjunto está contado seis 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, la elección (ordenada) puede hacerse de
maneras, ya que en el primer paso se tienen n opciones, en el segundo se tienen n-1, en el tercero n-2, y así sucesivamente, terminando en el paso k que tendrá n-k+1 opciones.
Ahora, hay que dividir el producto anterior entre el número de selecciones «equivalentes». Pero si se tiene k objetos, hay k! formas de permutarlos, es decir, k! formas de listarlos en distinto orden. Recordemos que k! se lee k-factorial y es igual a .
Concluimos que el número de subconjuntos con k elementos, escogidos de un conjunto con n elementos es . Multiplicando el numerador y el denominador de la fracción por 1×2×3×···×(n-k) .
La expresión anterior puede escribirse de forma más compacta usando factoriales, expresión que es usada en ocasiones como la definición misma de coeficiente binomial (sobre todo en textos elementales que no explican el origen combinatorio de la misma):
Definición recursiva
Hay una fórmula recursiva para los coeficientes binomiales (véase El teorema de Pascal):
donde con y siendo
Demostración:
Definición por inducción matemática Algunos matemáticos esta definición la conocen como definición recursiva.Markushevich en Sucesiones recurrentes y Schneider en Matemáticas discretas.
Si se tiene un conjunto de n elementos, donde n ≥ 0, hay un único subconjunto sin elementos (o de cero elementos), que es el conjunto vacío, por lo que el número de estos subconjuntos de cero elementos que hay es 1, cualquiera que sea n.Sadosky, Manuel Introducción al álgebra, Eudeba 1963.
1)
Por otro lado, si tenemos una lista de los subconjuntos de k elementos y a cada uno de ellos añadimos, por turno, cada uno de los n-k elementos del conjunto inicial que no estaban en dicho subconjunto, la lista de subconjuntos resultante contendrá todos los subconjuntos de k+1 elementos y además cada uno de ellos aparecerá repetido k+1 veces en dicha lista.
2) Ribnikov: Análisis combinatorio ,1985)
El teorema de binomio y coeficientes binomiales
Finalmente, existe una tercera forma de definir los coeficientes binomiales, la cual da origen a su nombre. Sin embargo, esta definición obscurece el significado combinatorio de los números, pues la equivalencia con las definiciones anteriores no es evidente.
Por ejemplo, si desarrollamos obtenemos: , por tanto, al ser 10 el coeficiente de x³y², concluimos que C(5,3)=10.
thumb|Desarrollo de (x+y)³
La afirmación de que esta definición es equivalente a las anteriores se conoce como teorema binomial o teorema de Newton, quien dio una prueba de una versión general del resultado. Sin embargo, la forma de calcular los coeficientes era conocida por diversas culturas con muchos siglos de anticipación.
Para ilustrar la equivalencia entre esta definición y la anterior, consideremos un ejemplo con n=3, k=2. Podemos pensar que los factores de están coloreados de azul, rojo y verde respectivamente.
Por un lado, se sabe que , por lo que el coeficiente de es 3. Por otro lado, al desarrollar los factores, aparecerá un término cada vez que se elija dos colores para x (dejando el color restante para y). El número de formas de escoger dos colores entre tres posibles opciones es precisamente , como se estableció con anterioridad. La conclusión es que el coeficiente de es necesariamente .
Para el caso general, se puede imaginar que los n factores de (x+y)n han sido coloreados con diferentes colores, por lo que el coeficiente de xkyn-k será igual al número de formas de escoger k colores para asignarlos a la variable x (dejando los n-k colores restantes para y). El número de formas para escoger k colores entre n posibles opciones es C(n,k), con lo que se termina la prueba.
En contextos más técnicos, suele usarse una forma diferente de expresar el teorema de Newton mediante el uso de sumatorios:
Esta fórmula se generaliza para más de dos sumandos de la siguiente manera:
,
donde es un coeficiente multinomial que se define: . Los coeficientes multinomiales también tienen definición combinatoria. Puesto que no es más que la suma de , ,... y , también se emplean notaciones en las que , no aparece, como . Otras notaciones son o .
El triángulo de Pascal
thumb|Página 4 del Traité du triangle arithmétique, escrito por Blaise Pascal en 1654
En 1654, Blaise Pascal entabló correspondencia con Pierre de Fermat sobre ciertos problemas de probabilidad, correspondencia que daría origen a su Traité du triangle arithmétique, considerado uno de los trabajos pioneros en el estudio moderno de la probabilidad. En ese trabajo, entre otras cosas, estudia lo que hoy se conoce como triángulo de Pascal que es un arreglo de números definido a continuación.
Se tiene una cuadrícula rectangular en la cual se escribe el número 1 en las casillas del borde superior y el borde izquierdo: 1 1 1 1 … 1 1 1 …
thumb|Forma común de ilustrar el triángulo de Pascal
Los números de las demás casillas se obtienen con la siguiente regla: en cada casilla se escribe la suma de los valores de dos casillas contiguas una situada a su izquierda y la otra en la parte superior: 1 1 1 1 1 1 1 … 1 2 3 4 5 6 7 …1 3 6 10 15 21 28 …1 4 10 20 35 56 84 ……………………
La matriz es simétrica, por ello es común presentar el arreglo en forma triangular, con los bordes inclinados, tal como se ilustra en la figura. De esta forma, cada número es igual a la suma de los dos que se encuentran arriba del mismo.
thumb|Las entradas del triángulo de Pascal consisten de coeficientes binomiales.
Pascal notó que para cualquier entero n, se cumple que
ya que solo hay una forma de escoger cero o todos los elementos de un conjunto dado. De esta forma, se pueden reescribir los bordes como: C(0,0) C(1,1) C(2,2) C(3,3) … C(1,0) C(2,0) C(3,0) … Finalmente, Pascal notó que las demás casillas del arreglo también son coeficientes binomiales: C(0,0) C(1,1) C(2,2) C(3,3) … C(1,0) C(2,1) C(3,2) C(4,3) …C(2,0) C(3,1) C(4,2) C(5,3) …C(3,0) C(4,1) C(5,2) C(6,3) ……………… Cuando se listan las entradas de forma triangular como en la figura, es posible enunciar este resultado como
La afirmación de que las entradas del triángulo de Pascal son precisamente los coeficientes binomiales, se basa en la siguiente identidad, conocida ahora como identidad de Pascal o teorema de Pascal.
Prueba del teorema de Pascal thumb|El teorema de Pascal se prueba dividiendo la selección en dos casos.
Si bien puede probarse el teorema de Pascal por medio de manipulaciones algebraicas de la fórmula con factoriales, una prueba puramente combinatoria es mucho más sencilla, proporcionando un ejemplo elegante del enfoque y técnicas de la combinatoria.
Como ejemplo, se verificará el Teorema de Pascal cuando n=5, k=3. El lado izquierdo de la identidad cuenta el número de formas de escoger tres elementos a partir de un conjunto de cinco elementos. Supongamos ahora que el primer objeto se colorea de rojo y los demás azules. Al escoger los tres objetos, hay dos casos: Entre los objetos escogidos se incluye el objeto rojo. Todos los objetos escogidos son azules. Ambos casos cubren la totalidad de subconjuntos con tres elementos, por tanto su suma debe ser igual a .
Para contar el primer caso, dado que el objeto rojo tiene que estar incluido, solo es necesario escoger dos objetos entre los cuatro azules restantes, lo cual puede efectuarse de formas.
En el segundo caso, puesto que el objeto rojo no ha sido seleccionado, se debe escoger tres elementos entre los cuatro azules. El número de formas de hacer esta elección es .
Concluimos entonces que el número total de subconjuntos con 3 elementos, , es igual al número de subconjuntos del primer caso, sumado al número de subconjuntos incluidos en el segundo caso, , es decir: .
El caso general se obtiene de forma similar, marcando un elemento particular, para luego dividir el conteo en dos casos, dependiendo si el elemento marcado está incluido o no. Cuando se incluye el elemento marcado falta escoger k-1 objetos de los n-1 no marcados, mientras que cuando no se incluye, hay que escoger k objetos de los n-1 marcados, concluyendo que .
Identidades que involucran coeficientes binomiales thumb|Simetría en el triángulo de Pascal