Diferencia entre revisiones de «Matemáticas/Combinatoria y optimización»
Contenido eliminado Contenido añadido
m m |
+información importada de eswiki, concretamente de http://es.wikipedia.org/w/index.php?title=Tri%C3%A1ngulo_de_Pascal&oldid=60148840 bajo licencia GFDL y CC SA 3.0 |
||
Línea 9:
===Demostración===
Tenemos <math>n_{1}</math> opciones para el primer paso para cada uno de estas opciones, <math>n_{2}</math> para el segundo, (...). Por inducción se puede probar que tenemos <math>n_{1}, n_{2},...,n_{t}</math>
== Combinaciones sin repetición ==
Los [[Coeficiente binomial|coeficientes binomiales]] son la base misma de la [[combinatoria]]. Veamos por qué:
Tomemos un [[binomio]], por ejemplo <math>(a+b)^3</math>, y desarrollémoslo:
::<math>(a+b)^3 = (a+b)\cdot (a+b) \cdot (a+b)</math>
luego quitemos las paréntesis, pero sin cambiar el orden en los productos, es decir sin aplicar la [[conmutatividad]]:
::<math> (a+b)\cdot (a+b) \cdot (a+b)= (a a + ab + ba + bb )\cdot (a+b) </math>
::<math> = aaa + aab + aba + abb + baa + bab + bba + bbb \quad </math>
Y agrupemos los términos que contienen el mismo número de a, (y de b):
::<math> = aaa + (aab + aba + baa) + (abb + bab + bba) + bbb \quad</math>
El primer [[paréntesis]] contiene todas las palabras constituidas de un ''b'' y dos ''a''. En este caso, es fácil ver que hay exactamente tres. En el caso general, para contar las palabras, hay que aplicar la conmutatividad, pues las palabras que contienen el mismo número de a y b darán el mismo término:
::<math> = 1\cdot a^3 + 3\cdot a^2b + 3\cdot ab^2 + 1\cdot b^3 </math>
{|
|El primer factor 3, que es
|<math>{3 \choose 1}</math>
|cuenta las tres palabras mencionadas (aab, aba y baa).
|}
{|
|El segundo factor 3, que es
|<math>{3 \choose 2}</math>
|cuenta las palabras hechas de dos ''b'' y un ''a'' (abb, bab y bba).
|}
Obviamente, sólo hay una palabra de tres letras constituidas de ''a'' solamente, y esto corresponde al monomio '''1·a³''', con 1 = <math>{3 \choose 0}</math> ( «0 » por ''ninguna b'').
En vez de hablar de palabras formadas con ''a'' y ''b'', es equivalente imaginar una hilera de ''n'' cajones inicialmente vacíos, y ''p'' bolas intercambiables que se tienen que repartir, en cada [[cajón]] no cabiendo más de una. Se trata en todos casos de repartir ''p'' objetos entre ''n'' sitios posibles, o de escoger un grupo de ''p'' objetos/sitios entre ''n'' objetos/sitios. De ahí la apelación ''p entre n''.
Todo lo anterior lleva al '''teorema''':
{|
| Hay exactamente
|<math>{n \choose p}</math>
| maneras de escoger un conjunto de ''p'' elementos entre ''n'' elementos.
|}
En matemática anormal, se prefiere hablar de [[conjunto]]s:
{|
|Existen
|<math>{n \choose p}</math>
|subconjuntos de cardinal p en un conjunto de cardinal n.
|}
Este punto de vista permite hallar la fórmula para los [[Distribución binomial|coeficientes binomiales]]. En efecto, para elegir el « primer » elemento, hay ''n'' posibilidades, luego para escoger el segundo quedan ''n-1'' posibilidades y así sucesivamente hasta el elemento número ''p'', que tiene ''n-p+1''. El orden en el que se ha elegido estos ''p'' elementos no importa, se podía haber obtenido el mismo [[subconjunto]] de ''p'' elementos en otro orden. Hay [[factorial|p!]] [[permutación y grupo simétrico|permutaciones]] posibles de estos ''p'' elementos, es decir p! maneras de obtener el mismo conjunto.
{|
| Por tanto hay
|<math> \frac {n \cdot (n-1) \cdot (n-2) ... (n-p+1)} {p!} </math>
|subconjuntos posibles.
|}
En conclusión:
<center>
<math> {n\choose p} = \frac {n \cdot (n-1) \cdot (n-2) ... (n-p+1)} {p \cdot (p-1) \cdot (p-2) ... 2 \cdot 1} = \frac {n!} {p! \cdot (n-p)!} </math>
</center>
Verifiquémoslo en un ejemplo:
{|
|
|<math>{5\choose 2} = \frac { 5!} {2! 3!} = \frac {5 \times 4 \times 3 \times 2} {2 \times 3 \times 2} = 10 </math>
|}
En el triángulo, el valor en la quinta línea y segunda columna es 10. Para rematar, listemos las palabras de cinco letras formadas de 2 ''a'' y 5-2 = 3 ''b'' (en el orden alfabético, o en el orden creciente considerando que ''a'' es la cifra ''0'' y ''b'' la cifra ''1''):<br />
aabbb, ababb, abbab, abbba, baabb, babab, babba, bbaab, bbaba, bbbaa.
La fórmula permite verificar todas las propiedades del párrafo anterior, sin embargo se puede prescindir de los cálculos en la mayoría de los casos, con tal de manipular los conceptos idóneos.
[[Archivo:partición en dos de un conjunto.png|right]]
Un [[subconjunto]] A de E define una ''partición'' de E en dos partes E = A ∪ B , con A ∩ B = {}= ∅ ([[conjunto vacío]]). Aquí <math> B = \overline{A}</math> es el complementario de A en E.
Da lo mismo escoger los ''p'' elementos de A que los ''n-p'' elementos de <math>\overline{A}</math>.
{|
|Esto justifica, sin cálculo, la simetría
|<math>{n\choose {n-p}} ={ n\choose p}</math>.
|}
{|
|Si p > n, no hay subconjuntos de E con ''p'' elementos, porque E contiene sólo ''n'', luego
|<math> {n\choose p} = 0</math>
|}
{|
|También son evidentes las igualdades
|<math> {n\choose 1} = n</math>
| y
|<math> {n\choose 0} = 1</math>
| porque, en el primer caso,
|}
hay tantas maneras de escoger subconjunto de tamaño 1 que de elementos de E, y en el segundo caso, sólo existe un conjunto con cero elemento: el conjunto vacío.
La regla fundamental también tiene explicación gráfica:
Prueba: se escoge un elemento ''e'' cualquiera de ''E'', que contiene n+1 elementos: E = E' ∪ {e}. Luego se consideran los subconjuntos ''A'' de ''E'' de cardenal p+1. Son de dos tipos: o contienen e, o no.
{|
|Si ''e'' ∈ ''A'', entonces falta elegir ''p'' elementos de E' para completar ''A''. Hay
|<math> {n\choose p}</math>
| posibilidades.
|}
{|
|Si ''e'' ∉ A, entonces falta elegir ''p+1'' elementos de E' para definir ''A''. Hay
|<math> {n\choose {p+1}}</math>
| posibilidades.
|}
Sumando los dos casos, se obtiene todos las partes de p+1 elementos de E, constituido de n+1 elementos.
{|
|Hay por tanto
|<math> {{n+1}\choose {p+1}} = {n\choose {p+1}}+ {n\choose p}</math>
|}
Un ejemplo:
[[Archivo:suma de binomiales figura.png]]
Aquí va una propiedad [[aritmética]], sin interpretación geométrica: cuando '''n es primo''', los coeficientes binomiales en la línea ''n'' son divisibles por ''n'', excepto los dos ''bordes'' de la misma (que valen 1).
Escrito formalmente:
{{teorema
|titulo=
|enunciado=Si ''p'' es primo entonces ''p'' divide a <math>{p\choose k}</math> para ''k''= 2, 3, ..., p-1.
|demo=En la fracción <math>\frac {n!} {p! (n-p)!} </math> el factor primo ''n'' aparece una vez en el numerador y jamás en el denominador. (El denominador es un producto de números entre 1 y n-1). Por tanto la fracción es divisible por n.
}}
[[Archivo:triángulo de Pascal con n primo.png|right]]
En la figura, los ejemplos están en verde, y los contraejemplos (cuando n no es primo y p divide n) en amarillo.
| |||