Ingenieria En Sistemas
Páginas: 9 (2215 palabras)
Publicado: 25 de julio de 2012
Coeficientes
Los coeficientes binomiales o combinaciones son una serie de números estudiados en combinatoria que indican el 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 suelen usar otras definiciones equivalentes.
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. Al momento 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 losobjetos, ú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 {A, B, C, D, E}, sino que cada subconjunto está contado 6 veces, por loque 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 elección (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 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
k! = 1×2×3×...× k
Concluimos que el número de subconjuntos con k elementos,escogidos de un conjunto con elementos es
[pic].
Multiplicando el numerador y el denominador de la fracción por 1×2×3×···×(n-k)
[pic]
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):
|Elcoeficiente binomial [pic] está dado por la fórmula [pic] |
El teorema de Newton y coeficientes multinomiales
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 definicionesanteriores no es evidente.
|El coeficiente binomial [pic] es el coeficiente del término [pic] obtenido al desarrollar [pic] |
Por ejemplo, si desarrollamos (x+y)5 obtenemos:
(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5,
por tanto, al ser 10 el coeficiente de x³y², concluimos que C(5,3)=10.
[pic]
[pic]
Desarrollo de (x+y)³
La afirmación de que estadefinició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 coeficientes binomiales o combinaciones son una serie de números estudiados en combinatoria que indican el 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 suelen usar otras definiciones equivalentes.
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. Al momento 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 losobjetos, ú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 {A, B, C, D, E}, sino que cada subconjunto está contado 6 veces, por loque 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 elección (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 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
k! = 1×2×3×...× k
Concluimos que el número de subconjuntos con k elementos,escogidos de un conjunto con elementos es
[pic].
Multiplicando el numerador y el denominador de la fracción por 1×2×3×···×(n-k)
[pic]
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):
|Elcoeficiente binomial [pic] está dado por la fórmula [pic] |
El teorema de Newton y coeficientes multinomiales
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 definicionesanteriores no es evidente.
|El coeficiente binomial [pic] es el coeficiente del término [pic] obtenido al desarrollar [pic] |
Por ejemplo, si desarrollamos (x+y)5 obtenemos:
(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5,
por tanto, al ser 10 el coeficiente de x³y², concluimos que C(5,3)=10.
[pic]
[pic]
Desarrollo de (x+y)³
La afirmación de que estadefinició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...
Leer documento completo
Regístrate para leer el documento completo.