CURSOENLNEAINGENIERA
Coeficiente binomial
Los coeficientes binomiales, nmeros combinatorios o
combinacionesnota 1 son nmeros estudiados en combinatoria que
corresponden al nmero de formas en que se pueden extraer
subconjuntos a partir de un conjunto dado. Sin embargo,
dependiendo del enfoque que tenga la exposicin, se pueden usar
otras definiciones equivalentes.
Definicin combinatoria
, 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 eleccin). Existen
15 formas de efectuar tal eleccin:
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 nmero de formas de escoger k elementos a partir de un conjunto
,
,
, o
de n, puede denotarse de varias formas:nota 2
. 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.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Los nmeros 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 definicin es:
El coeficiente binomial
es el nmero de subconjuntos de k
elementos escogidos de un conjunto con n elementos.
Es importante notar que la definicin asume implcitamente que n y k
son naturales, y que adems k no excede a n. Podemos definir
C(n,k)=0 si k>n, puesto que no es posible escoger ms elementos
que los que tiene el conjunto dado (por tanto hay cero formas de
hacer la eleccin). Estas precisiones cobrarn relevancia ms
adelante cuando se discutan generalizaciones del concepto (por
ejemplo, cuando n o k sean negativos o cuando no sean nmeros
enteros).
Definicin algebraica
Hay 543 formas de escoger ordenadamente 3 objetos de un
conjunto con 5.
La definicin no permite calcular el valor de los coeficientes
binomiales, salvo listando los subconjuntos y contndolos. Sin
embargo, existe una frmula explcita que nos proporciona el valor de
C(n,k).
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Supongamos que el conjunto original tiene 5 elementos, de los cuales
se deben escoger 3. Al momento de escoger el primero, se tiene 5
opciones disponibles, pero una vez fijo el primero, slo hay 4
opciones para el segundo, y por tanto slo 3 opciones para el ltimo
(pues no se puede repetir los escogidos en los primeros 2 pasos). De
este modo, la seleccin puede hacerse de 543=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 seleccin diferente de tomar B, luego C y luego E. Pero en la
definicin de coeficiente binomial, no importa el orden en que se
eligen los objetos, nicamente cules 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 {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, la eleccin (ordenada) puede
hacerse de
n (n-1) (n-2) ... (n-k+1)
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 nmero 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
k! = 123... k
Concluimos que el nmero de subconjuntos con k elementos,
escogidos de un conjunto con n elementos es
.
Multiplicando el numerador y el denominador de la fraccin por
123(n-k)
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
La expresin anterior puede escribirse de forma ms compacta
usando factoriales, expresin que es usada en ocasiones como la
definicin misma de coeficiente binomial (sobre todo en textos
elementales que no explican el origen combinatorio de la misma):
El coeficiente binomial
est dado por la frmula
Definicin recursiva
Hay una frmula recursiva para los coeficientes binomiales (vase El
teorema de Pascal):
con los valores iniciales
Demostracin:
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Definicin por induccin matemtica
Algunos matemticos esta definicin la conocen como definicin
recursiva 1
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
vaco, por lo que el nmero de estos subconjuntos de cero elementos
que hay es 1, cualquiera que sea n.2
1.- c(n, 0) = 1
Por otro lado, si tenemos una lista de los subconjuntos de k
elementos y a cada uno de ellos aadimos, 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 adems cada uno de ellos
aparecer repetido k+1 veces en dicha lista.
2.- c(n, k+1)= C(n, k) (n-k)/ (k +1).
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
definicin obscurece el significado combinatorio de los nmeros, pues
la equivalencia con las definiciones anteriores no es evidente.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
El
coeficiente
binomial
es
el
coeficiente
del
trmino
obtenido al desarrollar
Por ejemplo, si desarrollamos (x+y)5 obtenemos:
,
por tanto, al ser 10 el coeficiente de xy, concluimos que C(5,3)=10.
Desarrollo de (x+y)
La afirmacin de que esta definicin es equivalente a las anteriores se
conoce como teorema binomial o teorema de Newton, quien dio una
prueba de una versin general del resultado. Sin embargo, la forma
de calcular los coeficientes era conocida por diversas culturas con
muchos siglos de anticipacin.
Para ilustrar la equivalencia entre esta definicin y la anterior,
consideremos un ejemplo con n=3, k=2. Podemos pensar que los
factores de (x+y)=(x+y)(x+y)(x+y) estn coloreados de azul, rojo y
verde respectivamente.
Por un lado, se sabe que (x+y) = x+3xy+3xy+y, por lo que el
coeficiente de xy es 3. Por otro lado, al desarrollar los factores,
aparecer un trmino xy cada vez que se elija dos colores para x
(dejando el color restante para y). El nmero de formas de escoger 2
colores entre 3 posibles opciones es precisamente C(3,2), como se
estableci con anterioridad. La conclusin es que el coeficiente de xy
es necesariamente C(3,2).
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 nmero de formas de escoger k colores para
asignarlos a la variable x (dejando los n-k colores restantes para y).
El nmero de formas para escoger k colores entre n posibles opciones
es C(n,k), con lo que se termina la prueba.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
En contextos ms tcnicos, suele usarse una forma diferente de
expresar el teorema de Newton mediante el uso de sumatorios:
El desarrollo de
es
Esta frmula se generaliza para ms de dos sumandos de la siguiente
manera:
donde
es un coeficiente multinomial que se define:
. Los coeficientes multinomiales tambin
tienen definicin combinatoria. Puesto que no es ms que la suma
de
,
,... y
, tambin se emplean notaciones en las que , no
aparece, como
. Otras notaciones son
El teorema de Pascal
Pgina 4 del Trait du triangle arithmtique, escrito por Blaise Pascal
en 1654
En 1654, Blaise Pascal entabl correspondencia con Pierre de Fermat
sobre ciertos problemas de probabilidad, correspondencia que dara
origen a su Trait du triangle arithmtique, considerado uno de los
trabajos pioneros en el estudio moderno de la probabilidad. En ese
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
trabajo, entre otras cosas, estudia lo que hoy se conoce como
tringulo de Pascal que es un arreglo de nmeros definido a
continuacin.
Se tiene una cuadrcula rectangular en la cual se escribe el nmero 1
en las casillas del borde superior y el borde izquierdo:
1 1 1 1 ...
1
1
1
...
Forma comn de ilustrar el tringulo de Pascal
Los nmeros de las dems casillas se obtienen con la siguiente regla:
en cada casilla se escribe la suma de los valores de las dos casillas
contiguas situadas a su izquierda y 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 ...
... ... ... ... ... ... ...
Es comn, sin embargo, presentar el arreglo en forma triangular, con
los bordes inclinados, tal como se ilustra en la figura. De esta forma,
cada nmero es igual a la suma de los dos que se encuentran arriba
del mismo.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Las entradas del tringulo de Pascal consisten de coeficientes
binomiales
Pascal not que para cualquier entero n, se cumple que
ya que slo 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 dems casillas del arreglo tambin
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
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
La posicin k (contando desde cero) en la fila n del tringulo de
Pascal es igual al coeficiente binomial
La afirmacin de que las entradas del tringulo de Pascal son
precisamente los coeficientes binomiales, se basa en la siguiente
identidad, conocida ahora como identidad de Pascal o teorema de
Pascal.
Para cualquier par de nmeros naturales n, k se cumple
Blaise Pascal, (1654)
Prueba del teorema de Pascal
El teorema de Pascal se prueba dividiendo la seleccin en dos casos.
Si bien puede probarse el teorema de Pascal por medio de
manipulaciones algebraicas de la frmula con factoriales, una prueba
puramente combinatoria es mucho ms sencilla, proporcionando un
ejemplo elegante del enfoque y tcnicas de la combinatoria.
Como ejemplo, se verificar el Teorema de Pascal cuando n=5, k=3.
El lado izquierdo de la identidad cuenta el nmero de formas de
escoger 3 elementos a partir de un conjunto de 5 elementos.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Supongamos ahora que el primer objeto se colorea de rojo y los
dems azules. Al escoger los 3 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 3 elementos,
por tanto su suma debe ser igual a
Para contar el primer caso, dado que el objeto rojo tiene que estar
incluido, slo es necesario escoger 2 objetos entre los 4 azules
restantes, lo cual puede efectuarse de
formas.
En el segundo caso, puesto que el objeto rojo no ha sido
seleccionado, se debe escoger 3 elementos entre los 4 azules. El
nmero de formas de hacer esta eleccin es
Concluimos entonces que el nmero total de subconjuntos con 3
elementos,
, es igual al nmero de subconjuntos del primer caso,
sumado al nmero 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
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Identidades que involucran coeficientes
binomiales
Simetra en el tringulo de Pascal
Existe una cantidad muy grande de identidades que involucran
coeficientes binomiales. El teorema de Pascal es un primer ejemplo
de identidad relativa a coeficientes binomiales, a continuacin se
analizarn algunas pocas de las ms conocidas. Son de particular
inters puesto que sus pruebas proporcionan nuevamente ejemplos
de razonamiento combinatorio, el cual no es usualmente presentado
al tratar el tema pues por lo general, en los pocos casos en que se
dan razones sobre su origen, se limitan a simples manipulaciones de
la definicin algebraica.
Identidad de simetra
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Hay la misma cantidad de formas de escoger 3 objetos y pintarlos de
rojo, que formas de escoger 2 objetos y pintarlos de azul
La primera identidad a considerar es una igualdad de simetra o la
propiedad de Stiffel que establece
Para todo n, k se cumple:
Por ejemplo, C(12,5) = 792 = C(12,7). Es una propiedad de simetra
porque equivale a la afirmacin de que el tringulo de Pascal es
simtrico respecto a su eje vertical. Es comn remitirse a la frmula
de factoriales para verificar su veracidad.
La interpretacin combinatoria de la identidad de simetra es la
afirmacin de que al escoger un subconjunto automticamente se
determina su complemento, por lo que hay la misma cantidad de
subconjuntos con k elementos que subconjuntos con n-k elementos.
Por ejemplo, si se tiene un conjunto con 5 elementos, de los cuales
se desea pintar 3 de rojo, es posible hacer la seleccin de C(5,3)=10
formas. Pero cada seleccin automticamente determina 2 objetos
que no fueron escogidos. As, hay una correspondencia entre
selecciones de 3 objetos y selecciones de 2. La conclusin es que
debe haber el mismo nmero de formas de hacer una u otra
seleccin, es decir:
Nmero total de subconjuntos posibles[editar]
Correspondencia entre subconjuntos y sucesiones s/no
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Otra identidad muy famosa se refiere a la cantidad de subconjuntos
que puede tener un conjunto dado. Esta identidad establece
.
Por ejemplo, si n=5:
Frecuentemente, la demostracin de la identidad se reduce a
sustituir x=1, y=1 en el teorema de Newton, aunque tal prueba
impide entender la idea central detrs del resultado.
Partamos
de
un
conjunto
de
elementos.
La
suma
cuenta el nmero total de
subconjuntos posibles, ya que
es el nmero de subconjuntos vacos (slo hay uno).
es el nmero de subconjuntos con un elemento.
es el nmero de subconjuntos con dos elementos.
es el nmero de subconjuntos con tres elementos.
es el nmero de subconjuntos con cuatro elementos.
es el nmero de subconjuntos con cinco elementos (slo
hay uno, el conjunto total).
La veracidad de la identidad quedar establecida si al contar el
nmero total de subconjuntos de una forma distinta, se obtiene que
tal cantidad es 25.
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
Supongamos que el conjunto original es {A, B, C, D, E}. Cada
subconjunto est en correspondencia con una serie de 5 opciones
s/no:
El subconjunto {A, C, D} corresponde a la serie s, no, s, s,
no, ya que en el subconjunto s estn incluidos el primer,
tercer y cuarto elementos del conjunto original, mientras que
no estn incluidos el segundo y el quinto elemento.
Del mismo modo, dada una sucesin de 5 opciones s/no, es posible
recuperar el conjunto que le da origen:
A la serie s, s, no, no, s le corresponde el subconjunto {A,
B, E}.
Por tanto, al corresponder cada subconjunto con una serie de s/no,
se tiene que el nmero de subconjuntos es igual al nmero de series
posibles. Sin embargo, el nmero de formas de hacer 5 elecciones,
cada una con 2 opciones, es 22222 = 25.
La prueba del caso general con conjuntos de cualquier tamao es
directa. Cada subconjunto corresponde a una sucesin de n opciones
s/no, habiendo 222=2n diferentes sucesiones.
Multiconjuntos
repeticin
combinaciones
con
Artculo principal: Combinaciones con repeticin
As como los coeficientes binomiales enumeran formas de tomar
subconjuntos a partir de un conjuto dado, es posible plantear el
problema de determinar el nmero de formas de escoger un
multisubconjunto de un conjunto.
Recordemos que en un multiconjunto es permitido repetir elementos
aunque, al igual que en los conjuntos, el orden en que se mencionan
es irrelevante.
Por ejemplo, {a, e, e, i, o, o, o, u} es el mismo multiconjunto
que {e, i, o, u, a, e, o, o}
Para ilustrar el problema, consideremos el conjunto X={a, b, c, d}.
Listemos todos los posibles multiconjuntos de 3 elementos obtenidos
del conjunto X. Para brevedad, indicaremos las letras como si fuesen
una palabra:
aaa aab aac aad abb abc abd acc acd add
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
bbb bbc bbd bcc bcd bdd ccc ccd cdd ddd
Se recalca que el orden no importa, por esto es que no se lista por
ejemplo, aca ya que el multiconjunto {a, c, a} es el mismo que el
multiconjunto {a, a, c}. Estas selecciones donde se permite
repeticin pero no se toma en cuenta el orden se denominan
combinaciones con repeticin.
El nmero de formas en que se puede extraer un multiconjunto con k
elementos de un conjunto con n elementos se denota4 5
y corresponde al nmero de k-combinaciones con repeticin tomadas
de un conjunto con n elementos.
As, del listado inicial podemos deducir que
. Antes de
establecer una frmula para el clculo directo de combinaciones con
repeticin, plantearemos un ejemplo clsico de problema relacionado
con multiconjuntos.
[Contraer]De
cuntas maneras
repartir 10 caramelos a 4 nios?
se
puede
Vamos a imaginar que los nombres son Alonso,
Beto, Carlos y Daniel (que representaremos como
A, B, C, D).
Una posible forma de repartir los caramelos sera:
dar 2 caramelos a Alonso, 3 a Beto, 2 a Carlos y 3 a
Daniel. Dado que no importa el orden en que se
reparten, podemos representar esta seleccin como
AABBBCCDDD
Otra forma posible de repartir los caramelos podra
ser: dar 1 caramelo a Alonso, ninguno a Beto y
Carlos, los 9 restantes se los damos a Daniel. Esta
reparticin la representamos como
ADDDDDDDDDD
De manera inversa, cualquier serie de 10 letras A,
B, C, D corresponde a una forma de repartir los
IngnieursduMondeNRG
J.R.A.A.
CURSOENLNEAINGENIERA
caramelos. Por ejemplo, la serie AABBBBBDDD
corresponde a:
Dar dos caramelos a Alonso, 5 caramelos a
Beto, ninguno a Carlos y 3 a Daniel.
De esta forma, por el principio de la biyeccin, el
nmero de formas en que se puede repartir los
caramelos es igual al nmero de series de 10 letras
(sin tomar en cuenta el orden) A, B, C, D. Pero cada
una de ellas corresponde a un multiconjunto con 10
elementos, por lo que concluimos que el nmero
total de formas de repartir los caramelos es
La solucin del ejemplo anterior es conceptualmente correcta (da el
resultado mediante una interpretacin combinatoria) pero no es
prctica ya que no proporciona realmente el nmero de formas en
que se puede hacer la reparticin. Para obtener la frmula
procedemos a usar la siguiente estratagema.
Queremos dividir 10 objetos (los caramelos) en 4 grupos. Para ello
colocamos 10 objetos en lnea e insertamos 3 separadores para
dividirlos en 4 secciones. Por ejemplo, si representamos los
caramelos con asteriscos y los separadores con barras,nota 3 los
ejemplos mencionados seran:
AABBBCCDDD **/***/**/***
ADDDDDDDDDD *///*********
AABBBBBDDD **/*****//***
Y cualquier disposicin de 10 asteriscos separados por 3 barras
(permitiendo grupos vacos) corresponde a una forma de repartir y a
su vez, a un multiconjunto:
****/***/**/* AAAABBBCCD (4 caramelos para
Alonso, 3 para Beto, 2 para Carlos y 1 para Daniel)
*****/*****// AAAAABBBBB (5 caramelos para
Alonso y 5 para Beto)
De esta forma, el nmero de formas de repartir corresponde al
nmero de disposiciones de 13 smbolos, de los cuales: 10 son
asteriscos y 3 barras. Pero esto es precisamente el nmero de formas
de elegir 3 objetos de un conjunto con 13 (de las 13 disposiciones se
estn escogiendo cuales 3 sern barras) y por tanto el resultado (el
nmero de ordenamientos) es
IngnieursduMondeNRG
formas.
J.R.A.A.
CURSOENLNEAINGENIERA
Este argumento se puede aplicar en general: repartir k objetos entre
n personas, corresponde a formar multiconjuntos de tamao k (los
karamelos) escogidos de un conjunto con n (los nios), y a su vez
esto puede enumerarse con una serie de k asteriscos y n-1 barras,
que puede realizarse de
Queda establecido as el siguiente teorema.
formas.
El nmero
de multiconjuntos con k elementos escogidos de un
conjunto con n elementos satisface:
Es igual al nmero de combinaciones con repeticin de k
elementos escogidos de un conjunto con n elementos.
Es igual al nmero de formas de repartir k objetos en n
grupos.
Y adems
Notas al pie
1.
Estrictamente hablando, una combinacin es la seleccin de un
subconjunto, de modo que un coeficiente binomial cuenta el nmero
de combinaciones. Sin embargo es comn usar el trmino para
referirse tambin a la cantidad de stas como "combinaciones" en
expresiones como "combinaciones de 5 en 3 es igual a 10".
2.
La forma C(n,k) se prefiere cuando no se dispone de medios
para representar ndices o no se dispone de smbolos matemticos
(por ejemplo, en el texto de un e-mail), sin embargo, la tercera
forma es la ms comn en entornos acadmicos y textos sobre el
tema
3.
La eleccin de asteriscos y barras puede ser sustituida por
cualquier par de smbolos, es frecuente usar tambin 0 en vez de
asterisco y 1 en vez de barras.
IngnieursduMondeNRG
J.R.A.A.
