Combinacións

As combinacións son un concepto en matemáticas, máis concretamente en combinatoria, que describe as diferentes formas de escoller un determinado número de obxectos a partir dun conxunto dun determinado tamaño, cando os obxectos son discerníbeis e non importa a orde na que se colocan ou listan os obxectos. O nome completo, aínda que pouco empregado, é combinación sen repetición de n elementos tomados de k en k. Noutras palabras, as combinacións de tamaño k dun conxunto E de cardinal n son os subconxuntos de E que teñen tamaño k.

A diferenza das permutacións, as combinacións só se refiren aos elementos elixidos do conxunto, non á orde na que se escollen. Un exemplo é a man obtida sacando simultaneamente k cartas dunha baralla de n cartas. Neste caso, a orde das cartas non é importante para que o xogador desenvolva a súa estratexia.

As combinacións utilízanse, entre outras cousas,  na probabilidade.

 Definición 
Sexa E un conxunto finito de cardinal n e k un número natural. As combinacións deste conxunto son os seus subconxuntos (ou as súas partes). Denotamos  o conxunto de k-combinacións de E.

 Número de combinacións 

O conxunto  é finito e a súa cardinalidade é o coeficiente binomial , denotado tamén como . Temos: ,Onde  é o número de k-permutacións de E e k! é o factorial de k.

Coa fórmula para , conseguimos , que para  tamén se pode escribir:.

 Cálculo do número de combinacións 
Un algoritmo eficiente para calcular o número  de combinacións de k elementos entre n, utiliza as seguintes identidades (0 ≤ k ≤ n ):,  e .A primeira permite reducir o número de operacións a realizar reducíndoo a k ≤ n/2. Os dous seguintes permiten demostrar:O cálculo pódese realizar mediante un simple bucle iterativo (bucle for).

 Exemplo

Por outra parte


Para valores grandes de n e k, adoita ser máis práctico utilizar as seguintes fórmulas aproximadas (atopamos as xustificacións e outras máis detalladas no artigo coeficiente binomial):

 (para k fixo e n tendendo ao infinito) e (se  e  tenden ao infinito con ) 

 .

 Enumeración de combinacións 
Sexa A un conxunto con n elementos,  un obxecto que non está en A e k un número natural. Entón para formar as partes de  tendo k + 1 elementos, formamos as partes de k + 1 elementos de A, así como as partes de k elementos de A ás que engadimos {a}. Noutras palabras :    (  se k > n )(esta identidade ten como consecuencia directa a fórmula de recorrencia que permite a construción do triángulo de Pascal :  ). Esta identidade pode ser explotada para un algoritmo que enumera combinacións, por exemplo dos n primeiros números enteiros.

 Exemplos
 Sexa A o conxunto de 5 elementos A = { a, b, c, d, e }.
 As combinacións de 2 elementos entre os 5 son :
 as que conteñen dous elementos distintos de a : { b, c }, { b, d }, { b, e }, { c, d }, { c, e }, { d, e },
 as que conteñen a e outro elemento : { a, b }, { a, c }, { a, d }, { a, e },

 As combinacións de 3 elementos escollidos entre os 5 elementos de A son:
 as que conteñen a e outros dous elementos : { a, b, c }, { a, b, d }, { a, b, e }, { a, c, d }, { a, c, e }, { a, d, e },
 as que conteñen tres elementos distintos de a : { b, c, d }, { b, c, e }, { b, d, e }, { c, d, e },

Estas son de feito os complementos das combinacións anteriores.

 Número de combinacións con repetición 

Unha k-combinación con repeticións, ou k-multicombinación, ou multisubconjunto de tamaño k dun conxunto S de tamaño n vén dada por un conxunto de k elementos non necesariamente distintos de S, onde non se ten en conta a orde: dúas secuencias definen o mesmo multiconxunto se se pode obter un do outro permutando os termos. Noutras palabras, é unha mostra k elementos dun conxunto de n elementos  que permiten duplicados (é dicir, con substitución) mais sen ter en conta as diferentes ordes (por exemplo, {2,1,2} = {1). ,2,2}). Asociamos un índice a cada elemento de S e pensamos nos elementos de S como tipos de obxectos, entón temos que  denota o número de elementos de tipo i nun multisubconxunto. O número de multisubconxuntos de tamaño k é daquela o número de solucións enteiras non negativas da ecuación diofántica:

Se S ten n elementos, o número de eses k-multisubconxuntos denotarase mediante

unha notación análoga ao coeficiente binomial que conta k-subconxuntos. Esta expresión, n de selección múltiple k, tamén se pode dar en termos de coeficientes binomiais:

Do mesmo xeito que cos coeficientes binomiais, hai varias relacións entre estas expresións de selección múltiple. Por exemplo, para ,

 Exemplo de contaxe de  multisubconxuntos 
Por exemplo, se tes catro tipos de filloas (n = 4) nun menú para escoller e queres tres filloas (k = 3), o número de formas de escoller as filloas con repetición pódese calcular como

Este resultado pódese verificar enumerando todos os 3-multisubconxuntos do conxunto S = {1,2,3,4}. Isto móstrase na seguinte táboa. A segunda columna mostra as filloas que realmente escolliches, a terceira columna mostra as solucións enteiras non negativas  da ecuación  .

 Núm. 3-multiconxunto solución    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] 
 Notas 

 Véxase tamén 

 Bibliografía 


 Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.



 Outros artigos 
 Multiconxunto.
 Permutación.

 Ligazóns externas 
 Topcoder tutorial de combinatoria  
 Many Tipos comúns de problemas matemáticos de permutación e combinación, con solucións detalladas 
 The Unknown Formula Para combinacións nas que as opcións se poden repetir e a orde "non" importa
 The dice roll with a given sum problem Unha aplicación das combinacións con repetición para lanzar varios dados

Categoría:Combinatoria
Categoría:Wikipedia:Páxinas con traducións non revisadas