(Parte 1 de 6)

Fones: (84) 215-3820 / 215.3819 – FAX: (84) – 211. 9219

ANÁLISE COMBINATÓRIA Prof. Benedito Tadeu V. Freire

Novembro de 2001

Primeiro, àqueles que enfrentam bem as circunstâncias com que se deparam no dia-a-dia

A quem posso chamar de educador

Depois, àqueles que são honrados em suas relações com todos os homens, agüentando com

razoável com seus companheiros quanto é humanamente possível

facilidade e bom humor aquilo que é ofensivo para os outros, então sendo tão agradável e

Àqueles que tem seus prazeres sob controle e não acabam derrubados por suas infelicidades.

Àqueles a quem o sucesso não estraga, que não fogem do seu próprio eu, mas sim, se mantêm firme, como homens de sabedoria e sobriedade

Sócrates (Publicado pela “Folha de São Paulo”, em 15/10/2001, Dia do Professor)

1 O Princípio Aditivo Pág. 3 2 O Princípio Multiplicativo Pág. 3 3. Permutações Pág. 13

4. Combinações Pág. 15 5 Bibliografia Pág. 29

Enunciamos abaixo o que chamamos de Princípio Aditivo:

1. O PRINCÍPIO ADITIVO

Se A e B são dois conjuntos disjuntos, com m e n elementos, respectivamente, então A È B possui m + n elementos

Para ilustrar o Princípio Aditivo, apresentamos dois problemas abaixo.

PROBLEMA 1 Numa classe existem 18 rapazes e 12 garotas. De quantas maneiras podemos selecionar 1 estudante?

Existem 18 + 12 = 30 estudantes. Logo, podemos selecionar 1 estudante de 30 maneiras.

PROBLEMA 2

Numa confeitaria há 5 sabores de picolés e 3 sabores de salgados. Suponha que Maria só tenha permissão para tomar um picolé ou comer um salgado. Quantos são os possíveis pedidos que Maria pode fazer? SOLUÇÃO

Ou Maria escolhe um sabor de picolé dentre os 5 ou 1 tipo de salgado dentre os 3. Portanto, Maria pode fazer 8 pedidos diferentes.

2. O PRINCÍPIO MULTIPLICATIVO Para motivar o Princípio Multiplicativo consideremos o problema abaixo.

PROBLEMA 3 Uma pessoa pode viajar no trecho Natal/Recife/Natal de ônibus, automóvel, avião, navio ou trem. Se o meio de transporte da ida não é o mesmo da volta, de quantas maneiras essa pessoa pode realizar a viagem?

Se a pessoa for de ônibus, ela pode voltar de avião, navio ou trem, o que lhe fornece 3 maneiras distintas de fazer o percurso de ida e volta. Notando ônibus por O, avião por A, navio por N e trem por T, podemos indicar as 3 maneiras distintas de fazer o percurso por:

De maneira análoga, se a pessoa for de avião, há novamente 3 modos distintos de fazer o percurso de ida e volta:

(A, O), (A, N), (A, T) Se a pessoa for de navio, há, também, 3 modos distintos de fazer o percurso de ida e volta:

(N, O), (N, A), (N, T) Analogamente, se fizer o percurso de ida usando o trem:

(T, O), (T, A), (T, N) Essas maneiras podem ser dispostas no seguinte quadro

VOLTA
IDA

Observe que as possibilidades (O, O), (A, A), (N, N) e (T, T) não são possíveis, já que o meio de transporte de ida não pode ser o mesmo meio de transporte de volta.

O quadro acima mostra-nos, basta contar todas as possibilidades, que existem 4 x 3 = 12 maneiras distintas de viajar no trecho Natal/Recife/Natal, usando meios de transportes distintos para a ida e a volta.

Podemos interpretar o problema da seguinte maneira: para a escolha do transporte de ida temos 4 opções distintas. Uma vez escolhido o transporte de ida, a escolha do transporte de volta pode ser feita de 3 maneiras distintas. Logo, o total de possibilidades é 4 x 3 = 12.

O problema acima motiva um princípio básico da Análise Combinatória: o Princípio Multiplicativo, que enunciamos a seguir.

Se uma decisão d1 pode ser tomada de m maneiras e se, uma vez tomada a decisão d1, a decisão d2 puder ser tomada de n maneiras então o número de maneiras de se tomarem as decisões d1 e d2 sucessivamente é m.n

Como no problema 1, utilizando uma tabela podemos verificar o Princípio Multiplicativo. Designando por:

a1, a2, ..., am as distintas maneiras de tomar a decisão d1
b1, b2, ..., bn as distintas maneiras de tomar a decisão d2
Decisão d2 b1 b2 b3 bn
Decisão d1
a1(a1, b1) (a1, b2) (a1, b3) ................... (a1, bn)
a2 (a2, b1) (a2, b2) (a2, b3)(a2, bn)
a3 (a3, b1) (a3, b2) (a3, b3)(a3, bn)
am (am, b1) (am, b2) (am, b3)(am, bn)

O quadro acima nos mostra que existem m.n pares ordenados e que em cada par ordenado (ai, bj):

ai representa uma das m possíveis maneiras de tomar a decisão d1 bj representa uma das n possíveis maneiras de tomar a decisão d2

Portanto, existem m.n maneiras de se tomar as decisões d1 e d2

PROBLEMA 4

(a) De quantas maneiras podemos escolher um quadrado preto e um quadrado branco num tabuleiro de xadrez (i. e. um tabuleiro 8 x 8)? (b) De quantas maneiras podemos escolher um quadrado preto e um quadrado branco num tabuleiro de xadrez se os dois quadrados não podem pertencer à mesma linha ou coluna?

(a) O tabuleiro possui 32 quadrados brancos e 32 quadrados pretos. Para se escolher um quadrado preto existem 32 possibilidades e para a escolha de um quadrado branco temos, também, 32 possibilidades. Logo, temos 32 x 32 = 1024 maneiras distintas de se escolher um quadrado preto e um quadrado branco. (b) Para se escolher um quadrado preto temos 32 possibilidades e para escolher um quadrado branco, diminuindo as possibilidades dos brancos na mesma linha e mesma coluna que o quadrado preto, temos 24 opções. Assim, temos 32 x 24 = 768 maneiras distintas de escolher um quadrado preto e um quadrado branco, não estando ambos na mesma linha ou coluna.

PROBLEMA 5 Existem quantos números naturais com quatro algarismos ímpares distintos?

Os algarismos ímpares são: 1, 3, 5, 7, 9. Um número com 4 algarismos é da forma: abcd.

A escolha de um algarismo para ocupar a posição a pode ser feita de 5 maneiras. Uma vez escolhido o algarismo para a posição a, restam 4 possibilidades para a escolha do algarismo da posição b. Para a posição c, restam 3 possibilidades. Para a posição d restam 2. Pelo Princípio Multiplicativo, a quantidade de números de 4 algarismos ímpares distintos é:

5 x 4 x 3 x 2 = 120.

PROBLEMA 6 Uma bandeira é formada por quatro listras, que devem ser coloridas usando as cores amarelo, branco e cinza, não devendo listras adjacentes ter a mesma cor. De quantos modos pode ser colorida a bandeira?

A primeira listra pode ser colorida de 3 modos; a segunda de 2 modos (não podendo usar a cor empregada na primeira listra); a terceira de 2 modos (não podendo usar a cor empregada na segunda listra) e, finalmente, para colorir a quarta listra, podemos usar 2 cores (não podendo usar a cor empregada na terceira listra). Assim, temos 3 x 2 x 2 x 2 = 24 modos distintos de colorir a bandeira satisfazendo as exigências do enunciado.

PROBLEMA 7 Num tabuleiro 2 x 2, cada quadrado unitário pode ser pintado ou de branco ou de preto. De quantos modos distintos podemos pintar o tabuleiro?

Um tabuleiro 2 x 2 tem 4 quadrados unitários. Cada um desses quadrados unitários pode ser pintado de dois modos distintos: ou de branco ou de preto. Pelo Princípio Multiplicativo, podemos pintar o tabuleiro de 2 x 2 x 2 x 2 = 16 maneiras distintas.

PROBLEMA 8

Um alfabeto consiste de três letras: A, B, C. Nesta língua, uma palavra é uma seqüência arbitrária de não mais do que três letras. Quantas palavras existem nesta língua? SOLUÇÃO

Basta contar quantas palavras existem com uma, duas ou três letras e somar esses valores.

Com uma letra existem 3 palavras: A, B e C. Com duas letras existem 3 x 3 = 9 palavras e com três letras existem 3 x 3 x 3 = 27 letras. Portanto, nesta língua existem 3 + 9 + 27 = 39 palavras.

PROBLEMA 9 (a) Quantos divisores naturais possui o número 360? (b) Quantos desses divisores são ímpares?

(c) Quantos são pares? (d) Quantos são quadrados perfeitos?

(Parte 1 de 6)

Comentários