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.

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^[1][2] ${\displaystyle {\mathcal {P}}_{k}(E)}$ o conxunto de k-combinacións de E.

O conxunto ${\displaystyle {\mathcal {P}}_{k}(E)}$ é finito e a súa cardinalidade é o coeficiente binomial ${\displaystyle {n \choose k}}$, denotado tamén como ${\displaystyle C_{n}^{k}}$. Temos:

${\displaystyle C_{n}^{k}={n \choose k}={\frac {A_{n}^{k}}{k!}}}$ ,

Onde ${\displaystyle A_{n}^{k}}$ é o número de k-permutacións de E e k! é o factorial de k. Coa fórmula para ${\displaystyle A_{n}^{k}={\frac {n!}{(n-k)!}}}$, conseguimos ${\displaystyle {n \choose k}={\frac {n(n-1)\ldots (n-k+1)}{k!}}}$, que para k ≤ n tamén se pode escribir:

${\displaystyle {n \choose k}={\frac {n!}{k!(n-k)!}}}$.

Un algoritmo eficiente para calcular o número ${\displaystyle {\binom {n}{k}}}$ de combinacións de k elementos entre n, utiliza as seguintes identidades (0 ≤ k ≤ n ):

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

${\displaystyle {\binom {10}{7}}=?\quad 10-7=3<7,\quad {\binom {7}{0}}=1\Rightarrow {\binom {8}{1}}={\frac {8}{1}}\times 1=8\Rightarrow {\binom {9}{2}}={\frac {9}{2}}\times 8=36\Rightarrow {\binom {10}{3}}={\frac {10}{3}}\times 36=120\Rightarrow {\binom {10}{7}}=120.}$

Por outra parte

${\displaystyle {\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):

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

${\displaystyle {\binom {n}{k}}{\sim }{\frac {1}{\sqrt {2\pi \alpha (1-\alpha )n}}}\left({\frac {1}{\alpha ^{\alpha }(1-\alpha )^{1-\alpha }}}\right)^{n}}$ .

Sexa A un conxunto con n elementos, a un obxecto que non está en A e k un número natural. Entón para formar as partes de ${\displaystyle 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 :

(esta identidade ten como consecuencia directa a fórmula de recorrencia que permite a construción do triángulo de Pascal : ${\displaystyle {\tbinom {n+1}{k+1}}={\tbinom {n}{k+1}}+{\tbinom {n}{k}}}$ ). 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 },

${\displaystyle {5 \choose 2}={4 \choose 2}+{4 \choose 1}=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 },

${\displaystyle {5 \choose 3}={4 \choose 2}+{4 \choose 3}=6+4=10.}$

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

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 ${\displaystyle 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:^[3]

$${\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}$$

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

$${\displaystyle \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,^[4] tamén se pode dar en termos de coeficientes binomiais:

$${\displaystyle \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 ${\displaystyle n\geq 1,k\geq 0}$,

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

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

${\displaystyle \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.^[5] A segunda columna mostra as filloas que realmente escolliches, a terceira columna mostra as solucións enteiras non negativas ${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$ da ecuación ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$ ^[6].

• 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 ed.). 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. 

• Multiconxunto.
• Permutación.

• 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