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] $𝒫_{k} (E)$ o conxunto de k-combinacións de E.

Número de combinacións

Modelo:Ap

O conxunto

𝒫_{k} (E)

é finito e a súa cardinalidade é o coeficiente binomial

(\binom{n}{k})

, denotado tamén como

C_{n}^{k}

. Temos:

C_{n}^{k} = (\binom{n}{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

(\binom{n}{k}) = \frac{n (n - 1) \dots (n - k + 1)}{k!}

, que para Modelo:Math tamén se pode escribir:

(\binom{n}{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 \dots \cdot \frac{n}{k}$

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

Exemplo: $(\binom{10}{7}) = ? 10 - 7 = 3 < 7, (\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

(\binom{10}{7}) = \frac{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):

(\binom{n}{k}) \sim n^{k} / k!

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

k / n \to α \in] 0; 1 [

)

(\binom{n}{k}) \sim \frac{1}{\sqrt{2 π α (1 - α) n}} {(\frac{1}{α^{α} (1 - α)^{1 - α}})}^{n}

.

Enumeración de combinacións

Sexa A un conxunto con n elementos, Modelo:Math 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 :

$𝒫_{k + 1} (A \cup {a}) = 𝒫_{k + 1} (A) \cup {X \cup {a} ∣ X \in 𝒫_{k} (A)}$ ( $𝒫_{k} (A) = \emptyset$ se k > n )

(esta identidade ten como consecuencia directa a fórmula de recorrencia que permite a construción do triángulo de Pascal :

(\binom{n + 1}{k + 1}) = (\binom{n}{k + 1}) + (\binom{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 },

(\binom{5}{2}) = (\binom{4}{2}) + (\binom{4}{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 },

(\binom{5}{3}) = (\binom{4}{2}) + (\binom{4}{3}) = 6 + 4 = 10 .

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

Número de combinacións con repetición

Modelo:Ver tamé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:^[3]

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

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

$((\binom{n}{k})),$

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:

$((\binom{n}{k})) = (\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 \geq 1, k \geq 0$ ,

$((\binom{n}{k})) = ((\binom{k + 1}{n - 1})) .$

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

((\binom{4}{3})) = (\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 $[x_{1}, x_{2}, x_{3}, x_{4}]$ da ecuación $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

Modelo:Listaref

Véxase tamén

Bibliografía

Modelo:Cita libro
Modelo:Cita libro
Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
Modelo:Cita libro
Modelo:Cita libro
Modelo:Cita libro

Outros artigos

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

Modelo:Control de autoridades

[1] Modelo:Cita libro

[2] Modelo:Cita libro

[3] Modelo:Harvnb

[4] Modelo:Harvnb

[5] Modelo:Harvnb

[6] Modelo:Harvnb

[1]

[2]

[3]

[4]

[5]

[6]

Combinacións

Índice

Definición

Número de combinacións

Cálculo do número de combinacións

Enumeración de combinacións

Número de combinacións con repetición

Exemplo de contaxe de multisubconxuntos

Notas

Véxase tamén

Bibliografía

Outros artigos

Ligazóns externas

Menú de navegación

Combinacións

Definición

Número de combinacións

Cálculo do número de combinacións

Enumeración de combinacións

Número de combinacións con repetición

Exemplo de contaxe de multisubconxuntos

Notas

Véxase tamén

Bibliografía

Outros artigos

Ligazóns externas

Menú de navegación

Procura