Combinación (matemáticas)
En matemáticas y, en concreto, en combinatoria, una combinación es una selección de elementos de un conjunto que tiene miembros distintos, de modo que el orden de selección no importa (a diferencia de las permutaciones). Por ejemplo, dadas tres frutas, digamos una manzana, una naranja y una pera, hay tres combinaciones de dos frutas que se pueden extraer de este conjunto: podemos elegir una manzana y una pera; una manzana y una naranja; o una pera y una naranja. Más formalmente, una k-combinación de un conjunto S es un subconjunto de k elementos distintos de S. Dos combinaciones son idénticas si y solo si cada combinación tiene los mismos miembros. (El orden de elección de los elementos no importa; si el orden importara, elegir la manzana y luego la pera sería distinto de elegir la pera y luego la manzana).
Si el conjunto donde elegir tiene n elementos, el número de k combinaciones (es decir, el número de subconjuntos de k elementos), denotado por o , es igual al coeficiente binomial
que se puede escribir usando factoriales como cuando , y vale cero cuando (no hay ningún subconjunto de más elementos que el total).
Esta fórmula se demostrar como sigue. Primero elegimos k elementos distintos del conjunto de n por orden. Para elegir el primero tenemos n opciones; para el segundo, como ya no podemos elegir el ya hemos elegido, n-1 opciones; para el tercero, n-2, y así hasta el k-ésimo, para el que tenemos n-(k-1)=n-k+1 opciones. En total tenemos n(n-1)···(n-k+1) opciones para elegir los k elementos por orden.
Así tendríamos el número de elecciones ordenadas de k elementos. En efecto, contando de esta forma, estamos contando varias veces la misma selección de elementos simplemente porque los hemos tomado en órdenes distintos. Por ejemplo, estamos contando como distintas las elecciones que toman los mismos elementos pero que el primer elemento que elige una la otra lo elige en último lugar. En general, estamos contando cada combinación (cada elección de un mismo subconjunto de elementos) tantas veces como maneras tenemos de reordenar sus elementos (formas de elegirlos en un cierto orden). Como el número de formas de reordenar un conjunto de k elementos es k!=k(k-1)···1, el número de elecciones de k elementos sin importar su orden (i.e. de k-combinaciones) es
Una combinación es una combinación de n cosas tomadas k a la vez sin repetición. Para referirse a combinaciones en las que se permite la repetición, a menudo se utilizan los términos[1] k-combinación con repetición, k-multiconjunto, [2] o k-selección.[3] Si en el ejemplo anterior de las frutas fuera posible tener más de un ejemplar de fruta de cada tipo habría tres selecciones 2 más: una con dos manzanas, una con dos naranjas y una con dos peras.
Aunque el conjunto de tres frutas era lo suficientemente pequeño para escribir una lista completa de combinaciones, esto se vuelve poco práctico a medida que aumenta el tamaño del conjunto. Por ejemplo, una mano de póquer se puede describir como una combinación de 5 (k = 5) de cartas de una baraja de 52 cartas (n = 52). Las 5 cartas de la mano son todas distintas, y el orden de las cartas en la mano no importa (te repartan las cartas en el orden en que te las repartan, la mano que tienes es la misma). Usando la fórmula de arriba, hay 2.598.960 combinaciones de este tipo y la probabilidad de sacar una mano concreta al azar es por tanto de 1 / 2.598.960.
Número de k combinaciones
editarEl número de k-combinaciones de un conjunto S de n elementos se denota a menudo en textos de combinatoria elemental por , o mediante variaciones como , , , o incluso [4] (la última forma es estándar en los textos en francés, rumano, ruso y chino[5][6]). Sin embargo, el mismo número aparece en muchos otros contextos matemáticos, donde se denota por (a menudo leído como " n sobre k "); en particular, aparece como coeficiente en la fórmula binomial, y de ahí su nombre, coeficiente binomial.
Se puede definir para todos los números naturales k a la vez por la relación (dada por la fórmula binomial)
de lo cual se desprende claramente que
y además
para k > n.
Para ver que estos coeficientes cuentan k-combinaciones de S, primero se puede considerar una colección de n variables distintas Xs etiquetadas por los elementos s de S, y expandir el producto sobre todos los elementos de S:
Expandiendo el producto en una suma, esta tiene 2n sumandos distintos correspondientes a todos los subconjuntos de S: cada sumando es el producto de unas y a cada uno de estos le podemos hacer corresponder el subconjunto . Ahora, si denotamos todas las variables Xs como una variable no etiquetada X, de modo que el producto se convierte en (1 + X)n, la expresión de cada k-combinación de S se convierte indistintamente de sus elementos y su orden en Xk, de modo que el coeficiente de esa potencia en el resultado es igual al número de dichas k-combinaciones.
Los coeficientes binomiales se pueden calcular explícitamente de varias maneras. Para obtenerlos todos para las expansiones de (1 + X), (1 + X)2, ..., (1 + X)n, se puede utilizar (además de los casos básicos ya dados) la relación de recursión
para 0 < k < n, lo cual se sigue algebraicamente de que (1 + X)n = (1 + X)n − 1(1 + X); esto conduce a la construcción del triángulo de Pascal. Una manera combinatoria de justificar esta relación surge de usar que es el número de subconjuntos de k elementos de un conjunto S de n. Así, fijamos un elemento . Los subconjuntos de k elementos de S se pueden separar en aquellos que contengan a s0 y aquellos que no. Podemos calcular la cantidad que hay de los primeros: al haber elegido ya el elemento s0, sólo nos faltan por elegir k-1 elementos de los n-1 restantes. De estos hay . Por otro lado, también podemos contar el número de k-combinaciones que no contienen a s0: hay que elegir un subconjunto de k elementos de los n-1 restantes, esto es, hay opciones. De aquí se sigue que .
Para determinar un coeficiente binomial individual, es más práctico utilizar la fórmula
cuya demostración ya se ha dado en la introducción.
Cuando k es mayor que n/2, la fórmula anterior contiene factores comunes en el numerador y el denominador, y al cancelarlos se obtiene la relación
para 0 ≤ k ≤ n. Esto expresa una simetría que es evidente a partir de la fórmula binomial, y que también puede entenderse en términos de k-combinaciones tomando el complemento de dicha combinación, que es una (n − k)-combinación (cada k-combinación determina una (n - k)-combinación y viceversa: aquellos elementos que no han sido escogidos; por tanto tiene que haber la misma cantidad de cada una).
Finalmente, hay una fórmula que muestra esta simetría directamente y tiene el mérito de ser fácil de recordar:
donde n! denota el factorial de n. Se obtiene de la fórmula anterior multiplicando denominador y numerador por (n − k)! , por lo que de hecho computacionalmente es menos eficiente que esa fórmula.
De las fórmulas anteriores se deducen las relaciones entre los números adyacentes en el triángulo de Pascal en las tres direcciones:
Junto con los casos básicos , estos permiten el cálculo sucesivo de todos los números de combinaciones de un conjunto de un mismo número de elementos (una fila en el triángulo de Pascal), de k-combinaciones de conjuntos de tamaños crecientes y de combinaciones con un complemento de tamaño fijo n − k.
Ejemplo de conteo de combinaciones
editarComo ejemplo concreto, se puede calcular el número de manos de cinco cartas posibles a partir de una baraja estándar de cincuenta y dos cartas como: [7]
Alternativamente, se puede utilizar la fórmula en términos de factoriales y cancelar algunos factores del numerador con algunos del denominador, después de lo cual sólo se requiere la multiplicación de los factores restantes:
Otro cálculo alternativo, equivalente al primero, se basa en escribir
lo cual da
Cuando se evalúa en el siguiente orden, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, esto se puede calcular utilizando sólo aritmética de números enteros. La razón es que cuando se calcula cada división, el resultado intermedio que se produce es en sí mismo un coeficiente binomial, por lo que nunca se producen restos (los coeficientes binomiales son por definición el número de combinaciones de un conjunto, es decir, números enteros).
Utilizando la fórmula simétrica en términos de factoriales sin realizar simplificaciones se obtiene un cálculo bastante extenso:
Enumeración de k-combinaciones
editarSe pueden enumerar todas las k-combinaciones de un conjunto dado S de n elementos en un orden fijo, lo que establece una biyección de un intervalo de números enteros con el conjunto de esas k-combinaciones. Suponiendo que S es un conjunto ordenado, por ejemplo S = {1, 2, ..., n}, hay dos posibilidades naturales para ordenar sus k combinaciones: comparando primero sus elementos más pequeños (como en las ilustraciones anteriores) o comparando primero sus elementos más grandes. La última opción tiene la ventaja de que agregar un nuevo elemento más grande a S no cambiará la parte inicial de la enumeración, sino que sólo agregará las nuevas k-combinaciones del conjunto más grande después de las anteriores. Repitiendo este proceso, la enumeración puede extenderse indefinidamente con k-combinaciones de conjuntos cada vez más grandes. Si además se toman los intervalos de los números enteros comienzando en el 0, entonces la i-ésima k-combinación de la enumeración se puede calcular fácilmente a partir de i, y la biyección así obtenida se conoce como sistema numérico combinatorio. También se conoce como "rango"/"ranking" y "unranking" en matemáticas computacionales. [8] [9]
Hay muchas formas de enumerar k-combinaciones. Una forma es rastrear los números de índice k de los elementos seleccionados, comenzando con {0 .. k −1} (basado en cero) o {1 .. k } (basado en uno) como la primera k-combinación permitida. Luego, pasar repetidamente a la siguiente k-combinación permitida incrementando el número de índice más pequeño para el cual esto no crearía dos números de índice iguales y, al mismo tiempo, restableciendo todos los números de índice más pequeño a sus valores iniciales.
Combinaciones con repetición
editarUna k-combinación con repetición, o k-multicombinación, o multisubconjunto de tamaño k de un conjunto S de tamaño n queda definida por un conjunto de k elementos no necesariamente distintos de S, donde no se tiene en cuenta el orden: dos secuencias definen el mismo multiconjunto si una puede obtenerse de la otra permutando los términos. En otras palabras, es una elección de k elementos de un conjunto de n elementos que permite duplicados (es decir, con reemplazo) pero ignora ordenamientos diferentes (por ejemplo, {2,1,2} = {1,2,2}). Si se asocia un índice a cada elemento de S y se piensa en los elementos de S como tipos de objetos, entonces podemos denotar por el número de elementos del tipo i en un multisubconjunto.
Volviendo al ejemplo de las frutas de la introducción, teníamos tres frutas: una manzana, una naranja y una pera. Las 2-combinaciones eran elecciones de subconjuntos de dos elementos (de dos frutas distintas). Para entender las k-multicombinaciones, o multiconjuntos de k elementos, supóngase que tenemos una cantidad arbitrariamente grande de esas frutas (las manzanas, naranjas y peras son los tipos de fruta anteriores). Las 2-multicombinaciones se corresponderían con elegir dos frutas cualesquiera, permitiendo duplicados: podemos tomar dos manzanas, dos naranjas o dos peras además de las 2-combinaciones. Las k-multicombinaciones se corresponderían con tomar k frutas cualesquiera, permitiendo repetir tipos.
Otra manera de verlo es que el número de multisubconjuntos de tamaño k de un conjunto de tamaño n es el número de soluciones enteras no negativas (lo que permite cero) de la ecuación diofántica: [10]
En efecto, el conjunto es el conjunto de tipos de objetos que hay para elegir. De cada tipo i tenemos que elegir una cantidad xi de manera que en total la cantidad de objetos elegidos sea k, es decir, imponemos que
Si S tiene n elementos, el número de k- multisubconjuntos se denota por
una notación análoga al coeficiente binomial, que cuenta k-subconjuntos. Esta expresión también se puede dar en términos de coeficientes binomiales:
Esta relación se puede demostrar fácilmente utilizando una representación conocida como barras y estrellas:[11]
Demostración:
Podemos representar una solución de la ecuación diofántica anterior como sigue. Dibujamos estrellas, luego un separador (una barra), luego otras estrellas, luego otra barra, y así sucesivamente. El número total de estrellas en esta representación es k y el número total de barras, n - 1 (pues una separación en n partes necesita n - 1 separadores). Así pues, una secuencia de k + n - 1 símbolos (estrellas y barras) corresponde a una solución de la ecuación si contiene k estrellas. Cualquier solución se puede representar eligiendo k de las k + n - 1 posiciones para ser ocupadas por estrellas, y rellenando las otras con barras. Por ejemplo, la solución de la ecuación (n = 4 y k = 10) se puede representar por
☆☆☆|☆☆||☆☆☆☆☆.
Así pues, hay una biyección entre k-multiconjuntos de un conjunto de n elementos y colocaciones de k estrellas en una lista de k + n - 1 símbolos, por lo que hay la misma cantidad de una cosa que da la otra. Pero la segunda cosa son el número de subconjuntos de k elementos de uno de k + n - 1 elementos, es decir, viene dado, por definición, por
Esto ilustra que .
Igual que con los coeficientes binomiales, existen varias relaciones entre estas expresiones de elección múltiple. Por ejemplo, para , se satisface que
Esta identidad se desprende del intercambio de las estrellas y las barras en la representación anterior.[12]
Ejemplo de conteo de multisubconjuntos
editarPor ejemplo, si hay cuatro tipos de donuts (n = 4) en un menú para elegir y se quieren tres donuts (k = 3), el número de formas de elegir las donuts (con repetición porque podemos pedir el mismo más de una vez) se puede calcular como
Este resultado se puede verificar enumerando todos los 3-multisubconjuntos del conjunto S = {1,2,3,4}. Esto se muestra en la siguiente tabla.[13] La segunda columna enumera los donuts que realmente eligió, la tercera columna muestra las solución entera no negativa de la ecuación que se corresponde con la elección y la última columna da la representación de las soluciones mediante estrellas y barras. [14]
No. | 3-multiset | Eq. solution | Stars and bars |
---|---|---|---|
1 | {1,1,1} | [3,0,0,0] | |
2 | {1,1,2} | [2,1,0,0] | |
3 | {1,1,3} | [2,0,1,0] | |
4 | {1,1,4} | [2,0,0,1] | |
5 | {1,2,2} | [1,2,0,0] | |
6 | {1,2,3} | [1,1,1,0] | |
7 | {1,2,4} | [1,1,0,1] | |
8 | {1,3,3} | [1,0,2,0] | |
9 | {1,3,4} | [1,0,1,1] | |
10 | {1,4,4} | [1,0,0,2] | |
11 | {2,2,2} | [0,3,0,0] | |
12 | {2,2,3} | [0,2,1,0] | |
13 | {2,2,4} | [0,2,0,1] | |
14 | {2,3,3} | [0,1,2,0] | |
15 | {2,3,4} | [0,1,1,1] | |
16 | {2,4,4} | [0,1,0,2] | |
17 | {3,3,3} | [0,0,3,0] | |
18 | {3,3,4} | [0,0,2,1] | |
19 | {3,4,4} | [0,0,1,2] | |
20 | {4,4,4} | [0,0,0,3] |
Número de formas de colocar objetos en contenedores
editarUna combinación también puede pensarse como una selección de dos conjuntos de elementos: los que van en el contenedor "de elementos elegidos" y los que van en el contenedor "de elementos no elegidos". Esto se puede generalizar a cualquier número de contenedores con la restricción de que cada artículo debe ir exactamente a un contenedor. El número de formas de colocar objetos en contenedores viene dado por el coeficiente multinomial
donde n es el número de artículos, m es el número de contenedores y es el número de artículos que van al contenedor i.
Una forma de ver por qué se cumple esta ecuación es numerar primero los objetos arbitrariamente del 1 al n y poner los objetos con números En el primer contenedor, en orden, los objetos con números en el segundo contenedor en orden, y así sucesivamente. Hay numeraciones distintas, pero muchas de ellas son equivalentes, porque lo que importa es el conjunto de elementos en un contenedor, no su orden en el mismo. Cada permutación del contenido de cada contenedor produce una forma equivalente de colocar los elementos en los contenedores. Sabemos qque el número de maneras de reordenar elementos es . Como resultado, cada clase de equivalencia consta de numeraciones distintas, y el número de clases de equivalencia es .
El coeficiente binomial es el caso especial en el que k elementos entran en el contenedor elegido y el resto ( ) de los artículos van al contenedor de no elegidos. En ese caso, la fórmula anterior recupera la del coeficiente binomial:
Véase también
editarNotas y referencias
editar- ↑ When the term combination is used to refer to either situation (as in (Brualdi, 2010)) care must be taken to clarify whether sets or multisets are being discussed.
- ↑ Mazur, 2010, p. 10
- ↑ Ryser, 1963, p. 7 also referred to as an unordered selection.
- ↑ Uspensky, 1937, p. 18
- ↑ High School Textbook for full-time student (Required) Mathematics Book II B (en chino) (2nd edición). China: People's Education Press. June 2006. pp. 107-116. ISBN 978-7-107-19616-4.
- ↑ 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press). People's Education Press. p. 21.
- ↑ Mazur, 2010, p. 21
- ↑ Lucia Moura. «Generating Elementary Combinatorial Objects». Site.uottawa.ca. Archivado desde el original el 9 de octubre de 2022. Consultado el 10 de abril de 2017.
- ↑ «SAGE : Subsets» (PDF). Sagemath.org. Consultado el 10 de abril de 2017.
- ↑ Brualdi, 2010, p. 52
- ↑ In the article Stars and bars (combinatorics) the roles of n and k are reversed.
- ↑ Benjamin y Quinn, 2003, p. 72 (identity 145)
- ↑ Benjamin y Quinn, 2003, p. 71
- ↑ Mazur, 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.
Bibliografía
editar- Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7.
- Brualdi, Richard A. (2010), Introductory Combinatorics (5th edición), Pearson Prentice Hall, ISBN 978-0-13-602040-0.
- Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
- Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5.
- Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America.
- Uspensky, James (1937), Introduction to Mathematical Probability, McGraw-Hill.
Enlaces externos
editar- Tutorial de Topcoder sobre combinatoria
- Muchos tipos de problemas comunes sobre permutaciones y combinaciones, con soluciones detalladas
- La fórmula desconocida para combinaciones en las que las elecciones se pueden repetir y el orden no importa
- Problema del lanzamiento de dados con una suma dada Una aplicación de las combinaciones con repetición al lanzamiento de múltiples dados