NOES DE CONTAGEM

1. PRNCPIO FUNDAMENTAL DA CONTAGEM

Lema 1: Consideremos os conjuntos A = {a1, a2, ..., am} e B = {b1, b2,...,bn}. Podemos formar m.n pares ordenados (ai, bj)

em que ai A e bj B.

Aplicao Nvel 1: Uma moa possui 5 blusas e 6 saias. De quantas formas ela pode vestir-se com uma blusa e uma

saia?

Soluo: Pelo Lema 1 temos 5 . 6 = 30 formas.

Aplicao Nvel 2: Um mgico se apresenta em pblico vestindo cala e palet de cores diferentes. Qual o nmero

mnimo de peas para que ele possa se apresentar em 24 sesses com conjuntos diferentes?

Soluo: Pelo Lema 1 temos: n(C) x n(P) = 24. Os naturais que satisfazem essa condio so: 1.24, 2.12, 3.8 3 4.6.

Dentre eles, a soma mnima 10. Portanto teremos 4 Calas e 6 Palets ou 4 Palets e 6 Calas.

Aplicao Nivel 3: Quantos divisores positivos tem o nmero 3888 ?

Soluo: 3888 = 24 . 35. Da cada divisor um nmero do tipo 2 . 3 , em que { 0,1,2,3,4} e { 0,1,2,3,4,5}. Portanto, o nmero de divisores o nmero de pares ordenados ( , ), que pelo Lema 1 5.6 = 30.

Princpio fundamental da contagem parte I: Consideremos r conjuntos A = {a1, a2, ..., an1}, B = (b1, b2,...,bn2},..., Z =

{z1, z2, ..., znr} ento, o nmero de r-uplas ordenadas(seqncias de r elementos) do tipo (ai,bj,...,zp) em que ai A e bj

B... zpZ n1.n2. ... . nr . Caso os conjuntos tenham o mesmo nmero de elementos teremos nr .

Aplicao Nvel 1: De quantas formas podemos responder a 12 perguntas de um questionrio, cujas respostas para

cada pergunta so: sim ou no?

Soluo: Cada folha de respostas do questionrio consta de uma seqncia (a1, a2, ... a12 ) em que a1 {S, N}, a2 {S,

N},..., a12 {S, N}. Logo pelo PFCI temos 2.2.2.2.2.2.2.2.2.2.2.2 = 212 formas.

Aplicao Nvel 2: Quantos nmeros telefnicos com 7 dgitos podem ser formados, se usarmos dgitos de 0 a 9?

Soluo: Cada nmero de telefone uma seqncia do tipo (a1, a2, a3, a4, a5, a6, a7) em que a1 {0, 1, 2, ...,9}, a2

{0, 1, 2, ...,9}, ..., a7 {0, 1, 2, ...,9}. Logo pelo PFCI, o nmero de seqncias possveis : 10.10.10.10.10.10.10 =

107=10 000 000 nmeros de telefones.

Aplicao Nvel 3: O sistema telefnico de So Paulo utiliza sete(7) dgitos para designar os diversos telefones.

Supondo que o primeiro dgito seja sempre dois(2) e que o dgito zero (0) no seja utilizado para designar estaes(2

e 3 dgitos), quantos nmeros de telefones diferentes poderemos ter?

Soluo: Seja A = {0, 1, 2, ..., 9}. Cada nmero de telefone uma seqncia do tipo (2, a1, a2, b1, b2, b3 , b4), em que ai

A* e bj A. Ento existem 9 . 9 . 10 . 10 . 10 . 10 . 10 = 81 . 104 nmeros de telefones.

Lema 2: Consideremos o conjuntos A = {a1, a2, ..., am}. Podemos formar m.(m-1) pares ordenados (ai, aj) tais que ai aj (para i j) e ai A e aj A.

Aplicao Nvel 1: Quantos nmeros de dois algarismos distintos podemos formar com os dgitos 1, 2, 3, 4, 5, 6, 7 e 8?

Soluo: Cada nmero pode ser considerado um par de dgitos (a,b) em que a {1, 2, 3, 4, 5, 6 ,7, 8}, b {1, 2, 3, 4,

5, 6 ,7, 8} e a b. Logo pelo Lema 2 o resultado procurado 8 . 7 = 56 nmeros.

Aplicao Nvel 2: Um edifcio tem 8 portas. De quantas formas uma pessoa poder entrar no edifcio e sair por uma

porta diferente da que usou para entrar?

Soluo: Cada percurso consta de um par ordenado (a,b), com a b, em que a representa a porta de entrada, a {1, 2, 3, 4, 5, 6, 7, 8} (quantidade de portas) e b a de sada, b {1, 2, 3, 4, 5, 6, 7}. Temos, ento, 8 . 7 = 56 possibilidades.

Aplicao Nvel 3: Num concurso com 12 participantes, se nenhum puder ganhar mais que um prmio, de quantas

maneiras podero ser distribudos um primeiro e um segundo prmios?

Soluo: Cada entrega de prmios pode ser representada pelo par ordenado (a,b), com a b, em que a representa o primeiro prmio, a {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}(quantidade de participantes) e b representa o segundo prmio,

b {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. Temos ento, pelo Lema 2, 12.11 = 132 possibilidades.

Princpio fundamental da contagem parte II: Consideremos o conjunto A = {a1, a2, ..., am},com m(m>2) elementos.

Ento o nmero de r-uplas ordenadas formadas com elementos distintos dois a dois de A m.(m-1).(m-2). ... . [m (r-

1)].

Aplicao Nvel 1: Quatro atletas participam de uma corrida. Quantos resultados possveis existem para o 1, 2 e 3

lugares?

Soluo: Seja o conjunto dos atletas A = {a1, a2, a3, a4}. Devemos formar r-uplas do tipo (ai, aj, ak), com i j k. Ento pelo PFCII, temos: 4 . 3 . 2 = 24 resultados possveis.

Aplicao Nvel 2: De quantos modos 3 pessoas podem ficar em fila indiana?

Soluo: Seja o conjunto das pessoas P ={a1, a2, a3}. Devemos formar r-uplas do tipo (ai, aj, ak), com i j k. Ento pelo PFCII, temos: 3 . 2 = 6 modos possveis.

Aplicao Nvel 3: Em um baralho de 52 cartas, cinco cartas so escolhidas sucessivamente. Quantas so as seqncias

de resultados possveis se a escolha das cartas for feita sem reposio?

Soluo: Seja o conjunto das cartas C = { a1, a2, ..., a55}. Cada escolha consta de r-uplas do tipo (ai, aj, ak, al, am), com i j k l m. Ento pelo PFCII, temos: 52.51.50.49.48 = 311 875 200 a quantidade de resultados possveis.

2. CONSEQUNCIAS DO PRINCPIO FUNDAMENTAL DA CONTAGEM

Arranjos com repetio: Seja M = {a1, a2, ..., am}. Chamamos arranjo com repetio dos m elementos, tomados r a r,

toda r-upla ordenada formada com elementos de M no necessariamente distintos. Indica-se: (AR)m,r.

Pelo princpio fundamental da contagem I, temos: (AR)m,r = mr, (r fatores) r IN*.

Aplicao Nvel 1: Uma urna contm uma bola vermelha (V), uma branca (B) e uma azul (A). Uma bola extrada,

observada sua cor e reposta na urna. Em seguida outra bola extrada e observada sua cor. Quantas so as possveis

sequncias de cores observadas ?

Soluo: (AR)3,2 = 32 = 9 sequncias.

Aplicao Nvel 2: Um cofre possui um disco marcado com os dgitos 0,1,2...,9. O segredo do cofre formado por uma

sequncia de 3 dgitos. Se uma pessoa tentar abrir o cofre, quantas tentativas dever fazer, no mximo, para

conseguir abri-lo supondo que o segredo formado por dgitos no necessariamente distintos?

Soluo: Para um segredo com dgitos no necessariamente distintos teremos: A = 103 = 1000 tentativas.

Arranjos: Seja M = {a1, a2, ..., am}. Chamamos arranjo dos m elementos, tomados r a r (1 < r < m), toda r-upla ordenada

formada com elementos de M necessariamente distintos. Indica-se: Am,r.

Pelo princpio fundamental da contagem II, temos Am,r = m.(m-1).(m-2). ... . [m (r-1)], (r fatores) com (1 < r < m).

Tambm se costuma escrever Am,r = )!(!rm

m

, m, r IN* com r < m e m! = m.(m-1).(m-2). ... . 3 . 2 . 1.

Aplicao Nvel 1: De um baralho de 52 cartas, 3 cartas so retiradas sucessivamente e sem reposio. Quantas

sequncias de cartas possvel obter?

Soluo: A52,3 = 52.51.50 = 132 600 sequncias.

Aplicao Nvel 2: Um cofre possui um disco marcado com os dgitos 0,1,2...,9. O segredo do cofre formado por uma

sequncia de 3 dgitos. Se uma pessoa tentar abrir o cofre, quantas tentativas dever fazer, no mximo, para conseguir

abri-lo supondo que o segredo formado por dgitos distintos?

Soluo: Para um segredo com dgitos distintos teremos: A10,3 = 10.9.8 = 720 tentativas.

Aplicao Nvel 3: De quantas maneiras um tcnico de futebol pode formar um quadro de 11 jogadores, escolhidos

entre 22, dos quais 3 so goleiros e s o goleiro tem posio fixa?

Soluo: Notemos inicialmente que, se numa configurao o jogador A centroavante e B ponta-direita, ser

considerada distinta a configurao em que A ponta-direita e B centroavante. Da, cada escalao consta de um

goleiro e de uma sequencia ordenada de 10 jogadores escolhidos entre os 19. Como h 3 goleiro, o nmero total de

possiiblidades : 3.A19,10=

5.9200100.566.3810.11.12.13.14.15.16.17.18.19.3!9

!9.10.11.12.13.14.15.16.17.18.19.3

!9!19

.3)!1019(!19

.3)!(!

.3 ====

=

rm

m

.

Aplicao Nvel 4: No jogo de loto, de uma urna contendo 90 pedra numeradas de 1 a 90, quatro pedras so retiradas

sucessivamente; qual o nmero de extraes possveis, tal que a terceira pedra seja 80?

Soluo: Como importa a ordem em que as pedras so sorteadas, cada extrao um arranjo das 89 pedra tomadas 3

a 3, uma vez que se deseja que a 3 pedra seja 80. Logo, o nmero de possibilidades : A89,3 = 89.88.87 = 681.384.

Aplicao Nvel 5: Existem 10 cadeiras numeradas de 1 a 10. De quantas formas duas pessoas podem se sentar,

devendo haver ao menos uma cadeira entre elas?

Soluo: Cada maneira delas sentarem corresponde a um par ordenado: (senta-se A, senta-se B). Ento o total de

pares ordenados A10,2 = 10.9 = 90. Como deve haver ao menos uma cadeira entre elas temos de excluir pares cujos

elementos sejam nmeros consecutivos. So eles: (1,2), (2,3),(3,4),...,(9,10) = 9 pares

+ (2,1),(3,2),(4,3),...,(10,9) = 9 pares = 18 pares.

Portanto, teremos 90 18 = 72 formas.

Aplicao Nvel 6: Qual o numero de funes injetoras definidas em A = {1,2,3} com valores em B = {0,1,2,3,4}?

Soluo: Cada funo vai ser definida por uma n-upla de imagens, em que todos os elementos da n-upla devem ser

distintos, pois a funo injetora. Logo, nmero de funes o nmero de arranjos dos 5 elementos de B, tomados 3

a 3, isto , A5,3 = 5.4.3 = 60 funes injetoras.

Aplicao Nvel 7: Qual a quantidade de nmeros de 3 algarismos que tm pelo menos 2 algarismos repetidos?

Soluo: Calculemos o total de nmeros formados por 3 algarismos no necessariamente distintos (n-upla (a,b,c)):

a pode ser escolhido de 9 maneiras (o 0 no convm para algarismo das centenas);

b e c sero escolhidos entre os 10 algarismos, isto , n-uplas do tipo (b,c), isto , A = 102 = 100.

Assim ao todo teremos 9.100 = 900 nmeros formados de 3 algarismos.( poderamos fazer tambm 999-99 =

900).

Calculemos agora o total de nmeros formados por 3 algarismos distintos. (n-upla(a,b,c)):

a pode ser escolhido de 9 maneiras;

b e c sero escolhidos entre os 9 algarismos restantes, isto , n-uplas do tipo (b,c) sem repetio, isto ,

A9,2 = 9.8 = 72.

Assim ao todo teremos 9 . 72 = 648 nmeros formados por 3 algarismos distintos.

Finalmente, o total de nmeros de 3 algarismos em que pelo menos 2 so repetidos 900 648 = 252.

Aplicao Nvel 8: Com os algarismos 1,2,3,4,5,6 quantos nmeros pares de 3 algarismos distintos podemos formar ?

Soluo: Cada nmero formado uma tripla ordenada do tipo: (_,_,2) ou (_,_,4) ou (_,_,6).

O nmero de triplas possveis de cada tipo : A5,2 = 5.4 = 20. Assim, teremos 20 + 20 + 20 = 60 algarismos distintos.

Permutaes: Seja M = {a1, a2, ..., am}. Chamamos permutao dos m elementos de M a todo arranjo de m elementos

de M em que r = m. Indica-se: Pm.

Da pela definio de arranjo temos: Pm = Am,m = m.(m-1).(m-2). ... . 3.2.1, isto , Pm = m!, m IN*

Obs.: 1! = 1 e 0! = 1.

Aplicao Nvel 1: De quantas formas 5 pessoas podem ficar em fila indiana?

Soluo: Cada forma das pessoas ficarem em fila indiana uma permutao. Assim: P5 = 5! = 5.4.3.2.1= 120 formas.

Aplicao Nvel 2: Formados e dispostos em ordem crescente todos os nmeros que se obtm permutando os

algarismos 1,2,4,6,8, que lugar ocupa o nmero 68412?

Soluo: O nmero 68412 precedido por nmeros da forma:

I) (1,_,_,_,_) que so em nmero de P4 = 4! = 4.3.2.1 = 24

II) (2,_,_,_,_) que so em nmero de P4 = 4! = 4.3.2.1 = 24

III) (4,_,_,_,_) que so em nmero de P4 = 4! = 4.3.2.1 = 24

IV) (6,1,_,_,_) que so em nmero de P3 = 3! = 3.2.1 = 6

V) (6,2,_,_,_) que so em nmero de P3 = 3! = 3.2.1 = 6

VI) (6,4,_,_,_) que so em nmero de P3 = 3! = 3.2.1 = 6

VII) (6,8,1,_,_) que so em nmero de P2 = 2! = 2.1 = 2

VIII) (6,8,2,_,_) que so em nmero de P2 = 2! = 2.1 = 2.

Da conclumos que 68412 precedido por um total de 24 + 24 + 24 + 6 + 6 + 6 + 2 + 2 = 94 nmeros, isto , 68412 o

95 nmero.

Aplicao Nvel 3: Com relao a palavra TEORIA:

a) Quantos anagramas existem? Soluo: P6 = 6! = 720

b) Quantos anagramas comeam por T? Soluo: P5= 5! = 120

c) Quantos anagramas comeam por T e terminam com A? Soluo: P4! = 4! = 24

d) Quantos anagramas comeam por vogal? Soluo: 4.P5! = 4 . 120 = 480

e) Quantos anagramas tm as vogais juntas? Soluo: P3! . P4! = 24 . 6 = 144.

Obs.: na letra e) EOIA funcionam como uma nica letra permutando com T e R (P3) e EOIA permutam entre si (P4).

Aplicao Nvel 4: Calcule o nmero total de inteiros positivos que podem ser formados com os algarismos 1,2,3,4, se

nenhum algarismo repetido em nenhum inteiro.

Soluo: Com apenas um algarismo teremos: 1, 2, 3 e 4; isto , 4 nmeros.

Com dois algarismos teremos: A4,2 = 4.3 = 12 nmeros.

Com trs algarismos teremos: A4,3 = 4.3.2 = 24 nmeros.

Com quatro algarismos teremos: A4,4 = P4 = 4! = 24 nmeros.

Assim ao todo podemos formar 4 + 12 + 24 + 24 = 64 nmeros inteiros positivos.

Aplicao Nvel 5: Quantos anagramas da palavra PASTEL comeam e terminam por consoante?

Soluo: A4,2 . P4 = (4.3) . (4.3.2.1) = 12.24 = 288 anagramas.

Obs.: P4 a permutao das quatro letras entre as consoantes iniciais e finais e A4,2 o arranjo sem repetio das 4

consoantes em dois lugares(incio e fim do anagrama).

Aplicao Nvel 6: As placas dos automveis so formadas por trs letras seguidas de quatro algarismos. Quantas

placas podem ser formadas com as letras A,B e C junto com os algarismos pares, sem haver repetio de letras ou de

algarismos?

Soluo: P3 . A5,4 = 6 . 120 = 720 placas.

Obs.: P3 a permutao das letras trs letras e A5,4 o arranjo de 0,2,4,6,8 nos 4 lugares.

Aplicao Nvel 7: De quantas formas 4 pessoas podem se sentar ao redor de uma mesa circular?

Soluo: (n-1)! = (4-1)! = 3! = 6 formas (permutaes circulares).

Aplicao Nvel 8: Temos m meninos e m meninas. De quantas formas eles podem formar uma roda, de modo que os

meninos e as meninas se alternem?

Soluo: (m-1)!.m! formas.

Combinaes: Seja M = {a1, a2, ..., am}. Chamamos combinaes dos m elementos de M, tomados r a r, aos

subconjuntos de M constitudos de r elementos. Indica-se: Cm,r .

Podemos provar que Cm,r = )!(!!

rmr

m

, m, r IN e r < m.

Obs.: Cm,m = 1, Cm,0 = 1 e C0,0 = 1

Aplicao Nvel 1: Deseja-se formar uma comisso de trs membros e dispe-se de dez funcionrios. Quantas

comisses podem ser formadas?

Soluo: C10,3 = comisses120!7!.3!7.8.9.10

)!310(!3!10

==

Aplicao Nvel 2: Um conjunto A possui n elementos, sendo n>4. Determine o nmero de subconjuntos de A com 4

elementos.

Soluo: Cn,4 = ossubconjuntn

n

n

n

)!4(24!

)!4(!4!

=

Aplicao Nvel 3: O conjunto A tem 45 subconjuntos de 2 elementos. Qual o nmero de elementos de A?

Soluo: Cn,2 = 45, isto , 09045)!2(!2! 2

==

nnn

n

cujas razes so 10 e -9. Da n = 10 elementos.

Aplicao Nvel 4: Em uma reunio social, cada pessoa cumprimentou todas as outras, havendo ao todo 45 apertos de

mo. Quantas pessoas havia na reunio.

Soluo: A apertar a mo de B equivale a B apertar a mo de A. Assim cada aperto de mo uma combinao das n

pessoas tomadas 2 a 2, isto , Cn,2 = 45, isto , n = 10 pessoas.

Aplicao 5: Um grupo tem 10 pessoas. Quantas comisses de no mnimo 4 pessoas podem ser formadas, com as

disponveis?

Soluo: C10,4 + C10,5 + C10,6 + C10,7 + C10,8 + C10,9 + C10,10 = 848.

Obs.: C10,0 + C10,1 + C10,2 + C10,3 + C10,4 + C10,5 + C10,6 + C10,7 + C10,8 + C10,9 + C10,10 = 210

C10,4 + C10,5 + C10,6 + C10,7 + C10,8 + C10,9 + C10,10 = 210 - C10,0 + C10,1 + C10,2 + C10,3 = 848.

Aplicao 6: Um salo tem 20 portas. De quantas maneiras diferentes este so poder ser aberto?

Soluo: O salo poder ser aberto abrindo-se 1,2,... ou at 10 portas. Abrir as portas ABCD equivale a abrir as portas

BCDA. Logo, o nmero de possibilidades dado pela soma das combinaes:

C10,1 + C10,2 + C10,3 + C10,4 + C10,5 + C10,6 + C10,7 + C10,8 + C10,9 + C10,10 = 210 - C10,0 = 2

10 1 = 1023 maneiras.

Aplicao 7: Uma organizao dispe de 10 economistas e 6 administradores. Quantas comisses de 6 pessoas podem

ser formadas de modo que cada comisso tenha no mnimo 3 administradores?

Soluo: CA6,3. CE10,3 + CA6,4. CE10,2 + CA6,5. CE10,1 + CA6,6 . CE10,0 = 2400 + 675 + 60 + 1 = 3136 comisses.

Obs.: CA = combinaes entre administradores e CE = combinaes entre economistas e CA.CE = combinaes das

comisses formadas pelos dois grupos.

Aplicao 8: A diretoria de uma firma constituda por 7 diretores brasileiros e 4 japoneses. Quantas comisses de 3

brasileiros e 3 japoneses podem ser formadas?

Soluo: CB7,3. CJ4,3 = 140 comisses.

Aplicao Nvel 9: Em uma sala h 8 cadeiras e 4 pessoas. De quantos modos distintos essas pessoas podero ocupar

as cadeiras?

Soluo: C8,4 . P4 = 1680 modos.

Obs.: C8,4 a combinao das 8 cadeiras em grupos de 4. P4 o nmero de permutaes entre as 4 pessoas em cada

uma das 4 cadeiras escolhidas.

Aplicao Nvel 10: Calcule o nmero de combinaes de 8 elementos, 3 a 3, que contm um determinado elemento.

Soluo: Como o determinado elemento deve fazer parte da combinao, ficam restando 2 nmeros a serem

escolhidos entre os 7 restantes. O resultado procurado , ento, C7,2 = 21.

Obs.: O nmero de combinaes de n elementos p a p que contm k elementos determinados Cn-k,p-k.

Permutaes com elementos repetidos: Seja M = {a1, a2, a1, a3, .ai, aj, ai,.., am}. Chamamos permutao dos m

elementos de M a todo arranjo de m elementos de M em que r = m. Indica-se: !!...!!

21

,...,, 21

r

nnn

nnnn

nP r =

Aplicao Nvel 1: Quantos anagramas existem da palavra ESTATSTICA?

Soluo: 831600!2!2!3!2!112,2,3,2

11 ==P anagramas.

Aplicao Nvel 2: Uma moeda lanada 20 vezes. Quantas sequncias de caras e coroas existem, com 10 caras e 10

coroas?

Soluo: Cada sequncia obtida uma permutao das 20 faces (como se cada sequncia fosse um anagrama de uma

palavra de 20 letras), sendo 10 caras e 10 coroas (como se a face cara fosse uma letra repetida 10 vezes assim como a

palavra coroa tambm). Assim temos: !10!10

!2010,1020 =P

sequncias.

Aplicao Nvel 3: Uma urna contm 3 bolas vermelhas e 2 amarelas. Elas so extradas uma a uma sem reposio.

Quantas seqncias de cores podemos observar?

Soluo: Cada sequencia de cores observadas uma permutao das 5 bolas, sendo 3 delas vermelhas e 2 delas

amarelas. Assim temos: 10!2!3

!52,35 ==P

sequncias de cores.

Aplicao Nvel 4: Com os dgitos 1,2,3,4,5,6,7, de quantas formas podemos permut-los de modo que os dgitos

mpares fiquem sempre em ordem crescente?

Soluo:

a) Para formar cada permutao, ns escolhemos inicialmente as 4 casas em que sero dispostos os dgitos mpares

(1,3,5,7, nesta ordem). Essa escolha pode ser feita de C7,4 = 35 maneiras diferentes.

b) Para cada escolha feita na etapa anterior, iremos preencher as casas restantes com todas as permutaes dos

dgitos pares (2,4,6), que so em nmero de P3 = 3! = 6.

c) Dessa forma, o total de permutaes satisfatrias 35.6 = 210.