Combinación

Una combinación (del latín combinatio 'resumen' ) o muestra desordenada es en combinatoria una selección de objetos de un conjunto básico dado, que (en contraste con la permutación ) no tiene que contener todos los objetos del conjunto básico y en el cual (en contraste a permutación y variación ) el pedido sea no tomada en cuenta. Si los objetos se pueden seleccionar varias veces, se habla de una combinación con repetición . Si, por el contrario, cada objeto solo puede aparecer una vez, se habla de una combinación sin repetición . La determinación del número de combinaciones posibles es una tarea estándar de contar combinatoria .

Definición de términos

Una combinación o muestra desordenada es una selección de objetos de un conjunto de objetos para los que el orden de selección no importa. Sin embargo, si el orden va a desempeñar un papel, se habla de una variación en lugar de una combinación. A diferencia de esto, las combinaciones y variaciones a veces se resumen en la literatura y una variación se denomina "combinación con consideración de la secuencia".${\ Displaystyle k}$${\ Displaystyle n}$

En combinación con la repetición, los objetos se pueden seleccionar varias veces, mientras que en una combinación sin repetición, cada objeto solo puede aparecer una vez. En un modelo de urna , una combinación con repetición corresponde a un sorteo de las bolas con reposición y una combinación sin repetición corresponde a un sorteo sin reposición.

Combinación sin repetición

Las 10 combinaciones sin repetir tres de cinco objetos

número

Los problemas de selección no repetitiva se pueden investigar de dos formas. En el caso clásico, se parte de una variación sin repetición para la cual entre los elementos seleccionados se encuentran opciones. Ahora, sin embargo, los elementos seleccionados se pueden organizar ellos mismos de diferentes formas. Si estos diferentes arreglos son todos irrelevantes, es decir, siempre deben contar como la misma selección de elementos, tenemos que dividir el resultado una vez más y solo obtenerlo. ${\ Displaystyle k}$${\ Displaystyle n}$${\ displaystyle {\ tfrac {n!} {(nk)!}}}$${\ Displaystyle k}$${\ displaystyle k!}$${\ displaystyle k!}$

${\ Displaystyle {\ frac {n!} {(nk)! \, k!}} = {\ frac {n (n-1) (n-2) \ ldots (n-k + 1)} {k!}} = {\ binom {n} {nk}} = {\ binom {n} {k}}}$

Posibilidades, cuyo número también se conoce como coeficiente binomial .

Un segundo enfoque, que se utiliza en particular para la evaluación de los experimentos de Bernoulli, considera la combinación sin repetición como un problema de ordenación. El número de selecciones posibles se puede determinar determinando el número de disposiciones mutuamente distinguibles de objetos seleccionados y no seleccionados, por lo que estos mismos ya no deberían ser distinguibles entre sí, es decir, todo el conjunto inicial sólo se "selecciona" en las dos clases de objetos. (por ejemplo, bola negra con número blanco) y "no seleccionado" (por ejemplo, bola blanca con número negro). Si ahora se investiga cuántas disposiciones diferentes de estas bolas blancas y negras hay, en las que solo su color debería desempeñar un papel, la fórmula anterior resulta de acuerdo con la fórmula para el número de permutaciones de elementos, cada una de las cuales no se puede diferenciar por clase. . Si se trata del número de objetos seleccionados y el número de objetos no seleccionados o viceversa, es irrelevante para el resultado; cuál de los dos subconjuntos del conjunto inicial es el de interés no influye en el número de posibles divisiones. ${\ Displaystyle k}$${\ Displaystyle nk}$

Pantalla de cantidad

La cantidad

${\ Displaystyle {\ bigl \ {} (x_ {1}, x_ {2}, \ ldots, x_ {n}) \ mid x_ {i} \ in \ {0,1 \}, x_ {1} + \ ldots + x_ {n} = k {\ bigr \}}}$

es el "conjunto de todas las combinaciones sin repetición de objetos para la clase " y tiene el número de elementos especificado anteriormente. Una representación alternativa de esta multitud es ${\ Displaystyle n}$${\ Displaystyle k}$

${\ Displaystyle {\ bigl \ {} (z_ {1}, z_ {2}, \ ldots, z_ {k}) \ mid 1 \ leq z_ {1} <z_ {2} <\ dotsb <z_ {k- 1} <z_ {k} \ leq n {\ bigr \}}}$.

Ejemplos de

loto

Si se quiere seleccionar entre objetos sin repetición y sin tener en cuenta el orden, como es el caso, por ejemplo, del sorteo de los números de lotería , existe ${\ Displaystyle 49}$${\ Displaystyle 6}$

${\ displaystyle {\ binom {49} {6}} = {\ frac {49!} {6! \, (49-6)!}} = 13,983,816}$

posibles elecciones. En el caso de la lotería, el orden no importa, por ejemplo si primero se saca el uno y luego el uno o primero el uno y luego el uno , es irrelevante para los números ganadores y la determinación del ganador de la lotería. El número de posibles soluciones se calcula a partir del número de bolas que se pueden sacar primero y luego . Sin embargo, dado que el orden no importa, se debe tener en cuenta que el producto incluye soluciones de igual valor. Con tres números sorteados es el número de posibilidades , pero como el orden del sorteo de las bolas no importa, el producto debe dividirse por el número de posibles órdenes de sorteo . ${\ Displaystyle 9}$${\ Displaystyle 17}$${\ Displaystyle 17}$${\ Displaystyle 9}$${\ Displaystyle 49}$${\ displaystyle 48}$${\ Displaystyle 49 \ cdot 48}$${\ Displaystyle 2 = 1 \ cdot 2 = 2!}$${\ Displaystyle 49 \ times 48 \ times 47}$${\ Displaystyle 6 = 1 \ times 2 \ times 3 = 3!}$

De varias maneras

Cuadro mural con múltiples letras ocultas "Deo gracias"

El fresco de Deo Gracias en la iglesia Wismar Holy Spirit muestra la letra "D" en el medio y una "S" en la parte inferior derecha. Si solo da pasos hacia la derecha o hacia abajo, el resultado es siempre el texto "DEOGRACIAS". Da un total de nueve pasos, cinco de los cuales tiene que dar un paso hacia la derecha y cuatro veces un paso hacia abajo. Por lo tanto hay

${\ displaystyle {9 \ choose 5} = {\ frac {9!} {5! \, 4!}} = 126}$

Opciones. Pero también puedes ir a las otras esquinas con el mismo resultado: cinco veces hacia la derecha y cuatro veces hacia arriba o hacia la izquierda y hacia abajo o hacia la izquierda y hacia arriba. En general, esto da como resultado posibilidades en este ejemplo . Esta tarea generalmente se conoce como el Problema de Manhattan , llamado así por el distrito de Nueva York con su distribución regular de calles.${\ Displaystyle 126 \ cdot 4 = 504}$

Irene Schramm-Biermann puesta de sol de Manhattan

La imagen de la derecha también se relaciona con el problema de Manhattan. Se trata de la secuencia de letras que componen la palabra "MANHATTANSUNSET". El inicio es M en la parte superior izquierda, el objetivo es la T en la parte inferior derecha. Necesita 7 pasos hacia la derecha y 7 pasos hacia abajo, de modo que con n = 7 yk = 7 hay exactamente 3432 formas diferentes de leer MANHATTANSUNSET.

Combinación con repetición

Las 35 combinaciones con repetición de tres de cada cinco objetos.

número

¿Deberían seleccionarse elementos de un conjunto de elementos , por lo que su orden debería seguir siendo irrelevante, pero ahora también se pueden repetir, como B. es posible al arrastrar con reemplazo, la siguiente fórmula resulta para el número de posibilidades (ver multi-set ): ${\ Displaystyle n}$${\ Displaystyle k}$

${\ displaystyle {\ frac {(n + k-1)!} {(n-1)! \, k!}} = {n + k-1 \ elige k} = {n + k-1 \ elige n -1} = \ left (\! \! {N \ choose k} \! \! \ Right)}$

Esto se puede ver cuando cada resultado de los elementos seleccionados de los elementos posibles está representado por una secuencia de símbolos, con símbolos ("N") que representan los elementos del conjunto seleccionado y símbolos ("K") que representan los elementos seleccionados. La secuencia siempre comienza con un símbolo N; el número de K símbolos antes del segundo N símbolo corresponde a la frecuencia con la que se dibujó el primero de los elementos, el número de K símbolos entre el segundo y tercer N símbolos corresponde al segundo de los elementos, y así sucesivamente "N" todos los símbolos se pueden combinar libremente, el número de combinaciones y, por lo tanto, el número de movimientos posibles corresponde a la fórmula dada. ${\ Displaystyle k}$${\ Displaystyle n}$${\ Displaystyle n + k}$${\ Displaystyle n}$${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle n}$${\ Displaystyle n}$

Por ejemplo, al seleccionar 3 de 5 elementos ("1", "2", "3", "4", "5") con reemplazo, el resultado "1, 3, 3" corresponde a la secuencia de símbolos "NKNNKKNN ”, El resultado“ 5, 5, 5 ”de la serie“ NNNNNKKK ”. Hay posibles combinaciones. ${\ Displaystyle {n + k-1 \ elige k} = {7 \ elige 3} = 35}$

Pantalla de cantidad

La cantidad

${\ Displaystyle {\ bigl \ {} (x_ {1}, x_ {2}, \ ldots, x_ {n}) \ mid x_ {i} \ in \ {0,1, \ ldots, k \}, x_ {1} + \ ldots + x_ {n} = k {\ bigr \}}}$

es el "conjunto de todas las combinaciones con repetición de cosas para la clase " y tiene la cantidad de elementos indicada anteriormente. Aquí denota el número de apariciones del -ésimo elemento de la muestra. Una representación alternativa de esta multitud es ${\ Displaystyle n}$${\ Displaystyle k}$${\ Displaystyle x_ {i}}$${\ Displaystyle i}$

${\ Displaystyle {\ bigl \ {} (z_ {1}, z_ {2}, \ ldots, z_ {k}) \ mid 1 \ leq z_ {1} \ leq z_ {2} \ leq \ dotsb \ leq z_ {k-1} \ leq z_ {k} \ leq n {\ bigr \}}}$.

Ejemplos de

Biyección entre combinaciones con repetición de tres de cinco objetos (derecha) y combinaciones sin repetición de tres de siete objetos (izquierda)

Oráculo del oso gomoso

Una aplicación de esto es el llamado oráculo de los ositos de goma , en el que se seleccionan osos de una bolsa de ositos de goma de diferentes colores. Entonces alli esta ${\ Displaystyle k = 5}$${\ Displaystyle n = 5}$

${\ Displaystyle \ left (\! \! {5 \ Choose 5} \! \! \ right) = {\ binom {9} {5}} = {\ frac {9!} {5! \, 4!} } = 126}$

diferentes combinaciones. Hay cinco combinaciones en las que todos los osos tienen el mismo color, combinaciones con dos colores diferentes, con tres colores, con cuatro colores y una con los cinco colores. Si la secuencia fuera importante a la hora de arrastrar, se estaría tratando con una “variación con repetición”, es decir con posibilidades. Cuando se le pregunta sobre el número de posibilidades para elegir cuatro bolígrafos de un stock de bolígrafos en seis colores diferentes, uno llega al mismo número ( mente maestra sin considerar la disposición). Por otro lado, existen posibilidades con la mente maestra "correcta" (teniendo en cuenta el arreglo) . ${\ displaystyle 40}$${\ displaystyle 60}$${\ Displaystyle 20}$${\ displaystyle 5 ^ {5} = 3125}$${\ Displaystyle 126}$${\ Displaystyle 6 ^ {4} = 1296}$

urna

Se saca una bola tres veces de una urna con cinco bolas numeradas y se vuelve a colocar cada vez. Por lo tanto, siempre puede elegir entre cinco bolas para los tres sorteos. Si no tiene en cuenta el orden de los números sorteados, hay ${\ Displaystyle (n = 5)}$${\ Displaystyle (k = 3)}$

${\ Displaystyle \ left (\! \! {5 \ Choose 3} \! \! \ right) = {\ binom {7} {3}} = {\ frac {7!} {4! \, 3!} } = 35}$

diferentes combinaciones. Estas combinaciones con repetición de cinco cosas para la clase de tres, es decir, de tres elementos conjuntos múltiples con elementos de la configuración inicial , se corresponden exactamente con las combinaciones sin repetición de siete cosas para la clase de tres, es decir, el número de de tres elementos subconjuntos de un total de siete -Elemento del conjunto inicial. (La existencia de una biyección puede usarse para probar la fórmula para el número de combinaciones con reemplazo). ${\ displaystyle 35}$${\ Displaystyle \ {1,2,3,4,5 \}}$${\ displaystyle 35}$

cubo

El uso de varios objetos idénticos, como dados con uno a seis ojos , es lo mismo que reemplazar . ¿Cuántos lanzamientos diferentes son posibles con tres dados? En principio, son posibles diferentes lanzamientos si uno lanza un dado tras otro y observa el orden. Si, por otro lado, lanza los tres dados al mismo tiempo, el orden ya no se puede definir de manera significativa. Dado que al lanzar los tres dados al mismo tiempo, por ejemplo, de banda ya no puede distinguirse de la o no, sólo hay ${\ Displaystyle 6 ^ {3} = 216}$${\ Displaystyle 1-1-2}$${\ Displaystyle 1-2-1}$${\ Displaystyle 2-1-1}$

${\ Displaystyle \ left (\! \! {6 \ Choose 3} \! \! \ right) = {\ binom {8} {3}} = {\ frac {8!} {5! \, 3!} } = 56}$

camadas diferentes (distinguibles). No confundir con la suma de los ojos, esta solo puede tomar diferentes valores (de a ). ${\ Displaystyle 16}$${\ Displaystyle 3}$${\ Displaystyle 18}$

literatura

• Martin Aigner : Matemáticas discretas . Vieweg, 2006, ISBN 3-8348-9039-1 . 
• Konrad Jacobs , Dieter Jungnickel : Introducción a la combinatoria . de Gruyter, 2003, ISBN 3-11-016727-1 . 
• Joachim Hartung , Bärbel Elpelt, Karl-Heinz Klösener: Estadística: Enseñanza y manual de estadística aplicada . Oldenbourg, 2005, ISBN 3-486-57890-1 . 

enlaces web

Wikcionario: Combinación  - explicaciones de significados, orígenes de palabras, sinónimos, traducciones

• VM Mikheev: Combinación . En: Michiel Hazewinkel (Ed.): Enciclopedia de Matemáticas . Springer-Verlag y EMS Press, Berlín 2002, ISBN 978-1-55608-010-4 (inglés, en línea ). 
• kfgauss70: Combinaciones con elementos repetidos . En: PlanetMath . (Inglés)
• Eric W. Weisstein : Combinación . En: MathWorld (inglés).

Evidencia individual

1. ↑ Hartung, Elpelt, Klösener: Estadística: enseñanza y manual de estadística aplicada . S. 96 . 
2. ^ Bronstein, Semendjajew: Taschenbuch der Mathematik . Harri Deutsch, 2008, ISBN 3-8171-2007-9 , págs. 810-811 . 
3. ^ Problema de Manhattan