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 \mathcal P_k(E) o conxunto de *k*-combinacións de *E.*

## Número de combinacións 
O conxunto \mathcal P_k(E) é finito e a súa cardinalidade é o coeficiente binomial {n \choose k}, denotado tamén como C_n^k. Temos:C_n^k={n \choose k}=\frac{A_n^k}{k!} ,Onde A_n^k é o número de *k*-permutacións de *E* e *k*! é o factorial de *k*.

Coa fórmula para A_n^k=\frac{n!}{(n-k)!}, conseguimos {n \choose k}=\frac{n(n-1)\ldots (n-k+1)}{k!}, que para  tamén se pode escribir:{n \choose k}=\frac{n!}{k!(n-k)!}.

## Cálculo do número de combinacións 
Un algoritmo eficiente para calcular o número \binom n k de combinacións de *k* elementos entre *n*, utiliza as seguintes identidades (0 ≤ *k* ≤ *n* ):
\binom n k = \binom n{n-k}, \binom{n+1}{k+1} = \frac{n+1}{k+1}\binom n k e \binom n 0 = 1.
A primeira permite reducir o número de operacións a realizar reducíndoo a *k* ≤ *n*/2. Os dous seguintes permiten demostrar:

\binom n k = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \cdots \cdot \frac{n}{k}

O cálculo pódese realizar mediante un simple bucle iterativo (bucle for).

; Exemplo
: 
\binom{10}7=?\quad 10-7=3
Por outra parte
: 
\binom{10}7=\dfrac{10\cdot 9 \cdot 8}{3\cdot 2 \cdot 1}=120.

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):

:{n \choose k} \sim n^k/k! (para *k* fixo e *n* tendendo ao infinito) e (se  e  tenden ao infinito con 
k/n \rightarrow \alpha \in ]0;1[
) 

:
\binom nk
{\sim} 
\frac{1}{\sqrt {2\pi \alpha(1-\alpha)n}}\left( \frac{1}{\alpha^{\alpha}(1-\alpha)^{1-\alpha}} \right)^n

 .

## 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 A\cup\{a\} 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 :

\mathcal P_{k+1}(A\cup\{a\})=\mathcal P_{k+1}(A)\cup\left\{X\cup\{a\}\mid X\in\mathcal P_k(A)\right\}
&nbsp;&nbsp;&nbsp;&nbsp;( \mathcal P_{k}(A)=\varnothing se *k* > *n* )
(esta identidade ten como consecuencia directa a fórmula de recorrencia que permite a construción do triángulo de Pascal : 
\tbinom{n+1}{k+1}=\tbinom{n}{k+1}+\tbinom nk
 ). 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* },
::{5\choose2}={4\choose2}+{4\choose1}=6+4=10.
:* 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* },
::{5\choose3}={4\choose2}+{4\choose3}=6+4=10.
::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 x_i 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:

x_1 + x_2 + \ldots + x_n = k.

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

\left(\!\!\binom{n}{k}\!\!\right),

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:

\left(\!\!\binom{n}{k}\!\!\right)=\binom{n+k-1}{k}.

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

\left(\!\!\binom{n}{k}\!\!\right)=\left(\!\!\binom{k+1}{n-1} \!\!\right).

### 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

:\left(\!\!\binom{4}{3}\!\!\right) = \binom{4+3-1}3 = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20.

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 [x_1,x_2,x_3,x_4] da ecuación x_1 + x_2 + x_3 + x_4 = 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