3 - Combinaciones - Foro fmat.cl

Foro fmat.cl > Sector Preparación Olimpiadas > Sector PreOlímpico > Combinatoria > Material de Entrenamiento

3 - Combinaciones

Opciones

S. E. Puelma Moy... S. E. Puelma Moya Ver Perfil del Miembro Ver los mensajes de este miembro	Apr 2 2006, 05:42 PM Publicado: #1
Dios Matemático Supremo Grupo: Administrador Mensajes: 2.706 Registrado: 13-May 05 Desde: Santiago de Chile Miembro Nº: 10 Nacionalidad: Colegio/Liceo: Sexo:	Ideas previas Con el tema de listas ordenadas y permutaciones, uno podría engañarse y creer que puede deducir el número de cartillas existentes en el juego millonario de azar del Loto. Después de todo, se eligen 6 números entre 39 posibles. Hay un detalle que ahora vamos a estudiar con más cuidado: ¿Qué hacer si el orden en que aparecen los elementos no es relevante? En el juego del Loto el orden es irrelevante. Por ejemplo, si yo juego una cartilla marcando los números 8, 9, 7, 31, 1, 21 en ese orden, y los números sorteados son 31, 21, 7, 1, 9, 8 en ese orden, de todos modos gano el premio mayor. Dicho de otro modo, la información relevante es que hemos elegido un subconjunto de {1, 2, 3, ..., 39} con seis elementos. Esto es precisamente la idea de combinación Combinación Debemos comenzar definiendo qué es una combinación: Si $TEX: $A$$ es un conjunto con $TEX: $n$$ elementos, y si $TEX: $k$$ es un número entero, con $TEX: $0\leq k\leq n$$ , llamaremos una combinación de $TEX: $k$$ elementos de $TEX: $A$$ (o una $TEX: $k-$$ combinación de $TEX: $A$$ ) a un subconjunto de $TEX: $A$$ que tenga $TEX: $k$$ elementos Por ejemplo, todo conjunto $TEX: $A$$ con $TEX: $n$$ elementos, admite una sola 0-combinación: el conjunto vacío $TEX: $\varnothing$$ , y una sola $TEX: $n-$$ combinación: el propio conjunto $TEX: $A$$ . El conjunto {2,5} es una 2-combinación de {1,2,3,4,5}. Este es el concepto por el cual preguntamos para motivar el estudio de la combinatoria: el número de cartillas que pueden ser jugadas en el Loto es igual al número de 6-combinaciones de {1, 2, 3, ..., 39}. En un contexto más general, el número de $TEX: $k-$$ combinaciones de un conjunto se conoce como número combinatorio. Si $TEX: $k$$ y $TEX: $n$$ son enteros, con $TEX: $0\leq k\leq n$$ (en adelante, siempre lo entenderemos así), anotaremos $TEX: $\displaystyle{n\choose k}$$ como el número de $TEX: $k-$$ combinaciones de un conjunto con $TEX: $n$$ elementos. Este es un número combinatorio -por razones obvias- o coeficiente binomial -por el rol que juega en el teorema del binomio de Newton, que no comentaré aquí-. Se lee " $TEX: $n$$ sobre $TEX: $k$$ " ¿Podemos encontrar una forma más explícita para calcular $TEX: $\displaystyle{n\choose k}$$ ? La respuesta es afirmativa, con ayuda de los factoriales, y se puede conseguir con el siguiente proceso: Atendemos nuevamente la pregunta: ¿Cuántas permutaciones de largo $TEX: $k$$ , tomadas de un conjunto con $TEX: $n$$ elementos, existen? De antemano, ya sabemos que la respuesta es $TEX: $\displaystyle{\frac{n!}{(n-k)!}}$$ ; buscamos una nueva respuesta para la misma pregunta. Para construir la lista, vamos a realizar dos pasos: Elegir los $TEX: $k$$ elementos que intervendrán en la lista (se obtiene una $TEX: $k-$$ combinación) Decidir el orden en que aparecerán estos $TEX: $k$$ elementos El primer paso puede hacerse de $TEX: $\displaystyle{n\choose k}$$ formas, y el segundo de $TEX: $k!$$ formas (se trata de una permutación de $TEX: $k$$ elementos ya elegidos). Aplicando la regla del producto, el número de permutaciones de largo $TEX: $k$$ es igual a $TEX: $\displaystyle{{n\choose k}\cdot k!}$$ . Esto es igual a $TEX: $\displaystyle{\frac{n!}{(n-k)!}}$$ , según comentamos al comienzo. Por lo tanto: $TEX: $\displaystyle{{n\choose k}\cdot k!=\frac{n!}{(n-k)!}\Rightarrow{n\choose k}=\frac{n!}{k!\cdot(n-k)!}}$$ La fórmula $TEX: $\displaystyle{{n\choose k}=\frac{n!}{k!\cdot(n-k)!}}$$ es muy útil para probar algunas propiedades por la vía aritmética. Sin embargo, cuando queremos calcular un valor concreto, lo mejor es comenzar con simplificar todo lo que sea posible. No deja de ser importante la interpretación combinatoria de este número: la cantidad de $TEX: $k-$$ combinaciones de un conjunto de $TEX: $n$$ elementos. Esto nos permite deducir algunas propiedades. Como ejercicio propuesto, para entender la deducción de la fórmula, haga un esquema para presentar todas las permutaciones de largo 2, de un conjunto con siete elementos. Comienza indicando todas las 2-combinaciones y luego, haz aparecer las permutaciones de largo 2. Las propiedades de los números combinatorios, aparecen en la lista de ejercicios propuestos. -------------------- Sebastián Elías Puelma Moya Administrador FMAT