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