Elementos de Matemática
Análise Combinatória - Atividades didáticas de 2007
Versão compilada no dia 31 de Julho de 2007.
Departamento de Matemática - UEL
Prof. Ulysses Sodré: ulysses(a)uel(pt)br
Matemática Essencial: http://www.mat.uel.br/matessencial/
Resumo: Notas de aulas construı́das com materiais usados em
nossas aulas na UEL. Elas devem ser usadas como roteiro e não
espero que elas venham a substituir qualquer livro sobre o assunto.
Alguns conceitos foram obtidos em livros citados na Bibliografia,
mas os assuntos foram bastante modificados. Sugiro que o leitor
pesquise na Internet para obter materiais gratuitos para os seus
estudos.
Mensagem: ‘Tudo tem a sua ocasião própria, e há tempo para
todo propósito debaixo do céu. Há tempo de nascer, e tempo de
morrer; tempo de plantar, e tempo de arrancar o que se plantou;
tempo de matar, e tempo de curar; tempo de derrubar, e tempo
de edificar; tempo de chorar, e tempo de rir; tempo de prantear,
e tempo de dançar; tempo de espalhar pedras, e tempo de ajuntar
pedras; tempo de abraçar, e tempo de abster-se de abraçar; tempo
de buscar, e tempo de perder; tempo de guardar, e tempo de deitar
fora; tempo de rasgar, e tempo de coser; tempo de estar calado,
e tempo de falar; tempo de amar, e tempo de odiar; tempo de
guerra, e tempo de paz. Que proveito tem o trabalhador naquilo
em que trabalha? Tenho visto o trabalho penoso que Deus deu aos
filhos dos homens para nele se exercitarem. Tudo fez formoso em
seu tempo; também pôs na mente do homem a idéia da eternidade,
se bem que este não possa descobrir a obra que Deus fez desde o
princı́pio até o fim.’
A Bı́blia Sagrada, Eclesiastes 3
CONTEÚDO
ii
Conteúdo
1 Introdução à Análise Combinatória
1
2 Arranjos
1
2.1
Arranjo simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.2
Arranjo com repetição . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.3
Arranjo condicional
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Permutações
3
3.1
Permutação simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3.2
Permutação com repetição . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3.3
Anagrama . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
3.4
Permutação circular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
4 Combinações
6
4.1
Combinação simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
4.2
Combinação com repetição . . . . . . . . . . . . . . . . . . . . . . . . . .
7
5 Regras para Análise Combinatória
8
5.1
Regra da soma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
5.2
Regra do Produto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
5.3
Número de Arranjos simples . . . . . . . . . . . . . . . . . . . . . . . . . .
9
5.4
Número de Permutações simples . . . . . . . . . . . . . . . . . . . . . . . .
11
5.5
Número de Combinações simples . . . . . . . . . . . . . . . . . . . . . . .
12
5.6
Número de arranjos com repetição . . . . . . . . . . . . . . . . . . . . . .
13
5.7
Número de permutações com repetição . . . . . . . . . . . . . . . . . . . .
14
5.8
Número de combinações com repetição . . . . . . . . . . . . . . . . . . . .
14
5.9
Propriedades das combinações . . . . . . . . . . . . . . . . . . . . . . . . .
15
5.10 Números Binomiais
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
15
Seção 1 Introdução à Análise Combinatória
1
1
Introdução à Análise Combinatória
Análise Combinatória é um conjunto de procedimentos que permite construir
grupos diferentes formados por um número finito de elementos de um conjunto
sob certas circunstâncias.
Na maioria das vezes, tomaremos conjuntos com m elementos e os grupos
formados com elementos deste conjunto terão p elementos, isto é, p será a
taxa do agrupamento, com p ≤ m.
Arranjos, Permutações e Combinações, são os três tipos principais de agrupamentos, sendo que eles podem ser simples, com repetição ou circulares.
Apresentaremos alguns detalhes de tais agrupamentos.
Observação 1. É comum encontrarmos na literatura termos como: arranjar,
combinar ou permutar, mas todo o cuidado é pouco com os mesmos, que às
vezes são utilizados em questões em uma forma dúbia!
2
Arranjos
Definição 1 (Arranjo). É um grupo formado com p elementos escolhidos de
uma coleção com m elementos, sendo p < m de forma que os p elementos
sejam distintos entre si pela ordem ou pela espécie. Os arranjos podem ser
simples ou com repetição.
2.1
Arranjo simples
Definição 2 (Arranjo simples). É um arranjo que não permite a repetição
de qualquer elemento em cada grupo de p elementos. O número de arranjos
simples é dado pela fórmula:
A(m, p) =
m!
(m − p)!
Exemplo 1. Para o conjunto {A, B, C, D}, o número de arranjos simples dos
m = 4 elementos tomados com a taxa p = 2 é formado por 12 grupos, pois
A(4, 2) =
4! 24
=
= 12
2!
2
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
2.2
Arranjo com repetição
2
Os grupos não possuem a repetição de qualquer elemento mas os elementos
podem aparecer na ordem trocada. Todos os grupos estão no conjunto:
{AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC}
2.2
Arranjo com repetição
Definição 3 (Arranjo com repetição). É um arranjo em que todos os m
elementos podem aparecer repetidos em cada grupo de p elementos. O número
de arranjos com repetição é dado pela fórmula:
Ar (m, p) = mp
Exemplo 2. Para o conjunto {A, B, C, D}, o número de arranjos com repetição
dos m = 4 elementos com a taxa p = 2 é formado por 16 grupos, pois
Ar (4, 2) = 42 = 16
Aparecem repetições em cada grupo. Os grupos estão no conjunto:
{AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD}
2.3
Arranjo condicional
Definição 4 (Arranjo condicional). É um arranjo em que todos os elementos
aparecem em cada grupo de p elementos, mas existe uma condição que deve
ser satisfeita acerca de alguns elementos. O número de arranjos condicionais
é dado pela fórmula:
Ac = A(m1 , p1 ) × A(m − m1 , p − p1 )
Exemplo 3. Vamos construir todos os arranjos com 4 elementos do conjunto
{A, B, C, D, E, F, G}, começando com 2 letras escolhidas no subconjunto
{A, B, C}.
Aqui temos um total de m = 7 letras, a taxa é p = 4, o subconjunto escolhido
tem m1 = 3 elementos e a taxa de formação para este subconjunto é p1 = 2.
Com as letras A, B e C, tomadas 2 a 2, temos 6 grupos que estão no conjunto:
PABC = {AB, BA, AC, CA, BC, CB}
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
Seção 3 Permutações
3
Com as letras D, E, F e G tomadas 2 a 2, obtemos 12 grupos que estão no
conjunto:
PDEF G = {DE, DF, DG, ED, EF, EG, F D, F E, F G, GD, GE, GF }
Usando a regra do produto, temos 72 possibilidades obtidas pela junção de
um elemento do conjunto PABC com um elemento do conjunto PDEF G . Um
tı́pico arranjo para esta situação é CAF G.
Cálculo para o exemplo:
Ac = A(3, 2) × A(7 − 3, 4 − 2) = A(3, 2) × A(4, 2) = 6 × 12 = 72
3
Permutações
Definição 5 (Permutação). Permutação é um agrupamento formado com m
elementos, de modo que todos os m elementos sejam distintos entre si pela
ordem. As permutações podem ser simples, com repetição ou circulares.
3.1
Permutação simples
Definição 6 (Permutação simples). Permutações são agrupamentos com todos os m elementos distintos. O número de permutações simples é:
P (m) = m!
Exemplo 4. Para o conjunto {A, B, C}, o número de permutações simples
desses m = 3 elementos é formado por P (3) = 3! = 6 grupos que não podem
ter a repetição de qualquer elemento em cada grupo mas que aparecem na
ordem trocada. Todos os agrupamentos estão no conjunto:
P = {ABC, ACB, BAC, BCA, CAB, CBA}
3.2
Permutação com repetição
Definição 7 (Permutação com repetição). Para os m elementos de um conjunto {x1 , x2 , x3 , ..., xm }, vamos supor que existem m1 elementos iguais a x1 ,
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
3.3
Anagrama
4
m2 elementos iguais a x2 , m3 elementos iguais a x3 , ..., mn elementos iguais
a xn , tal que m = m1 + m2 + m3 + ... + mn .
Para os nossos cálculos vamos usar m = m1 + m2 + m3 e o número de
permutações com repetição é dado pela fórmula:
Pr (m; m1 +m2 +m3 ) = C(m, m1 ) C(m−m1 , m2 ) C(m−m1 −m2 , m3 )
m!
(m−m1 )!
(m−m1 −m2 )!
=
m1 ! (m−m1 )! m2 ! (m−m1 −m2 )!
m3 ! 0!
m!
=
m1 ! m2 ! m3 !
Em geral, se m = m1 + m2 + m3 + ... + mn , o número de permutações com
repetição é dado pela fórmula:
Pr (m; m1 +m2 +m3 +...+mn ) =
3.3
m!
m1 ! m2 ! m3 ! ... mn !
Anagrama
Definição 8 (Anagrama). Um anagrama é uma (outra) palavra construı́da
com as mesmas letras da palavra original trocadas de posição.
Se as letras da palavra original são:
1. distintas, o número de anagramas é dado pelo número de permutações
simples.
2. repetidas, o número de anagramas é dado pelo número de permutações
com repetição.
Exemplo 5. Para obter os anagramas da palavra ARARAT, observamos que a
letra A ocorre m1 = 3 vezes, a letra R ocorre m2 = 2 vezes e a letra T ocorre
m3 = 1 vez. O número de permutações com repetição desses elementos
do conjunto {A, R, T } em agrupamentos de m = 6 elementos é dado por
60 grupos com a repetição de todos os elementos do conjunto aparecendo
também na ordem trocada.
Cálculo: Aqui m1 = 3, m2 = 2, m3 = 1, m = m1 + m2 + m3 = 6, logo
Pr (6; 3 + 2 + 1) =
6!
720
=
= 60
3! 2! 1! 6 × 2 × 1
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
3.4
Permutação circular
5
Todos os 60 anagramas da palavra ARARAT estão listados na tabela:
N
1
1
1
3
3
3
3
3
3
3
3
3
3
3
6
6
6
6
3.4
Inicial
RRT
RTR
TRF
AAA
AAT
ARR
ART
ATA
ATR
RRA
RTA
TAA
TAR
TRA
AAR
ARA
RAA
RAR
Anagramas formados com as três letras iniciais indicadas
RRTAAA
RTRAAA
TRRAAA
AAARRT, AAARTR, AAATRR
AATARR, AATRAR, AATRRA
ARRAAT, ARRATA, ARRTAA
ARTAAR, ARTARA, ARTRAA
ATAARR, ATARAR, ATARRA
ATRAAR, ATRARA, ATRRAA
RRAAAT, RRAATA, RRATAA
RTAAAT, RTAATA, RTATAA
TAAARR, TAARAR, TAARRA
TARAAR, TARARA, TARRAA
TRAAAR, TRAARA, TRARAA
AARART, AARATR, AARRAT, AARRTA, AARTAR, AARTRA
ARAART, ARAATR, ARARAT, ARARTA, ARATAR, ARATRA
RAAART, RAAATR, RAARAT, RAARTA, RAATAR, RAATRA
RARAAT, RARATA, RARTAA, RATAAT, RATATA, RATTAA
Permutação circular
Definição 9 (Permutação circular). Este tipo de permutação ocorre quando
temos grupos com m elementos distintos formando um cı́rculo. O número de
permutações circulares é dado pela fórmula:
Pc (m) = (m − 1)!
Exemplo 6. De quantos modos distintos as pessoas do conjunto {A, B, C, D}
poderão sentar-se junto a uma mesa circular (pode ser retangular) para realizar
o jantar sem haver repetição das posições?
Existem 24 permutações simples possı́veis com estas 4 pessoas, as quais estão
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
Seção 4 Combinações
6
no conjunto:
Pc = {ABCD, ABDC, ACBD, ACDB, ADBC, ADCB,
BACD, BADC, BCAD, BCDA, BDAC, BDCA,
CABD, CADB, CBAD, CBDA, CDAB, CDBA,
DABC, DACB, DBAC, DBCA, DCAB, DCBA}
Acontece que junto a uma mesa circular temos que:
ABCD=BCDA=CDAB=DABC ABDC=BDCA=DCAB=CABD
ACBD=CBDA=BDAC=DACB ACDB=CDBA=DBAC=BACD
ADBC=DBCA=BCAD=CADB ADCB=DCBA=CBAD=BADC
Assim, existem somente
P (4) = (4 − 1)! = 6
grupos distintos, que são:
Pc = {ABCD, ABDC, ACBD, ACDB, ADBC, ADCB}
4
Combinações
Definição 10 (Combinação). Combinação é um arranjo formado por um agrupamentos com p elementos de uma coleção com m elementos, sendo p ≤ m,
de forma que os p elementos sejam distintos entre si apenas pela espécie.
4.1
Combinação simples
Definição 11 (Combinação simples). É uma combinação em que não ocorre
a repetição de qualquer elemento em cada grupo de p elementos. O número
de combinações é dado pela fórmula:
C(m, p) =
m!
(m − p)! p!
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
4.2
Combinação com repetição
7
Exemplo 7. Considerando o conjunto {A, B, C, D}, o número de combinações
simples desses m = 4 elementos tomados com a taxa p = 2 é formado por
4!
24
C(4, 2) =
=
= 6 grupos que não podem ter a repetição de qualquer
2!2!
4
elemento nem podem aparecer na ordem trocada. Todos os agrupamentos
estão no conjunto:
Cs = {AB, AC, AD, BC, BD, CD}
4.2
Combinação com repetição
Definição 12 (Combinação com repetição). É uma combinação em que todos
os elementos podem aparecer repetidos em cada grupo até p vezes. O número
de combinações com repetição é dado pela fórmula:
Cr (m, p) = C(m + p − 1, p)
Exemplo 8. Para o conjunto {A, B, C, D}, o número de combinações com
repetição desses m = 4 elementos tomados com a taxa p = 2 é formado por
Cr (4, 2) = C(4 + 2 − 1, 2) = C(5, 2) =
5!
= 10
2!3!
grupos que possuem todas as repetições possı́veis de elementos em grupos de
2 elementos não podendo aparecer o mesmo grupo com a ordem trocada. Em
geral, todos os agrupamentos com 2 elementos formam um conjunto com 16
elementos:
Cr = {AA, AB, AC, AD, BA, BB, BC, BD,
CA, CB, CC, CD, DA, DB, DC, DD}
mas para obter as combinações com repetição, deveremos excluir deste conjunto os 6 grupos que já apareceram antes, pois
AB=BA, AC=CA, AD=DA, BC=CB, BD=DB, CD=DC
assim as combinações com repetição dos elementos de K tomados 2 a 2, são:
Cr = {AA, AB, AC, AD, BB, BC, BD, CC, CD, DD}
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
Seção 5 Regras para Análise Combinatória
5
8
Regras para Análise Combinatória
Em geral, problemas de Análise Combinatória são muito difı́ceis mas eles podem ser resolvidos através de duas regras básicas: a regra da soma e a regra
do produto.
5.1
Regra da soma
A regra da soma garante que se um elemento pode ser escolhido de m formas
e um outro elemento pode ser escolhido de n formas, então a escolha de um
ou outro elemento ocorrerá de m + n formas, desde que tais escolhas sejam
independentes, isto é, nenhuma das escolhas de um elemento pode coincidir
com uma escolha do outro.
5.2
Regra do Produto
A regra do produto garante que se um elemento H pode ser escolhido de m
formas diferentes e se depois de cada uma dessas escolhas, um outro elemento
M pode ser escolhido de n formas diferentes, a escolha do par (H, M ) nesta
ordem poderá ser realizada de m × n formas.
Exemplo 9. Sejam duas retas paralelas ou concorrentes sem que os pontos
sob análise estejam em ambas, sendo que a primeira reta r contém m pontos
distintos marcados por r1 , r2 , r3 , ..., rm e a segunda reta s contém n outros
pontos distintos marcados por s1 , s2 , s3 , ..., sn .
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.3
Número de Arranjos simples
9
De quantos modos podemos traçar segmentos de retas com uma extremidade
na reta r e a outra extremidade na reta s?
Ligando r1 a todos os pontos de s temos n segmentos, depois ligando r2 a
todos os pontos de s temos n segmentos, e continuamos até o último ponto
rm para obter também n segmentos. Como existem m pontos na reta r e n
pontos na reta s, temos m × n segmentos possı́veis.
5.3
Número de Arranjos simples
De quantas maneiras diferentes podemos escolher p elementos de um conjunto
com m elementos, com p ≤ m?
Cada uma dessas escolhas é um arranjo de m elementos tomados p a p.
Construı́mos uma seqüência com os m elementos do conjunto.
{c1 , c2 , c3 , c4 , c5 , ..., cm−2 , cm−1 , cm }
Cada vez que um elemento é retirado, indicamos esta operação com a mudança
da cor do elemento para a cor vermelha.
Para escolher o primeiro elemento do conjunto com m elementos, temos m
possibilidades. Vamos supor que a escolha tenha caı́do sobre o elemento de
ordem m.
{c1 , c2 , c3 , c4 , c5 , ..., cm−2 , cm−1 , cm }
Para escolher o segundo elemento, devemos observar o que sobrou no conjunto
e constatamos que agora existem apenas m − 1 elementos. Suponhamos que
tenha sido retirado o último elemento dentre os que sobraram no conjunto. O
elemento retirado na segunda fase é aquele de ordem m − 1.
{c1 , c2 , c3 , c4 , c5 , ..., cm−2 , cm−1 , cm }
Após a segunda retirada, sobraram m − 2 possibilidades para a próxima retirada. Do que sobrou, se retirarmos o terceiro elemento como sendo o de
ordem m − 2, teremos algo que pode ser visualizado como:
{c1 , c2 , c3 , c4 , c5 , ..., cm−2 , cm−1 , cm }
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.3
Número de Arranjos simples
10
Continuando o processo de retirada, cada vez temos 1 elemento a menos que
na fase anterior. Para retirar o elemento de ordem p, restam m − p + 1
possibilidades de escolha.
Para obter o número total de arranjos possı́veis de m elementos tomados com
a taxa p, basta multiplicar os números que aparecem na segunda coluna da
tabela:
Retirada Número de possibilidades
1
m
2
m-1
3
m-2
...
...
p
m-p+1
Número de arranjos: m(m − 1)(m − 2)...(m − p + 1)
Denotamos o número de arranjos de m elementos com a taxa p, por A(m, p)
e a expressão para o seu cálculo é dada por:
A(m, p) = m(m − 1)(m − 2)...(m − p + 1)
Exemplo 10. Quais e quantas são as possibilidades de dispor as 5 vogais
A,E,I,O,U em grupos de 2 elementos diferentes?
O conjunto solução é:
{AE, AI, AO, AU, EA, EI, EO, EU, IA, IE,
IO, IU, OA, OE, OI, OU, U A, U E, U I, U O}
A solução numérica é A(5, 2) = 5 × 4 = 20.
Exemplo 11. Consideremos as 5 vogais de nosso alfabeto. Quais e quantas
são as possibilidades de dispor estas 5 vogais em grupos de 2 elementos (não
necessariamente diferentes)?
Sugestão: Construir uma reta com as 5 vogais e outra reta paralela à anterior
com as 5 vogais, usar a regra do produto para concluir que há 5 × 5 = 25
possibilidades.
O conjunto solução é:
{AA, AE, AI, AO, AU, EA, EE, EI, EO, EU, IA, IE, II,
IO, IU, OA, OE, OI, OO, OU, U A, U E, U I, U O, U U }
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.4
Número de Permutações simples
11
Exemplo 12. Quantas placas de carros da forma XYZ-1234 são obtidas no
sistema brasileiro de trânsito com 3 letras iniciais e 4 algarismos no final?
Sugestão: Use as 26 letras do nosso alfabeto tomadas 3 a 3 e 10 algarismos
dispostos 4 a 4 e em seguida utilize a regra do produto.
5.4
Número de Permutações simples
Este é um caso particular de arranjo com p = m. Para obter o número de
permutações com m elementos distintos de um conjunto, basta escolher os
m elementos em uma certa ordem. A tabela de arranjos com as linhas até a
ordem p = m, permitirá obter o número de permutações de m elementos:
Retirada Número de possibilidades
1
m
2
m-1
...
...
p
m-p+1
...
...
m-2
3
m-1
2
m
1
Denotaremos o número de permutações de m elementos, por P (m) e a expressão para o seu cálculo será dada por:
P (m) = m(m − 1)(m − 2)...(m − p + 1)...3 × 2 × 1
Em função da forma como construı́mos o processo, podemos escrever:
A(m, m) = P (m)
Como o uso de permutações é intenso em Matemática e nas ciências, costumase simplificar a permutação de m elementos e escrever simplesmente:
P (m) = m!
Este sı́mbolo de exclamação posto junto ao número m é lido como: fatorial
de m, onde m é um número natural.
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.5
Número de Combinações simples
12
Embora zero não seja um número natural no sentido que tenha tido origem
nas coisas da natureza, procura-se dar sentido para a definição de fatorial de
m de uma forma mais ampla, incluindo m = 0 e para isto podemos escrever:
0! = 1
Em contextos mais avançados, existe a função gama que generaliza o conceito
de fatorial de um número real, excluindo os inteiros negativos e com estas
informações pode-se demonstrar que 0! = 1.
O fatorial de um número inteiro não negativo pode ser definido de uma forma
recursiva através da função P = P (m) ou com o uso do sinal de exclamação:
(m + 1)! = (m + 1) · m!,
0! = 1
Exemplo 13. De quantos modos podemos colocar juntos 3 livros A,B,C diferentes em uma estante? O número de arranjos é P (3) = 6 e o conjunto solução:
P = {ABC, ACB, BAC, BCA, CAB, CBA}
Exemplo 14. Quantos anagramas podemos formar com as letras da palavra
AMOR? O número de arranjos é P (4) = 24 e o conjunto solução é:
P = {AM OR, AM RO, AROM, ARM O, AORM, AOM R, M ARO, M AOR,
M ROA, M RAO, M ORA, M OAR, OAM R, OARM, ORM A, ORAM,
OM AR, OM RA, RAM O, RAOM, RM OA, RM AO, ROAM, ROM A}
5.5
Número de Combinações simples
Seja um conjunto com m elementos distintos. No estudo de arranjos, observamos que podemos escolher p elementos deste conjunto, mas ao realizar tais
escolhas pode ocorrer que duas coleções com p elementos tenham os mesmos elementos em ordens trocadas. Uma situação tı́pica é a escolha de um
casal (H, M ). Quando se fala casal, não tem importância a ordem da posição
(H, M ) ou (M, H), assim não precisamos escolher duas vezes as mesmas pessoas para formar o referido casal. Para evitar a repetição de elementos em
grupos com a mesma quantidade p de elementos, introduzimos o conceito de
combinação.
Uma coleção de p elementos de um conjunto com m elementos é uma combinação de m elementos tomados p a p, se as coleções com p elementos não
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.6
Número de arranjos com repetição
13
possuem os mesmos elementos que já apareceram em outras coleções com o
mesmo número p de elementos.
Aqui, temos um outro caso de arranjo, mas não acontece a repetição do
mesmo grupo de elementos em uma ordem diferente, o que significa que dentre
todos os A(m, p) arranjos com p elementos, existem p! desses arranjos com
os mesmos elementos. Para obter o número de combinações de m elementos
com a taxa p, devemos dividir o número de arranjos A(m, p) por m! para
obter apenas o número de arranjos que contém conjuntos distintos, ou seja:
C(m, p) =
=
=
=
=
A(m, p)
p!
m(m−1)(m−2)...(m−p + 1)
p!
m(m−1)(m−2)...(m−p + 1)
1 · 2 · 3 · 4....(p−1)p
m(m−1)(m−2)...(m−p + 1) (m−p)(m−p−1)...2 × 1
1 · 2 · 3 · 4....(p−1)p
(m−p)(m−p−1)...2 × 1
m!
p!(m − p)!
A expressão simplificada para a combinação de m elementos tomados p a p,
é uma das seguintes:
m!
m
C(m, p) =
=
p! (m − p)!
p
5.6
Número de arranjos com repetição
Tomemos um conjunto com m elementos distintos e consideremos p elementos
escolhidos neste conjunto em uma certa ordem. Cada uma dessas escolhas é
um arranjo com repetição de m elementos tomados p a p. Como existem m
possibilidades para a colocação de cada elemento, o número total de arranjos
com repetição de m elementos escolhidos p a p é dado por mp. Assim,
indicamos este número por:
Ar (m, p) = m × p
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.7
5.7
Número de permutações com repetição
14
Número de permutações com repetição
Problema: Sejam 3 bolas vermelhas, 2 bolas azuis e 5 bolas amarelas. Para
colocar estas bolas em uma ordem determinada, devemos obter o número de
permutações com repetição dessas bolas. Usaremos o seguinte procedimento:
1. Tomemos 10 compartimentos numerados onde serão colocadas as bolas.
2. Coloque as 3 bolas vermelhas em 3 compartimentos, o que dá C(10, 3)
possibilidades.
3. Coloque as 2 bolas azuis nos compartimentos que sobraram, para obter
C(10 − 3, 2) possibilidades e
4. Coloque as 5 bolas amarelas, para obter C(10 − 3 − 2, 5) possibilidades.
O número total de possibilidades pode ser calculado como:
7!
5!
10!
10!
×
×
=
Pr = C(10, 3) C(10 − 3, 2) C(10 − 3 − 2, 5) =
3!7! 2!5! 5!0! 3!2!5!
Tal metodologia pode ser generalizada.
5.8
Número de combinações com repetição
Sejam m elementos distintos e ordenados. Escolha p elementos um após o
outro e ordene estes elementos na mesma ordem que os elementos dados. O
resultado é denominado uma combinação com repetição de m elementos com
a taxa p, denotado por Cr (m, p). Aqui a taxa p poderá ser maior do que o
número m de elementos.
Exemplo 15. Seja o conjunto A = {a, b, c, d, e} e p = 6. As coleções
{a, a, b, d, d, d}, {b, b, b, c, d, e} e {c, c, c, c, c, c} são exemplos de combinações
com repetição de 5 elementos escolhidos 6 a 6.
Podemos representar tais combinações por meio de sı́mbolos # e vazios Ø onde
cada ponto # é repetido (e colocado junto) tantas vezes quantas vezes aparece
uma escolha do mesmo tipo, enquanto o vazio Ø serve para separar os objetos
em função das suas diferenças
{ a, a, b, d, d, d } equivale a
{ b, b, b, c, d, e } equivale a
{ c, c, c, c, c, c } equivale a
# # Ø # Ø Ø # # # Ø
Ø # # # Ø # Ø # Ø #
Ø Ø # # # # # # Ø Ø
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.9
Propriedades das combinações
15
Cada sı́mbolo possui 10 lugares com exatamente 6 # e 4 Ø. Para cada combinação existe uma correspondência biunı́voca com um sı́mbolo e reciprocamente. Podemos construir um sı́mbolo pondo exatamente 6 pontos em 10
lugares. Após isto, os espaços vazios são preenchidos com barras. Isto pode
ser feito de C(10, 6) modos. Assim:
Cr (5, 6) = C(5 + 6 − 1, 6)
Generalizando isto, podemos mostrar que:
Cr (m, p) = C(m + p − 1, p)
5.9
Propriedades das combinações
Seja m um número de elementos e o número p a taxa que define a quantidade
de elementos de cada escolha dentre os m elementos dados.
1. Taxas complementares: C(m, p) = C(m, m − p).
2. Relação de Stifel: C(m, p) = C(m − 1, p) + C(m − 1, p − 1).
5.10
Números Binomiais
Se m e p são números inteiros não negativos, o número de combinações de m
elementos tomados com a taxa p, indicado antes por C(m, p), é denominado
coeficiente binomial ou número binomial, denotado por:
m
m!
=
p
p!(m − p)!
Extensão: Existe uma extensão do conceito de número binomial ao conjunto
dos números reais e podemos calcular o número binomial de qualquer número
real r que seja diferente de um número inteiro negativo, tomado a uma taxa
inteira p, mas neste caso, não podemos mais utilizar a notação de combinação
C(m, p) pois esta somente tem sentido quando m e p são números inteiros
não negativos.
Tomando π = 3, 1415926535, obtemos
π
π(π − 1)
=
= 3, 36400587375
2
2
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.10
Números Binomiais
16
A função citada acima que permite a extensão é a função gama. Tais cálculos
são utilizados em Probabilidade e Estatı́stica.
Existem duas relações muito importantes, que podem ser escritas em função
da notação binomial:
Teorema 1 (Taxas complementares). Se n, k ∈ N com n ≥ k, então
n
n
=
k
n−k
Exemplo:
12
10
=
12
2
= 66.
Teorema 2 (Relação de Stifel). Se n, k ∈ N com n > k, então
n
n
n+1
+
=
k
k+1
k+1
Desenvolvendo o membro da esquerda, obtemos:
n
n
n!
n!
+
=
+
k
k+1
k!(n − k)! (k + 1)!(n − k − 1)!
n!(n − k)
n!(k + 1)
+
=
(k + 1)k!(n − k)! (k + 1)!(n − k)(n − k − 1)!
n!(k + 1)
n!(n − k)
=
+
(k + 1)!(n − k)! (k + 1)!(n − k)!
n!(k + 1 + n − k)
=
(k + 1)![(n + 1) − (k + 1)]!
(n + 1)n!
=
(k + 1)![(n + 1) − (k − 1)]!
(n + 1)!
n+1
=
=
(k + 1)![(n + 1) − (k − 1)]!
k+1
Exemplo:
12
10
=
11
10
+
11
9
= 605.
Teorema 3 (Binomial para n finito). Se h > 0 e n ∈ N , então
n X
n(n − 1) 2 n(n − 1)(n − 2) 3
n
n
(1+h) =
hn = 1+nh+
h +
h +...+hn
k
2!
3!
k=0
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.10
Números Binomiais
17
Teorema 4 (Desigualdade de Bernoulli com 2 termos). Se 1+h > 0 e n ∈ N ,
então:
(1 + h)n ≥ 1 + nh
Demonstração: Se n = 1, então (1 + h)1 ≥ 1 + 1h. Se (1 + h)n ≥ 1 + nh é
verdadeiro, mostraremos que (1 + h)n+1 ≥ 1 + (n + 1)h.
(1 + h)n+1 = (1 + h).(1 + h)n ≥ (1 + h).(1 + nh)
= 1 + h + nh + nh2 ≥ 1 + (n + 1)h
Teorema 5 (Desigualdade de Bernoulli com 3 termos). Se h > 0 e n ∈ N ,
então
n(n − 1) 2
h
(1 + h)n ≥ 1 + nh +
2!
Demonstração: Se n = 1 então (1 + h)1 ≥ 1 + 1h + 0.h2 .
n(n − 1) 2
h é verdadeiro, mostraremos que
2!
(n + 1)n 2
h
(1 + h)n+1 ≥ 1 + (n + 1)h +
2
Se (1 + h)n ≥ 1 + nh +
(1 + h)n+1 = (1 + h).(1 + h)n
≥ (1 + h).(1 + nh +
n(n − 1) 2
h)
2
n(n − 1) 3
n(n − 1) 2
h + h + nh2 +
h
2!
2
n(n − 1) 2 2n 2 n(n − 1) 3
= 1 + (n + 1)h +
h + h +
h
2
2
2!
n(n − 1) 2 2n 2
≥ 1 + (n + 1)h +
h + h
2
2
(n + 1)n 2
= 1 + (n + 1)h +
h
2
= 1 + nh +
Alguns casos particulares do Teorema binomial, são:
(a + b)2
(a + b)3
(a + b)4
(a + b)5
=
=
=
=
a2 + 2ab + b2
a3 + 3a2 b + 3ab2 + b3
a4 + 4a3 b + 6a2 b2 + 4ab3 + b4
a5 + 5a4 b + 10a3 b2 + 10a2 b3 + 5ab4 + b5
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.10
Números Binomiais
18
Teorema 6 (Binomial). Se m é um número natural, então:
m
m
m
m m
(a + b)m = am +
am−1 b +
am−2 b2 +
am−3 b3 + ... +
b
1
2
3
m
A demonstração do teorema será construı́da com o uso do Princı́pio da Indução
Matemática. Iremos considerar a Proposição P (m) de ordem m, dada por:
m
m
m
m m
(a + b)m = am +
am−1 b +
am−2 b2 +
am−3 b3 + ... +
b
1
2
3
m
P (1) é verdadeira pois (a + b)1 = a + b.
Vamos considerar verdadeira a proposição P (k), com k > 1:
k k−1
k k−2 2
k k−3 3
k k
(a + b) = a +
a b+
a b +
a b + ... +
b
1
2
3
k
k
k
Para mostrar que é verdadeira a proposição P (k + 1), devemos concluir que:
(a+b)k+1
k+1
k
k−1
k+1
= ak+1 +
ak b+
ak−1 b2 +
ak−2 b3 +...+
bk+1
1
2
3
k+1
Assim
(a + b)k+1 = (a + b)(a + b)k
k k
= (a + b)[ak + k1 ak−1b + k2 ak−2 b2 + k3 ak−3 b3 + ...
+
k b ]
k
k
k
k
= a[ak + 1 ak−1 b + 2 ak−2 b2 + 3 ak−3 b3 + ... + k bk ]
k k−2 2
k k−3 3
k k
b +
b + ... +
+b[ak + k1 ak−1 b +
3 a
k b ]
2 a
k k−2 3
k
k k
k k−1 2
k+1
= a
+ 1 a b + 2 a b + 3 a b + ... + k abk
k k−3 4
k k+1
+ak b + k1ak−1 b2 + k2 ak−2 b3 +
a
b
+
...
+
3
k−1 2
k bk−2 3
k
k
k
k
k
k+1
k
+ 2 ]a b
= a + [ 1 + 1]a b + [ 2 + 1 ]a b +
[ 2 3k−1
k
k
k
k
k−3 4
+[ 4 + 3 ]a b + ... + [ k−1 + k−2 ]a b
k
k
+[ kk + k−1
]ab + kk bk+1
= ak+1 + [ k1 + k0 ]ak b + [ k2 + k1 ]ak−1 b2
k
k
k
k−2 3
k−3 4
+[ k3 +
b + ... 2 ]a b + [ 4 + 3 ]a
k
k
k
k
+[ k−1 + k−2 ]a2 bk−1 + [ k + k−1 ]abk + kk bk+1
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007
5.10
Números Binomiais
19
A relação de Stifel garante as três primeiras e as três últimas as identidades:
k
1
k
2
k
3
+
+
+
k
0
k
1
k
2
=
=
=
k+1
1
k+1
2
k+1
3
k
k−2 +
k
k−1 +
k
k +
k
k−1
k
k−2
k
k−1
=
=
=
k+1
k−2
k+1
k−1
k+1
k
E assim podemos escrever:
k+1
(a + b)
k+1 k+1
k+1 k
k+1 k−1 2
k+1 k−2 3
=
a
+
a b+
a b +
a b
0
1
2
3
k+1 2 k−1
k+1
k+1
+... +
ab
+
abk +
bk+1
k−1
k
k+1
que garante que a propriedade P (m + 1) é verdadeira.
Análise Combinatória - Ulysses Sodré - Matemática - UEL - 2007