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

Número de combinacións

Artigo principal: coeficiente binomial.

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)!}}}$.

Cálculo do número de combinacións

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

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$, ${\displaystyle {\binom {n+1}{k+1}}={\frac {n+1}{k+1}}{\binom {n}{k}}}$ e ${\displaystyle {\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:

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

${\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}}$ .

Enumeración de combinacións

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 :

${\displaystyle {\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\}}$    ( ${\displaystyle {\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 : ${\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.

Número de combinacións con repetición

Véxase tamén: multiconxunto.

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).}$$

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

${\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].

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

1. Mathématiques concrètes (en francés). Ed. Techniques Ingénieur. 
2. Gianella, Hervé; Krust, Romain; Taieb, Frank; Tosel, Nicolas (2001). Problèmes choisis de mathématiques supérieures (en francés). Springer Science & Business Media. p. 120. ISBN 9783540423355. 
3. Brualdi 2010, p. 52
4. Benjamin & Quinn 2003, p. 70
5. Benjamin & Quinn 2003, p. 71
6. Mazur 2010, p. 10

Véxase tamén

Bibliografía

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

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