Nomeemos as pessoas como A,B,C,D,E,F. Uma boa dica é armarmos uma tabela de "dupla entrada". Assim teremos:
| A | B | C | D | E | F | |
| A | 1 | 2 | 3 | 4 | 5 | |
| B | 1 | 6 | 7 | 8 | 9 | |
| C | 2 | 3 | 10 | 11 | 12 | |
| D | 4 | 5 | 6 | 13 | 14 | |
| E | 7 | 8 | 9 | 10 | 15 | |
| F | 11 | 12 | 13 | 14 | 15 |
Verificamos que as partidas ficam determinadas à esquerda ou à direita da diagonal (duplas inexistentes). Se o campeonato tiver um turno só, basta selecionar uma delas.
Assim, se escolhermos a da direita temos: AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF.
Os 6 jogadores jogam cada um 5 vezes perfazendo um total de 15 partidas, conforme nos mostra a tabela.
Se os jogadores fossem desistindo de participar do campeonato e fossemos fazendo uma tabela de dupla entrada para os restantes de cada vez, teríamos o seguinte:
Os 6 jogadores jogam cada um 5 vezes perfazendo um total de 15 partidas, conforme nos mostra a tabela.
Se os jogadores fossem desistindo de participar do campeonato e fossemos fazendo uma tabela de dupla entrada para os restantes de cada vez, teríamos o seguinte:
| 2 pessoas jogam 1 partida |
| 3 pessoas jogam 1+2 = 3 partidas |
| 4 pessoas jogam 1+2+3 = 6 partidas |
| 5 pessoas jogam 1+2+3+4 = 10 partidas |
| 6 pessoas jogam 1+2+3+4+5 = 15 partidas |
| ...................................... |
Facilmente verificamos que se aumentarmos o número de participantes seria imediato calcularmos o número de partidas, ou seja, bastaria somarmos os numeros consecutivos da unidade até o número de participantes (n) menos a unidade (n-1).
Exemplo; Se fossem 7 jogadores teíamos: 1+2+3+4+5+6 = 21 paridas
Vamos agora pensar num outro tipo de jogo em que participem 3 jogadores de cada vez (sinuca, por exemplo).Neste caso, não conseguiriamos armar uma tabela de "tríplice entrada", mas olhando a disposição que se forma na tabela de dupla entrada, podemos armar grupos de 3 jogadores utilizando a mesma disposição. Assim teríamos os grupos:
Exemplo; Se fossem 7 jogadores teíamos: 1+2+3+4+5+6 = 21 paridas
Vamos agora pensar num outro tipo de jogo em que participem 3 jogadores de cada vez (sinuca, por exemplo).Neste caso, não conseguiriamos armar uma tabela de "tríplice entrada", mas olhando a disposição que se forma na tabela de dupla entrada, podemos armar grupos de 3 jogadores utilizando a mesma disposição. Assim teríamos os grupos:
| ABC,ABD,ABE,ABF,ACD,ACE,ACF,ADE,ADF,AEF |
| BCD,BCE,BCF,BDE,BDF,BEF |
| CDE,CDF,CEF |
| DEF |
Dos 20 grupos formados, observamos que:
a) cada grupo disputa 10 partidas
b) cada dupla joga 4 vezes
Suponhamos que um dos jogadores desistisse (F, por exemplo). Então os novos grupos seriam:
Analisando os novos grupos, vemos que:
a) cada jogador disputa 6 partidas
b) cada dupla joga 3 vezes junta
Se fossemos eliminando jogador por jogador teríamos a seguinte situação:
Desta vez não é tão facil descobrirmos o algorítmo de formação para o cálculo do número de partidas como fizemos para o campeonato de xadrez (2 pessoas). Vamos, então, manter em suspenso e mais adiante prosseguiremos este caso.
Repare que até agora formamos grupos (partidas de jogo) em que a ordem de escolha dos componente não modificava o grupo. Exemplo: Os jogadores do grupo ABC, podem ter sido escolhidos na ordem: ABC ou ACB ou BAC ou CBA ou BCA ou CAB
Em qualquer das ordens de seleção o grupo seria o mesmo.
Vamos pensar agora em um jogo em que a ordem de seleção modifique os grupos.
Seja, por exemplo, um jogo de fichas (tipo bingo) em que tenhamos os algarismos 1,2,e 3 para formar centenas.Neste caso teríamos as centenas;
Se tivessemos os algarismos 1,2,3, e 4 teríamos as centenas:
Continuando teremos a seguinte situação:
Verificamos que na formação das centenas o crescimento da formação dos grupos é muito maior do que nos jogos de xadrez e de sinuca. A explicação é devida a influência da ordem de seleção dos componentes dos grupos. Para as fichas de bingo a ordem é extremamente importante, já que a troca da ordem dos algarismos modifica a centena. Já para a composição dos grupos de pessoas a ordem de seleção não tem a mínima importância.
No caso em que a simples troca da ordem de um elemento afeta o agrupamento, diz-se que há um ARRANJO, no caso em que esta troca não afeta o agrupamento, diz-se que há uma COMBINA ÇÃO.
A análise combinatória estuda ainda um outro tipo de agrupamento, chamado de PERMUTAÇÃO. Na permutação os agrupamentos são feitos exclusivamente pela troca de ordem dos elementos do grupo.
Exemplo:
A centena 321 possui 6 permutações, ou seja: 321,312,231,213,123,132
Repare que na permutação todos os elementos são usados no agrupamento, enquanto que nos arranjos e combinações são sempre formados grupos com menos elementos do total a ser grupado.
Agora, que já sabemos do que se trata, ao falarmos de ARRANJOS, COMBINAÇÕES e PERMUTAÇÕES, vamos voltar onde paramos anteriormente e tentar calcular o número possível de arranjos, combinações e permutações de um dado conjunto de elementos.
PERMUTAÇÕES
Chamamos de permutações de n elementos todos os grupamentos possíveis formados com todos esses elementos, diferindo apenas na ordem em que são agrupados.
Assim, temos:
a) Conjunto de 1 elemento (A)
Neste caso, com 1 elemento temos apenas uma permutação, no caso A
b) Conjunto de 2 elementos (A,B)
Fixando um deles podemos colocar o outro à esquerda ou à direita dele. Temos, então, 2 permutações, no caso AB e BA
c) Conjunto de 3 elementos (A,B,C)
Fixando os grupos anteriores podemos colocar o terceiro elemento à esquerda, no meio, e à direita desses grupos. Temos, então, 6 permutações, no caso CAB,ACB,ABC,CBA,BCA e BAC
Se tomarmos um 4º elemento podemos colocá-lo à esquerda, à direita ou entre cada um dos grupos anteriores, perfazendo um total de 24 permutações
Resumindo, temos:
Como se pode ver, o número de permutações possíveis com n elementos é o produto dos números consecutivos desde a unidade até n.
Exemplo: Com 8 elementos, temos:
P8 = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 = 40320
Além da representação Pn, pode-se usar a representação de fatoria(!). Assim, Pn = n!
PERMUTAÇÕES CIRCULARES
Um tipo especial de permutação de elementos é aquele que se faz em volta de uma mesa, por exemplo. Esta permutação é chamada de circular.
Vamos supor 4 pessoas em linha. O número de permutações será 4! = 1 x 2 x 3 x 4 = 24
Coloquemos, agora, essas 4 pessoas em torno de uma mesa redonda. Verificamos que, por ser circular, não podemos mais afirmar quem é o primeiro da mesa. A noção de ordm mudou.
Você começa a contar as pessoas por onde desejar, Seja pois a disposição abaixo:
Repare que muda-se as posições e os elementos mentêem-se, entre si, na mesma ordem. Outra observação importante é que a contagem pode ser feita no sentido horário ou anti-horário.
Se compararmos este tipo de permutação com a permutação linear verificaremos que difere apenas no elemento inicial da contagem que se confunde com o início e o final da mesma. Por isso, a fórmula para calcularmos o número de permutações circulares é : PCn = (n-1)!
Se levarmos em conta os dois sentidos (horário e anti-horário) devemos dividir por dois esta fórmula, ou seja, PCn = (n-1)! / 2
ARRANJOS
Como já foi visto no exemplo das fichas de bingo, nos arranjos os grupamentos são feitos com um número menor de elementos do conjunto dado e a troca da ordem desses elementos provoca novo arranjo,
Exemplo:
Sejam os algarismos 3,4,5,7. Quantas dezenas podemos formar ?
Com certeza, teremos: 34,35,37,45,47,57,43,53,73,54,74 e 75
Generalizando, para formarmos os arranjos procedemos da seguinte maneira:
Se prosseguirmos, teremos para arranjos de n elementos p a p a relação:
An,p = n(n-1)(n-2)(n-3) ....... [n - (p-1)],
ou melhor
An,p = n(n-1)(n-2)(n-3) ....... (n-p+1)
Desta forma, se quizermos calcular A8,3, devemos fazer:
A8,3 = 8 x 7 x 6 = 336 (onde 6 refere-se a 8-3+1)
OBS:
Se não quizermos fazer a conta n-p+1 para sabermos até onde vai o produto, basta fazer p termos decrescentes de n, inclusive
No caso A8,3 são 3 termos (p=3) decrescentes de 8 (n=8). Então A8,3 = 8 x 7 x 6 = 336
COMBINAÇÕES
Como já vimos nos exemplos do campeonato de xadrez e de sinuca, as combinações são feitas com um número menor de elementos do conjunto dado e a troca da ordem desss elementos não provoca outra combinação.
Seja o mesmo exemplo que foi dado para os arranjos. Combinemos os algarismos 3,4,5,7 em dezenas que não se inverta os algarismos. Poderíamos, então, ter os grupos:34,35,37,45,47,43
Repare que se invertessemos essas 6 combinações teríamos os 12 arranjos anteriormente mostrados.
A diferença, portanto, está nas inversões possíveis de cada combinação para obtermos os arranjos. Em outras palavras:
An,p = Cn.p x Pp
Então, podemos afirmar que: Cn,p = An,p / Pp
Assim, se quizermos calcular as combinações de 6 elementos 2 a 2 devemos fazer:
C6,2 = A6,2 / P2 = 6 x 5 / 2 = 15
REPETIÇÃO DE ELEMENTOS
Normalmente os elementos do conjunto a ser grupado são diferentes entre si. Entretanto, muitas vezes temos que fazer as permutações, arranjos e combinações com elementos repetidos no conjunto dado.
Neste caso, devemos ter cuidado de levar em conta para cada tipo de agrupamento a influência da repetição dos elementos, que pode provocar um aumento ou diminuição na contagem dos grupos possíveis de serem formados.
Vamos estudar, caso a caso, o que acontece com a repetição de elementos em cada tipo de agrupamento.
PERMUTAÇÕES COM REPETIÇÃO
Suponhamos que temos os algarismos 2,2,3,3 . Quantos milhares podemos formar ?
Temos: 2233,2323,3223,3232,3322,2332
Observe que se os 4 algarismos fossem diferentes entre si teríamos 4! = 1 x 2 x 3 x 4 = 24 permutações. Com a repetição dos algarismos 2 e 3, as permutações passaram a ser 6 apenas.
Esta queda se refere aos grupos em que a inversão de ordem nada afetará para algarismos idênticos.
Exemplo: 2233, em nada afetará trocar de posição o 1º algarismo 2 com o 2º algarismo 2, nem o 3º algarismo 3 com o 4º algarismo 3.
Então, genericamente, podemos colocar os algarismos repetidos juntos e manter a formação linear. Teremos algo assim, por exemplo:
onde n = p + r + s
Ou seja,
n elementos sendo p letras "a", r letras "b" e s letras "c".
Se os n elementos fossem diferentes teríamos n! como o total das permutações. Como p letras formariam p! e são iguais estão multiplicando o total real de permutações, pois na realidade formam um conjunto unitário. Então o total de permutações deve descontar esses grupos idênticos, ou seja, deve fazer n! / p!.
Com o raciocínio idêntico para as r letras "b" e as s letras "c", teríamos n! / p!r!s!.
De forma genérica, teríamos:
PRnp,r,s,... = n! / p!r!s!...
ARRANJOS COM REPETIÇÃO
Com n elementos formamos n arranjos de 1 em 1 elemento. Ou seja: a, b, c, ..., n (n elementos unitários)
Se quizermos fazer duplas com repetição de elementos colocamos ao lado de cada elemento cada um dos outros elementos unitários. Ou seja,
Vemos que, com a repetição de todos os elementos teremos um total de n x n arranjos, ou n2 arranjos
Ae quizermos fazer triplas com repetição bastaria usar os elementos anteriores(duplas com repetição) e colocar ao lado de cada grupo formado cada um dos elementos unitários. Ou seja
Observamos que temos que repetir o grupo anterior n vezes, ou seja n2 x n = n3 arranjos.
Se prosseguirmos para grupos de 4,5,6,.... elementos podemos afirmar que teremos: ARn,p = np
Assim, por exemplo, se tivermos 6 algarismos e quizermos jogar no bicho com inversão em milhares, teremos um total de:
AR6,4 = 64 = 1296 milhares.
Observação:
Nos arranjos simples, em que os elementos são diferentes entre si p nunca pode ser maior que .n. Entretanto, quando os arranjos são com repetição, podemos ter p p>n, já que há elementos repetidos.
Exemplo:
Sejam os algarismos 3,3,3,3 e 2,2,2,2. Quantos milhares podemos formar ?
Temos, então: n = 2 (dois algarismos) e p=4 (milhares) logo AR2,4 = 24 = 16
COMBINAÇÕES COM REPETIÇÃO
São grupamentos formados de maneira que cada grupo contenha p elementos repetidos ou não e estes agrupamentos sejam diferentes entre si pelo menos por um elemento e pela repetição. Cada elemento, portanto, pode aparecer até p vezes em cada agrupamento.
Representemos esse tipo de combinação por CRn,p. Como cada grupo contem p elementos, no total das combinações existirão p.CRn,p elementos ao todo.
Cada n elemento entra o mesmo número de vezes no total de agrupamentos, ou seja, cada elemento entra no conjunto p.CRn,p / n vezes.
Se separarmos um elemento qualquer dos agrupamentos o número de vezes que cada elemento entra no conjunto será (p-1)CRn,p-1 / n
Se somarmos esse total (excluído um elemento) com o número de agrupamentos desse mesmo conjunto coltamos a ter o número de vezes que cada elemento aparece no grupamento anterior (antes de excluir determinado elemento). Assim, temos que:
(p-1).CRn,p-1 / n + CRn,p-1 = p.CRn,p / n
Extraindo o denominador ( já que n é diferente de zero), temos
(p-1).CRn,p-1 + n.CRn,p-1 = p.CRn,p
Colocando CRn,p-1 em evidencia, temos:
CRn,p-1 [ n + (p-1) ] = p.CRn,p
Dividindo, membro a membro, por p ( já que p é diferente de zero), temos
CRn,p-1 x (n+p-1) / p = CRn,p
Expandindo os termos das combinações desde p até 1 (p-1,p-2,p-3, ..., 3, 2, 1) e somando membro a membro, temos que:
CRn,p x CRn,p-1 x CRn,p-2 x ... x CRn,2 x CRn,1 = (n+p-1)/p x CRn,p-1 x (n+p-2)/(p-1) x CRn,p-2 x CRn,p-2 x ... x n
Simplificando membro a membro, temos
CRn,p = (n+p-1) / p x (n+p-2) / (p-1) x ... x n
ou mais simples ainda:
CRn,p = [ n(n+1)(n+2)(n+3) ... (n+p-1) ] / p!
Exemplo:
Se quizermos formar grupos de 3 objetos de um conjunto e 5 elementos com repetição, teremos:
CR5,3 = 5.6.7 / 1.2.3 = 35
Observação:
No cálculo da combinação simples, basta conhecermos os arranjos e dividir pela permutação do grupo.Exemplo:
C5,3 = 5.4.3 / 1.2.3 = 10
Repare que para calcular a mesma combinação ,com repetição, basta trocar o numerador para o produto crescente e não decrescente , como nos arranjos. Exemplo:
A5,3 = 5.4.3 ( 3 elementos decrescentes a partir de 5, ou seja, 5,4,3)
Para a combinação com repetição usamos este raciocínio só que crescente, ou seja 5.6.7 (3 elementos crescentes a partir de 5)
FORMULÁRIO
Com o que já foi visto dá para se resolver todos os problemas de análise combinatória. Entretanto, muitas vezes, o uso de fórmulas e propriedades pode facilitar a resolução desses problemas. Sendo assim, a seguir são apresentadas essas fórmulas e propriedades:
a) Permutações:
b) Arranjos:
c) Combinações:
d) Propriedades das combinações
a) cada grupo disputa 10 partidas
b) cada dupla joga 4 vezes
Suponhamos que um dos jogadores desistisse (F, por exemplo). Então os novos grupos seriam:
| ABC,ABD,ABE,ACD,ACE,ADE |
| BCD,BCE,BDE |
| CDE |
Analisando os novos grupos, vemos que:
a) cada jogador disputa 6 partidas
b) cada dupla joga 3 vezes junta
Se fossemos eliminando jogador por jogador teríamos a seguinte situação:
| 3 pessoas jogam 1 partida |
| 4 pessoas jogam 4 partidas |
| 5 pessoas jogam 10 partidas |
| 6 pessoas jogam 20 partidas |
| ...................................... |
Desta vez não é tão facil descobrirmos o algorítmo de formação para o cálculo do número de partidas como fizemos para o campeonato de xadrez (2 pessoas). Vamos, então, manter em suspenso e mais adiante prosseguiremos este caso.
Repare que até agora formamos grupos (partidas de jogo) em que a ordem de escolha dos componente não modificava o grupo. Exemplo: Os jogadores do grupo ABC, podem ter sido escolhidos na ordem: ABC ou ACB ou BAC ou CBA ou BCA ou CAB
Em qualquer das ordens de seleção o grupo seria o mesmo.
Vamos pensar agora em um jogo em que a ordem de seleção modifique os grupos.
Seja, por exemplo, um jogo de fichas (tipo bingo) em que tenhamos os algarismos 1,2,e 3 para formar centenas.Neste caso teríamos as centenas;
| 123,132 |
| 213,231 |
| 312,321 |
Se tivessemos os algarismos 1,2,3, e 4 teríamos as centenas:
| 123,124,132,134,142,143, |
| 213,214,231,241,234,243 |
| 312,314,321,341,324,342 |
| 412,413,421,431,423,432 |
Continuando teremos a seguinte situação:
| com 3 algarismos formamos 6 centenas |
| com 4 algarismos formamos 24 centenas |
| com 5 algarismos formamos 60 centenas |
| com 6 algarismos formamos 120 centenas |
| ..................................... |
Verificamos que na formação das centenas o crescimento da formação dos grupos é muito maior do que nos jogos de xadrez e de sinuca. A explicação é devida a influência da ordem de seleção dos componentes dos grupos. Para as fichas de bingo a ordem é extremamente importante, já que a troca da ordem dos algarismos modifica a centena. Já para a composição dos grupos de pessoas a ordem de seleção não tem a mínima importância.
No caso em que a simples troca da ordem de um elemento afeta o agrupamento, diz-se que há um ARRANJO, no caso em que esta troca não afeta o agrupamento, diz-se que há uma COMBINA ÇÃO.
A análise combinatória estuda ainda um outro tipo de agrupamento, chamado de PERMUTAÇÃO. Na permutação os agrupamentos são feitos exclusivamente pela troca de ordem dos elementos do grupo.
Exemplo:
A centena 321 possui 6 permutações, ou seja: 321,312,231,213,123,132
Repare que na permutação todos os elementos são usados no agrupamento, enquanto que nos arranjos e combinações são sempre formados grupos com menos elementos do total a ser grupado.
Agora, que já sabemos do que se trata, ao falarmos de ARRANJOS, COMBINAÇÕES e PERMUTAÇÕES, vamos voltar onde paramos anteriormente e tentar calcular o número possível de arranjos, combinações e permutações de um dado conjunto de elementos.
PERMUTAÇÕES
Chamamos de permutações de n elementos todos os grupamentos possíveis formados com todos esses elementos, diferindo apenas na ordem em que são agrupados.
Assim, temos:
a) Conjunto de 1 elemento (A)
Neste caso, com 1 elemento temos apenas uma permutação, no caso A
b) Conjunto de 2 elementos (A,B)
Fixando um deles podemos colocar o outro à esquerda ou à direita dele. Temos, então, 2 permutações, no caso AB e BA
c) Conjunto de 3 elementos (A,B,C)
Fixando os grupos anteriores podemos colocar o terceiro elemento à esquerda, no meio, e à direita desses grupos. Temos, então, 6 permutações, no caso CAB,ACB,ABC,CBA,BCA e BAC
Se tomarmos um 4º elemento podemos colocá-lo à esquerda, à direita ou entre cada um dos grupos anteriores, perfazendo um total de 24 permutações
Resumindo, temos:
| para 1 elemento temos 1 permutação |
| para 2 elementos temos 1 x 2 = 2 permutações |
| para 3 elementos temos 1 x 2 x 3 = 6 permutações |
| para 4 elementos temos 1 x 2 x 3 x 4 = 24 permutações |
| ............................................. |
Como se pode ver, o número de permutações possíveis com n elementos é o produto dos números consecutivos desde a unidade até n.
Exemplo: Com 8 elementos, temos:
P8 = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 = 40320
Além da representação Pn, pode-se usar a representação de fatoria(!). Assim, Pn = n!
PERMUTAÇÕES CIRCULARES
Um tipo especial de permutação de elementos é aquele que se faz em volta de uma mesa, por exemplo. Esta permutação é chamada de circular.
Vamos supor 4 pessoas em linha. O número de permutações será 4! = 1 x 2 x 3 x 4 = 24
Coloquemos, agora, essas 4 pessoas em torno de uma mesa redonda. Verificamos que, por ser circular, não podemos mais afirmar quem é o primeiro da mesa. A noção de ordm mudou.
Você começa a contar as pessoas por onde desejar, Seja pois a disposição abaixo:
Repare que muda-se as posições e os elementos mentêem-se, entre si, na mesma ordem. Outra observação importante é que a contagem pode ser feita no sentido horário ou anti-horário.
Se compararmos este tipo de permutação com a permutação linear verificaremos que difere apenas no elemento inicial da contagem que se confunde com o início e o final da mesma. Por isso, a fórmula para calcularmos o número de permutações circulares é : PCn = (n-1)!
Se levarmos em conta os dois sentidos (horário e anti-horário) devemos dividir por dois esta fórmula, ou seja, PCn = (n-1)! / 2
ARRANJOS
Como já foi visto no exemplo das fichas de bingo, nos arranjos os grupamentos são feitos com um número menor de elementos do conjunto dado e a troca da ordem desses elementos provoca novo arranjo,
Exemplo:
Sejam os algarismos 3,4,5,7. Quantas dezenas podemos formar ?
Com certeza, teremos: 34,35,37,45,47,57,43,53,73,54,74 e 75
Generalizando, para formarmos os arranjos procedemos da seguinte maneira:
| para arranjos unitários temos n arranjos |
| para arranjos binários temos n(n-1) arranjos |
| para arranjos ternários temos n(n-1)(n-2) arranjos |
| para arranjos quaternários temos n(n-1)(n-2)(n-3) arranjos |
| ............................................. |
Se prosseguirmos, teremos para arranjos de n elementos p a p a relação:
An,p = n(n-1)(n-2)(n-3) ....... [n - (p-1)],
ou melhor
An,p = n(n-1)(n-2)(n-3) ....... (n-p+1)
Desta forma, se quizermos calcular A8,3, devemos fazer:
A8,3 = 8 x 7 x 6 = 336 (onde 6 refere-se a 8-3+1)
OBS:
Se não quizermos fazer a conta n-p+1 para sabermos até onde vai o produto, basta fazer p termos decrescentes de n, inclusive
No caso A8,3 são 3 termos (p=3) decrescentes de 8 (n=8). Então A8,3 = 8 x 7 x 6 = 336
COMBINAÇÕES
Como já vimos nos exemplos do campeonato de xadrez e de sinuca, as combinações são feitas com um número menor de elementos do conjunto dado e a troca da ordem desss elementos não provoca outra combinação.
Seja o mesmo exemplo que foi dado para os arranjos. Combinemos os algarismos 3,4,5,7 em dezenas que não se inverta os algarismos. Poderíamos, então, ter os grupos:34,35,37,45,47,43
Repare que se invertessemos essas 6 combinações teríamos os 12 arranjos anteriormente mostrados.
A diferença, portanto, está nas inversões possíveis de cada combinação para obtermos os arranjos. Em outras palavras:
An,p = Cn.p x Pp
Então, podemos afirmar que: Cn,p = An,p / Pp
Assim, se quizermos calcular as combinações de 6 elementos 2 a 2 devemos fazer:
C6,2 = A6,2 / P2 = 6 x 5 / 2 = 15
REPETIÇÃO DE ELEMENTOS
Normalmente os elementos do conjunto a ser grupado são diferentes entre si. Entretanto, muitas vezes temos que fazer as permutações, arranjos e combinações com elementos repetidos no conjunto dado.
Neste caso, devemos ter cuidado de levar em conta para cada tipo de agrupamento a influência da repetição dos elementos, que pode provocar um aumento ou diminuição na contagem dos grupos possíveis de serem formados.
Vamos estudar, caso a caso, o que acontece com a repetição de elementos em cada tipo de agrupamento.
PERMUTAÇÕES COM REPETIÇÃO
Suponhamos que temos os algarismos 2,2,3,3 . Quantos milhares podemos formar ?
Temos: 2233,2323,3223,3232,3322,2332
Observe que se os 4 algarismos fossem diferentes entre si teríamos 4! = 1 x 2 x 3 x 4 = 24 permutações. Com a repetição dos algarismos 2 e 3, as permutações passaram a ser 6 apenas.
Esta queda se refere aos grupos em que a inversão de ordem nada afetará para algarismos idênticos.
Exemplo: 2233, em nada afetará trocar de posição o 1º algarismo 2 com o 2º algarismo 2, nem o 3º algarismo 3 com o 4º algarismo 3.
Então, genericamente, podemos colocar os algarismos repetidos juntos e manter a formação linear. Teremos algo assim, por exemplo:
| aaa...a bbb...b ccc...c |
| p r s |
onde n = p + r + s
Ou seja,
n elementos sendo p letras "a", r letras "b" e s letras "c".
Se os n elementos fossem diferentes teríamos n! como o total das permutações. Como p letras formariam p! e são iguais estão multiplicando o total real de permutações, pois na realidade formam um conjunto unitário. Então o total de permutações deve descontar esses grupos idênticos, ou seja, deve fazer n! / p!.
Com o raciocínio idêntico para as r letras "b" e as s letras "c", teríamos n! / p!r!s!.
De forma genérica, teríamos:
PRnp,r,s,... = n! / p!r!s!...
ARRANJOS COM REPETIÇÃO
Com n elementos formamos n arranjos de 1 em 1 elemento. Ou seja: a, b, c, ..., n (n elementos unitários)
Se quizermos fazer duplas com repetição de elementos colocamos ao lado de cada elemento cada um dos outros elementos unitários. Ou seja,
| aa ba ca ... na (repetindo a) |
| ab bb cb ... nb (repetindo b) |
| ac bc cc ... nc (repetindo c) |
| ....................................................... |
| an bn cn ... nn (repetindo n) |
Vemos que, com a repetição de todos os elementos teremos um total de n x n arranjos, ou n2 arranjos
Ae quizermos fazer triplas com repetição bastaria usar os elementos anteriores(duplas com repetição) e colocar ao lado de cada grupo formado cada um dos elementos unitários. Ou seja
| aaa baa caa ... naa |
| aab baa cab ... nab |
| aac bac cac ... nac |
| ....................................................... |
| aan ban can ... nan |
| aba bba cba ... nba |
| ....................................................... |
Observamos que temos que repetir o grupo anterior n vezes, ou seja n2 x n = n3 arranjos.
Se prosseguirmos para grupos de 4,5,6,.... elementos podemos afirmar que teremos: ARn,p = np
Assim, por exemplo, se tivermos 6 algarismos e quizermos jogar no bicho com inversão em milhares, teremos um total de:
AR6,4 = 64 = 1296 milhares.
Observação:
Nos arranjos simples, em que os elementos são diferentes entre si p nunca pode ser maior que .n. Entretanto, quando os arranjos são com repetição, podemos ter p p>n, já que há elementos repetidos.
Exemplo:
Sejam os algarismos 3,3,3,3 e 2,2,2,2. Quantos milhares podemos formar ?
Temos, então: n = 2 (dois algarismos) e p=4 (milhares) logo AR2,4 = 24 = 16
COMBINAÇÕES COM REPETIÇÃO
São grupamentos formados de maneira que cada grupo contenha p elementos repetidos ou não e estes agrupamentos sejam diferentes entre si pelo menos por um elemento e pela repetição. Cada elemento, portanto, pode aparecer até p vezes em cada agrupamento.
Representemos esse tipo de combinação por CRn,p. Como cada grupo contem p elementos, no total das combinações existirão p.CRn,p elementos ao todo.
Cada n elemento entra o mesmo número de vezes no total de agrupamentos, ou seja, cada elemento entra no conjunto p.CRn,p / n vezes.
Se separarmos um elemento qualquer dos agrupamentos o número de vezes que cada elemento entra no conjunto será (p-1)CRn,p-1 / n
Se somarmos esse total (excluído um elemento) com o número de agrupamentos desse mesmo conjunto coltamos a ter o número de vezes que cada elemento aparece no grupamento anterior (antes de excluir determinado elemento). Assim, temos que:
(p-1).CRn,p-1 / n + CRn,p-1 = p.CRn,p / n
Extraindo o denominador ( já que n é diferente de zero), temos
(p-1).CRn,p-1 + n.CRn,p-1 = p.CRn,p
Colocando CRn,p-1 em evidencia, temos:
CRn,p-1 [ n + (p-1) ] = p.CRn,p
Dividindo, membro a membro, por p ( já que p é diferente de zero), temos
CRn,p-1 x (n+p-1) / p = CRn,p
Expandindo os termos das combinações desde p até 1 (p-1,p-2,p-3, ..., 3, 2, 1) e somando membro a membro, temos que:
CRn,p x CRn,p-1 x CRn,p-2 x ... x CRn,2 x CRn,1 = (n+p-1)/p x CRn,p-1 x (n+p-2)/(p-1) x CRn,p-2 x CRn,p-2 x ... x n
Simplificando membro a membro, temos
CRn,p = (n+p-1) / p x (n+p-2) / (p-1) x ... x n
ou mais simples ainda:
CRn,p = [ n(n+1)(n+2)(n+3) ... (n+p-1) ] / p!
Exemplo:
Se quizermos formar grupos de 3 objetos de um conjunto e 5 elementos com repetição, teremos:
CR5,3 = 5.6.7 / 1.2.3 = 35
Observação:
No cálculo da combinação simples, basta conhecermos os arranjos e dividir pela permutação do grupo.Exemplo:
C5,3 = 5.4.3 / 1.2.3 = 10
Repare que para calcular a mesma combinação ,com repetição, basta trocar o numerador para o produto crescente e não decrescente , como nos arranjos. Exemplo:
A5,3 = 5.4.3 ( 3 elementos decrescentes a partir de 5, ou seja, 5,4,3)
Para a combinação com repetição usamos este raciocínio só que crescente, ou seja 5.6.7 (3 elementos crescentes a partir de 5)
FORMULÁRIO
Com o que já foi visto dá para se resolver todos os problemas de análise combinatória. Entretanto, muitas vezes, o uso de fórmulas e propriedades pode facilitar a resolução desses problemas. Sendo assim, a seguir são apresentadas essas fórmulas e propriedades:
a) Permutações:
| Pn = n! | PCn = (n-1)! | PRn = n! /( r! s! t! ...) |
b) Arranjos:
| An,p = n! / (n-p)! | ARn,p = np |
c) Combinações:
| Cn,p = n! / [p! (n-p)!] | CRn,p = [n(n+1)(n+2)...(n+p-1)] / p! |
d) Propriedades das combinações
|
Cn,p = Cn,n-p Termos equidistantes |
Cn,p = Cn-1,p + Cn-1,p-1 Relação de Stifel |