Elementos de Matematica Finita (2010-2011)Combinatoria: S(5, 2) + S(5, 3) problemas

resolvidos

1 - Calcular o coeficiente de x2y no polinomio p(x, y) = (2 + x y)5.

Resolucao: Temos

p(x, y) =( 5

k1, k2, k3

)2k1xk2(y)k3

onde a soma se faz sobre todas as triplas k1, k2, k3 de inteiros nao negativos taisque k1 + k2 + k3 = 5.O coeficinte pretendido e portanto(

5

2, 2, 1

)22(1) = 5!

2!2!22 = 5!

2 - Calcular os coeficientes de x17 e de x18 no polinomio p(x) =(1 + x2 + x3

)15.

Resolucao: Consideramos o polinomio

q(a, b) = (1 + a+ b)15 =( 15

k1, k2, k3

)ak2bk3

onde, tal como no exerccio anterior, a soma se faz sobre todas as triplas k1, k2, k3de inteiros nao negativos tais que k1 + k2 + k3 = 15, e verificamos que, aosubstituir a por x2 e b por x3, os coeficientes pretendidos se obtem como a somados coeficientes multinomiais em que 2k2 + 3k3 seja igual respectivamente a 17ou a 18.No primeiro caso temos(

15

9, 1, 5

)+

(15

8, 4, 3

)+

(15

7, 7, 1

)enquanto que no segundo temos(

15

9, 0, 6

)+

(15

8, 3, 4

)+

(15

7, 6, 2

)+

(15

6, 9, 0

)

3 - Dado um conjunto de m inteiros positivos, mostrar que existe umsubconjunto para o qual a soma dos elementos e divisvel por m.

1

Resolucao: Se os numeros sao a1, a2, , am consideramos a cadeia desubconjuntos

{a1} {a1, a2} {a1, a2, a3} {a1, a2, , am}As somas dos elementos de cada um destes subconjuntos dao-nos m numerosinteiros

b1 = a1b2 = a1 + a2 bm =1 +a2 + + am

e das duas uma: ou estes pertencem a classes de congruencia mod m difer-entes, e entao ha um deles que e divisvel por m, ou pelo princpio do pombal,ha dois (bi e bj , com 1 i < j m) na mesma classe de congruencia. Nestecaso

jl=i+1

al = bj bi 0 mod m

4 - De quantas maneiras podemos sentar 6 homens e 6 mulheres em 3 mesasredondas com 4 lugares cada, na condicao de ficarem 2 homens e 2 mulheres emcada mesa?

Resolucao: Temos que dividir homens e mulheres pelas 3 mesas, o que pode

ser feito de1

3!

((6

2, 2, 2

))2; o factor

1

3!e necessario por as mesas serem todas

iguais. Em cada mesa ha 3! maneiras de sentar as 4 pessoas. A resposta final eportanto

1

3!

((6

2, 2, 2

))2(3!)3 =

(6!)2(3!)2

(2!)6

5 - De quantas maneiras podemos dividir 45 pessoas em 9 equipas de 5pessoas cada e escolher um porta-voz em cada equipa?

Resolucao: Uma vez que as equipas sao todas iguais podemos dividir as

pessoas em equipas de1

9!

(45

5, 5, , 5)

maneiras. A escolha de um porta-voz

pode ser feita de 5 maneiras em cada equipa. Assim a resposta final e

1

9!

(45

5, 5, , 5)

59 =1

9!

45!59

(5!)9

6 - Temos 9 bolas identicas de cada uma de 3 cores. Quantos conjuntos de10 bolas podemos criar?

2

Resolucao: Estamos a contar o numero de maneiras de fazer 10 escolhas,com repeticao e sem ordem, de 3 cores, com a unica restricao de que nao podemosescolher sempre a mesma cor. Como ha tres maneiras de escolher sempre amesma cor, a resposta e(

10 + 3 13 1

) 3 =

(12

2

) 3

7 - Qual o numero de resultados possveis quando se lancam tres dadossimultaneamente?

Resolucao: Neste tipo de problemas, consideramos que os dados sao in-distinguveis entre si, mas que tem faces todas diferentes (nao importa se compintas, figuras, cores, etc.).O que queremos saber portanto e quantas escolhas, nao ordenadas e com repeticao,se podem fazer de 3 elementos de um conjunto com 6 elementos. A resposta e(

6 + 3 13

)= 56

Uma solucao alternativa passa por ordenar as faces dos dados (supondo, porexemplo, que tem pintas, de 1 a 6). As faces que aparecem num lancamentotem valores a, b e c que podem ser ordenados 1 a b c 6 (uma vez queos dados sao iguais); b pode tomar o valor k para exactamente k valores de a;se so tivessemos dois dados concluamos que havia

6k=1

k = 21

resultados possveis.

Com tres dados notamos que c pode tomar o valor k exactamente quandob k, ou seja, pelo raciocnio anterior, em

kj=1

j =k(k + 1)

2

casos. Portanto os resultados possveis para tres dados sao

6k=1

k(k + 1)

2=

1

2

(6k=1

k2 +

6k=1

k

)= 56

3

8 - De quantas maneiras podemos ordenar os elementos do conjunto [n](n > 3) de modo a que o 1 fique antes do 2 e o 3 antes do 4?

Resolucao: Podemos escolher as posicoes em que 1, 2, 3, 4 vao ficar, coloca-los numa das 6 ordens possveis

1, 2, 3, 4; 1, 3, 2, 4; 1, 3, 4, 2; 3, 1, 2, 4; 3, 1, 4, 2; 3, 4, 1, 2

e depois odenar nos espacos restantes os outros numeros de (n 4)! maneiras.O resultado

n!

4

sugere que podamos raciocinar de outra maneira:Uma ordenacao dos elementos de [n] corresponde a uma permutacao do mesmoconjunto. Vamos considerar que duas permutacoes pi e sao equivalentes se

pi = ou pi = (1, 2) ou pi = (3, 4) ou pi = (1, 2) (3, 4) ;esta relacao de equivalencia divide as n! permutacoes em classes com 4 per-mutacoes cada; e em cada classe ha exactamente uma permutacao que, vistacomo uma ordenacao dos elementos, satisfaz as condicoes do enunciado.

9 - Distribuem-se 200 bolas por 100 caixas; nenhuma caixa fica vazia enenhuma caixa contem mais que 100 bolas. Mostrar que e possvel dividir ascaixas em dois grupos de modo a que as caixas de cada grupo contem ao todo100 bolas.Sugestao Designando por xi o numero de bolas da caixa ci, considerar as classesmodulo 100 das somas

sk = x1 + x2 + + xk

Resolucao: Comecamos por notar que se sk sj mod 100 para algunsk < j, isso significa, dado que nao ha caixas vazias, que sj = sk + 100 e que,portanto,

xk+1 + + xj = 100o que nos da a divisao de caixas desejada.Vamos agora verificar que aquela condicao tem mesmo que ocorrer. Se nao fosseesse o caso, para cada 0 m < 100 haveria exactamente uma soma sk mmod 100.Suponhamos que existem t caixas com exactamente uma bola; o caso t = 0corresponde a todas as caixas terem exactamente 2 bolas cada e a resposta eobvia; por outro lado t 98, uma vez que nenhuma caixa pode ter mais do que100 bolas.Suponhamos entao que 0 < t 98 e ordenemos as caixas por ordem nao decres-cente do numero de bolas que contem. De acordo com a hipotese de todas asclasses de congruencia modulo 100 estarem representadas por somas, tem que

4

existir um ndice k para o qual sk t + 1 mod 100; eese ndice tem que sermaior que t e como as caixas com ndice maior que t tem xi > 1 bolas, temossk = t + 101. Mas pelo mesmo raciocnio teria que existir um ndice l para oqual sl = t + 102 t + 2 mod 100 o que so poderia acontecer se l = k + 1 exl = 1, o que e impossvel.

Podamos tambem argumentar que, com a ordem nao decrescente adoptada,xt+1 t+ 1; caso contrario

t+ (100 t)(t+ 2) 200 t(t 99) 0o que e impossvel. E entao, se existisse uma soma sk = t+ 101, teramos

x1 + + xxt+11 + xt+2 + + xk = 100,ou seja, retirando ao conjunto de caixas Ci, com t < i k, a caixa Ct+1 eacrecentando xt+1 1 caixas com uma bola cada, ficamos com um conjuntocontendo exactamente 100 bolas como queramos.

10 - Determinar uma formula para o numero de maneiras de alinhar 40bolas brancas e 40 bolas pretas, de modo a que nao haja mais do 3 bolas brancasseguidas.

Resolucao: Alinhando as 40 bolas pretas temos 41 espacos pelos quaisdistribuir as 40 bolas brancas, com a restricao indicada. Trata-se de contar assolucoes de

x1 + + x41 = 40, 0 xi 3 i

Sem a resticao o numero de solucoes e

(40 + 41 1

40

)=

(80

40

); se Xi designar

o conjunto das solucoes em que xi > 3, queremos calcular(80

40

) |

41i=1

Xi|

Calculamos a segunda parcela pelo Princpio de Inclusao-Exclusao; |Xi| =(36 + 40

40

)(colocamos 4 bolas no espaco i e distribumos as 36 restantes), e,

para qualquer escolha de ndices i1, , ik

|Xi1 Xik | =(

40 4k + 4040

)Note-se que basta considerar k 10; portanto(

80

40

)|

41i=1

Xi| =(

80

40

)

10j=1

(1)j1(

41

j

)(80 4j

40

)=

10j=0

(1)j(

41

j

)(80 4j

40

)

5

11 - Em quantas permutacoes de {1, 2 , n} e que 3(1) = 1?

Resolucao: 3(1) = 1 ocorre se 1 esta num ciclo de comprimento 1 ou3; o primeiro caso acontece para (n 1)! permutacoes (1 esta fixo e os outroselementos permutam entre si); para obter uma permutacao com 1 num ciclode comprimento 3, temos que escolher dois elementos para estarem no mesmociclo, ordenar o ciclo e permutar os restantes n 3 elementos; logo existem2

(n 1

2

)(n 3)! permutacoes nessas condicoes. Potanto a resposta e

(n 1)! + 2(n 1

2

)(n 3)! = 2(n 1)!

12 - a) Quantos numeros 1 n 300 sao divisveis por 3 mas ou nao saodivisveis por 5 ou nao sao divisveis por 7?

b) Quantos numeros 1 n 300 sao divisveis por 3 mas nao sao divisveisnem por 5 nem por 7?

Resolucao: Convem introduzir os conjuntos

A = {1 x 300 : x 0 mod 3}B = {1 x 300 : x 0 mod 5}C = {1 x 300 : x 0 mod 7}

Alem disso vamos usar a notacao Xc para designar o complementar de X emN300.

Na alnea a) temos que excluir de A os numeros que sejam simultaneamentemultiplos de 5 e de 7, ou seja os multiplos de 105; temos 100 2 = 98 =|A (B C)c| numeros.

Se interpretarmos o ou na frase como uma dijuncao exclusiva, entao temosque contar os multiplos de 3 e de 5 mas nao de 7 e os multiplos de 3 e de 7 masnao de 5, ou seja os multiplos de 15 mas nao de 105 e os multiplos de 21 masnao de 105:

|A B CcA C Bc| = (20 2) + (14 2) = 30

Note-se que aqui nao ha aplicacao do Princpio de Inclusao - Exclusao, ja quetemos a uniao de dois conjuntos qu nao se intersectam.

Na alnea b) queremos contar os elementos de ABc Cc = (Ac B C)c.Ora

A Bc Cc = A \ (A B A C)

6

e|A| = 100, |A B| = 20, |A C| = 14, |A B C| = 2

donde, pelo Princpio de Inclusao - Exclusao

|A Bc Cc| = 100 20 14 + 2 = 68

13 - - De quantas maneiras podemos sentar 21 pessoas, incluindo o Joao ea Ines, numa mesa redonda de modo a que o Joao e a Ines nao fiquem lado alado?

Resolucao: Sentando o Joao num lugar arbitrario, temos 18 lugares parasentar a Ines e 19! maneiras de sentar as restantes pessoas. Portanto a respostae 18 19!.Em alternativa podemos contar todas as maneiras de sentar as 21 pessoas numamesa redonda, que sao 20!, e subtrair as maneiras de as sentar de modo aque o Joao e a Ines fiquem juntos, que sao 2 19! porque podemos escolherarbitrariamente um par de cadeiras onde os dois se podem sentar de 2 maneiras,e sentar depois as outras pessoas de 19! modos diferentes.

14 - - a) Quantos anagramas (ou seja, palavras obtidas por reordenacaodas letras) existem da palavra BANANA?

b) Em quantos anagramas da palavra MISSISSIPPI e que os dois primeirosI aparecem antes do primeiro S?

Resolucao: a) Um anagrama de BANANA pode ser identificado com umafuncao f do conjunto dos 6 espacos no conjunto das 3 letras de tal modo que ftoma o valor B 1 vez, o valor A 3 vezes e o valor N 2 vezes, e portanto o seunumero e dado por (

6

2, 3, 1

)=

6!

2!3!= 60

b) Uma das formas de resolver e comecar por alinhar os quatro I e distribuiros quatro S pelas 3 posicoes possveis (so depois do segundo I) o que se pode

fazer de

(4 + 3 1

3 1)

maneiras. Em seguida, temos que escolher lugares para os

P de

(2 + 8

8

)maneiras e finalmente escolher um dos 11 lugares para o M.

Temos portanto um total de

11

(6

2

)(10

8

)= 14850

7

anagramas com a condicao dada.

15 - - Dados 5 pontos no plano com coordenadas inteiras, mostrar que pelomenos um dos segmentos unindo dois desses pontos contem mais um ponto decoordenadas inteiras.Sugestao: para cada ponto (x, y) considerar o par (x mod 2, y mod 2). Quan-tos pares destes existem?

Resolucao: O Princpio do Pombal garante que 2 dos 5 pontos, chamemos-lhes (a, b) e (c, d), sao congruentes mod 2, em cada coordenada; logo

a+ c 0 mod 2, b+ d 0 mod 2

e portanto o ponto (a+ c

2,b+ d

2) tem coordenadas inteiras.

16 - - Quantas solucoes em inteiros nao negativos existem para a equacao

x+ y + z + w = 7?

Resolucao: A resposta e (10

7

)que pode ser visto como o numero de maneiras de fazer 7 escolhas, nao ordenadase com repeticao, de entre 4 objectos; ou tambem como o numero de maneirasde escolher as posicoes de 3 marcas para separar 7 objectos em quatro grupos;etc.Em geral portanto o numero de solucoes em inteiros nao-negativos de umaequacao

x1 + x2 + + xk = ne (

n+ k 1k 1

)E o numero de solucoes em inteiros positivos e(

n 1k 1

)Isso pode concluir-se notando que a cada solucao x1, x2, , xk de

x1 + x2 + + xk = nem inteiros positivos, corresponde uma solucao x1 1, x2 1, , xk 1 daequacao

y1 + y2 + + yk = n k

8

em inteiros na-negativos.

17 - - Quantas palavras de 4 letras (com um alfabeto de 26 letras) existemem que as letras esto em ordem alfabtica?

Resolucao: Trata-se de escolher ( com repeticao) 4 posicoes em 26 lugares,

logo existem

(26 + 4 1

4

)=

(29

4

).

Se consideramos palavras sem letras repetidas, existem

(26

4

).

18 - - Quantas palavras de tres letras diferentes existem em que a letra domeio e uma vogal?

Resolucao: Com um alfabeto de 26 letras, temos 5 25 24 palavras.

19 - - Quantos caminhos de comprimento mnimo, constitudos por segmen-tos de comprimento 1 paralelos aos eixos, partem da origem (0, 0) e terminamno ponto (10, 6)?

Resolucao: Sao as maneiras de escolher de entre 16 segmentos que con-

stituem o caminho as posicoes dos 6 segmentos verticais, logo existem

(16

6

)caminhos.

20 - Quantos alinhamentos de quatro A, seis B e cinco C e que contem asequencia ABA? .

Resolucao: Num mesmo alinhamento a sequencia ABA pode ocorrer emmais do que uma posicao. Chamando Xi, com 1 i 13, ao conjunto dos alin-hamentos em que ABA ocorre com incio na posicao i, vamos usar o Princpiode Inclusao-Exclusao para contar |13i=1Xi|.|Xi| =

(12

2, 5, 5

)uma vez que, depois de colocada a sequencia na posicao indi-

cada nos restam 12 espacos para distribuir pelas restantes letras (dois A, cincoB e cinco C).As interseccoes XiXj com i < j tem diferente numero de elementos, conformej i = 2 ou j i > 2: no primeiro caso temos a sequencia ABABA a comecarna posicao i, onde 1 i 11, o que pode acontecer em

(10

1, 4, 5

)alinhamentos;

no segundo caso, temos duas ocorrencias separadas de ABA, uma comecandonuma posicao i 10 e a outra numa posicao i+ 3 j 13; para cada escolha

9

destas posicoes temos

(9

4, 5

)alinhamentos.

Finalmente, podemos ter interseccoes do tipo Xi Xi+2 Xi+4, com 1 i 9,e cada uma delas tem

(8

3, 5

)alinhamentos.

O resultado final e

13

(12

2, 5, 5

) 11

(10

1, 4, 5

) 55

(9

4, 5

)+ 9

(8

3, 5

)(o que da, so por curiosidade, 195930 alinhamentos...)

21 - Determinar uma formula para o numero de permutacoes de {1, 2 , n}que tem um ciclo de comprimento 2.

Resolucao: Podemos construir uma permutacao com um ciclo de compri-mento 2 escolhendo os dois elementos do ciclo e permutando os restantes n 2elementos entre si, de

(n

2

)(n 2)! maneiras. No entanto, uma permutacao

dessas pode conter outros ciclos de comprimento dois e para nao contar a maistemos que usar o Princpio de Inclusao-Exclusao: para cada par de elementosa, b {1, 2 , n} consideramos o conjunto X{ab} das permutacoes que contemo ciclo (a b). Queremos calcular o numero de elementos da uniao de todos osX{ab}.

Para cada k n/2, podemos escolher k pares de elementos de(

n

2, , 2, n 2k)

maneiras e permutar os elementos restantes de (n2k)! maneiras; como a ordemdos pares nao interessa temos que dividir por k!. Portanto temos

bn/2cj=1

(1)j1 1j!

(n

2, , 2, n 2j)

(n 2j)! = n!bn/2cj=1

(1)j1 1j!2j

A pergunta refere-se a permutacoes que contem pelo menos um ciclo decomprimento 2. Mas o calculo efectuado permite tamem dar uma formula para onumero de permutacoes com exactamente um ciclo de comprimento 2: Para cadapar de elementos {a, b}, as permutacoes que contem o ciclo a b) e nenhum outrociclo de comprimento 2 estao em bijeccao com as permutacoes de {1, , n2}que nao tem ciclos de comprimento 2. Ora, de acordo com o calculo anterior,aplicado a n 2, existem

(n 2)! (n 2)!b(n2)/2c

j=1

(1)j1 1j!2j

= (n 2)!b(n2)/2c

j=0

(1)j 1j!2j

10

permutacoes de {1, , n 2} nessas condicoes. Como podemos escolher o parde

(n

2

)maneiras, temos

(n

2

)(n 2)!

b(n2)/2cj=0

(1)j 1j!2j

=n!

2

b(n2)/2cj=0

(1)j 1j!2j

permutacoes de {1, 2 , n} com exactamente um ciclo de comprimento 2.

22 - - Quantas palavras de 10 letras nao contem todas as vogais?

Resolucao: Se A,E, I,O, U designarem os conjuntos das palavras de 10letras que nao contem cada uma das vogais, queremos calcular |AEIOU |e podemos aplicar o Princpio de Inclusao-Exclusao.Ora, cada um daqueles conjuntos tem 2510 elementos, a interseccao de dois delestem 2410 elementos, etc.

Tendo em conta que ha

(5

k

)modos de escolher k desses conjuntos, conclumos

que o numero de palavras e

5k=1

(1)k1(

5

k

)(26 k)10

23 - - De quantas maneiras podemos organizar 18 pessoas em

a) tres grupos de 5, 6 e 7 pessoas;

b) quatro grupos de 4, 4, 5 e 5 pessoas.

Resolucao: a)

(18

5, 6, 7

).

b)1

4

(18

4, 4, 5, 5

). O factor

1

4=

1

2!2!e necessario porque o numero multi-

nomial conta como casos diferentes aqueles em que, por exemplo, as pessoasA,B,C,D ficam no primeiro grupo de 4 e E,F,G,H no segundo, e aqueles emque estas ficam no primeiro e as outras no segundo.

24 - - De quantas maneiras se podem seleccionar 5 numeros no conjunto{1, 2, , 30} de modo a que o valor absoluto da diferenca entre quaisquer doisdeles seja pelo menos 3?

11

Resolucao: Temos 5 incognitas e intercalamos 2 espacos entre cada duasdelas. Sobram 30 5 8 = 17 espacos para distribuir por 6 intervalos, logotemos

(17 + 6 1

17

).

25 - - De quantas maneiras podemos seleccionar k pessoas numa mesaredonda com n pessoas (e n lugares) de modo a nunca escolher pessoas queestejam sentadas lado a lado?

Resolucao: Fixamos uma pessoa X e dividimos o problema em dois casos:Se X e seleccionado, os vizinhos nao sao, e sobram n 3 pessoas das quaistemos que escolher k 1 nao vizinhas. Este problema e equivalente aos modosde contar as palavras com k 1 S e n k 2 R, sem S seguidos; Se tivermosos k 1 S com k 2 R intercalados, sobram n 2k R para distribuir por kespacos, o que se pode fazer de

(n k 1k 1

)maneiras.

Se X nao for seleccionado, entao repetimos o raciocnio anterior mas com k S e

n k 1 R e obtemos(n kk

)maneiras.

Logo a resposta final e (n k 1k 1

)+

(n kk

)Este valor e igual a

(n k 1k 1

)n

k. O significado combinatorio desta expressao

e que X pode ser escolhido arbitrariamente entre as n pessoas. Assim se multi-

plicarmos

(n k 1k 1

)por n estamos a contar cada equipa de seleccionados k

vezes.

26 - - Num jogo em que sao sorteados 6 numeros no conjunto {1, 2, , 50},qual e a probabilidade de:

a) acertar em 3 numeros numa aposta simples de 6 numeros;

b) acertar em 4 numeros numa aposta multipla de 8 numeros

Resolucao: Nestes problemas, convem precisar que estamos a considerartodos os resultados como tendo a mesma probabilidade. Portanto, o valor pe-dido e o resultado da divisao do numero de casos favoraveis pelo numero decasos possveis. Temos entao:

a)

(6

3

)(44

3

)(

50

6

) .

12

b)

(6

4

)(44

4

)(

50

8

) .Podemos generalizar o problema: num jogo em que sao sorteados m numeros

de entre N , qual a probabilidade de, apostando em p numeros, acertar emexactamente k numeros? A generalizacao da resposta da alnea b) seria entao(

p

k

)(N pm k

)(N

m

) ,ou seja, tomamos como casos possveis todas as chaves de m numeros e comocasos favoraveis as que contem k elementos da aposta de p numeros e m knumeros nao apostados.Nesta solucao, tomamos o conjunto de p numeros apostados como dado ecomparamo-lo com todos os resultados possveis do sorteio. Podemos racioci-nar de outra forma, fixando uma chave sorteada e comparando-a com todas asapostas possveis. Desse modo obteramos como probabilidade de acertar emexactamente k numeros (

m

k

)(N mp k

)(N

p

) ;um calculo simples comprova que estes resultados sao iguais.

27 - De quantas maneiras podemos distribuir 20 bolas identicas por 8 caixasC1, C2, , C8, com a condicao das caixas C1 e C2 terem o mesmo numero debolas?E se as bolas forem tambem diferentes?

Resolucao: Cada uma das caixas C1 e C2 fica com k bolas em que 0 k 10. As restantes bolas sao distribudas pelas 6 outras caixas de

(20 2k + 5

5

)maneiras. Logo a resposta e

10k=0

(25 2k

5

)

Se as bolas sao diferentes, temos20!

(k!)2(20 2k)! maneiras de escolher doisconjuntos de k bolas paras as duas primeiras caixas, com 0 k 10; as

13

restantes bolas distribuem-se de 6202k maneiras pelas outras caixas (para cadabola, temos 6 caixas a` escolha). Logo a resposta neste caso e

10k=0

20!

(k!)2(20 2k)!6202k

28 - Quantas solucoes em inteiros existem para o sistema 0 < x < y < z n pois se k > n

tem-se

(n

k

)= 0

33 - De quantas maneiras podemos ordenar o conjunto {0, 1, 2, , 9} demodo a obter pelo menos uma das sequencias

1, 2, 3 3, 4, 5 4, 5, 6?

Resolucao: Se X1 e o conjunto das ordenacoes (ou permutacoes) de [9] emque aparece a sequencia 1, 2, 3, X2 e o conjunto das ordenacoes em que aparece asequencia 3, 4, 5, e X3 e o conjunto das ordenacoes e m que aparece a sequencia4, 5, 6, queremos calcular

|X1 X2 X3|e usamos o Princpio de Inclusao-Exclusao. Vemos primeiro que

|X1| = |X2| = |X3| = 7!

uma vez que, por exemplo, para X1, contamos as maneiras de ordenar os ele-mentos do conjunto

{{1, 2, 3}, 4, 5, 6, 7, 8, 9}.Do mesmo modo

|X1 X2| = 5! = |X1 X3|, |X2 X3| = 6!

e|X1 X2 X3| = 4!

e portanto|X1 X2 X3| = 3 7! 6! 2 5! + 4!

34 - Quantos subconjuntos de 10 letras do alfabeto nao contem duas letrasconsecutivas?

Resolucao: O problema e equivalente ao seguinte: quantas sequencias ex-istem com 10 S (seleccionados) e 16 R (rejeitados), sem 2 S consecutivos?

16

Alinhamos os 10 S com 9 R intercalados e distribumos os restantes R pelos 11

espacos possveis, com possvel repeticao e sem ordem, de

(7 + 10

10

)maneiras .

35 - De quantas maneiras podemos sentar n casais numa mesa redonda demodo a que nenhum casal fique lado a lado? E de quantas maneiras podemossentar n casais numa mesa redonda de modo a que os homens e as mulheresfiquem intercalados mas nenhum casal fique lado a lado?

Resolucao: Para qualquer dos problemas, o mais importante nesta aplicacaodo Princpio de Inclusao-Exclusao e a escolha da ordem por que fazemos os di-versos passos da contagem. Comecamos pelo primeiro.Designamos por Xi as maneiras de sentar as pessoas a` mesa em que o casal ifica lado a lado; colocando o casal i em dois lugares consecutivos de um dos2 modos possveis - homem a` direita ou a` esquerda da mulher - ha (2n 2)!maneiras de sentar as restantes pessoas. Logo |Xi| = 2(2n 2)!.Mais geralmente, se escolhermos j casais i1, , ij de

(n

j

)maneiras, podemos

distribu-los a` volta da mesa de (j 1)! maneiras, escolher para cada casalquem fica a` direita - 2j possibilidades - e distribuir depois as 2n 2j pessoasrestantes pelos j espacos. Para isso distribumos 2n 2j cadeiras pelos espacosde

(2n 2j + j 1

j 1)

maneiras e depois sentamos as pessoas nessas cadeiras de

(2n 2j)! maneiras. Em resumo,

|Xi1 Xij | = 2j(j 1)!(

2n j 1j 1

)(2n 2j)!

Como podemos sentar as pessoas sem restricoes de (2n1)! maneiras, o Princpiode Inclusao-Exclusao diz-nos que a resposta e

(2n 1)!nj=1

(1)j1(n

j

)2j(j 1)!

(2n j 1j 1

)(2n 2j)! =

= (2n 1)!nj=1

(1)j1(n

j

)2j(2n j 1)! =

=

nj=0

(1)j(n

j

)2j(2n j 1)!

Note-se que o calculo de Xi1 Xij | podia ter sido feita de modo diferente:sentamos o casal i1 (2 maneiras) e, antes de sentar os outros casais que vao ficarobrigatoriamente lado a lado, colocamos as restantes 2n 2j pessoas a` voltada mesa ((2n 2j)! maneiras); temos 2n 2j + 1 posicoes por onde distribuir

17

j1 pares de cadeiras para os casais a` espera ((j 1 + 2n 2j

j 1)

escolhas com

possvel repticao e sem ordem); finalmente distribumos os casais por esses paresde cadeiras de (j 1)! maneiras e ordenamo-los de 2j1 maneiras.Como e facil verificar, o resultado coincide. O interesse nesta maneira de ordenaras escolhas e que se adapta muito bem ao segundo problema, em que queremosque homens e mulheres fiquem intercalados:Em primeiro lugar, sem a restricao de separar os casais, ha (n 1)!n! maneirasde sentar homens e mulheres intercalados: ordenamos as mulheres a` volta damesa de (n 1)! maneiras e depois escolhemos os lugares dos homens.Suponhamos agora que queremos garantir que os casais i1, , ij ficam lado alado. Podemos primeiro sentar o casal i1 (2 maneiras); em seguida alinhamosprimeiro as n j mulheres e depois os n j homens intercalados ((n j)!2maneiras), respeitando a ordem do primeiro casal, ou seja, ficamos com nj+1mulheres e n j + 1 homens intercalados a` volta da mesa; temos de novo 2n2j+1 espacos para distribuir, com possvel repeticao e sem ordem, os j1 paresde cadeiras para os casais i2, , ij , o que se pode fazer de

(j 1 + 2n 2j

2n 2j)

maneiras; e distribumos os casais por esses pares de cadeiras de (j1)! maneiras.Cada um desses casais ja nao tem escolha sobre quem fica a` direita: num espacoM H tem que ficar na posicao H M, e vice versa. Em resumo, a solucao e

(n 1)!n!nj=1

(1)j1(n

j

)2(n j)!2

(j 1 + 2n 2j

2n 2j)

(j 1)!

Neste caso a simplificacao da expressao nao e tao evidente:

(n 1)!n!nj=1

(1)j1(n

j

)2(n j)!2

(j 1 + 2n 2j

2n 2j)

(j 1)! =

= (n 1)!n!nj=1

(1)j12n!j!

(n j)! (2n j 1)!(2n 2j)! =

= (n 1)!n!nj=1

(1)j12 n!2n j (n j)!

(2n j)!j!(2n 2j)! =

= 2n!

nj=0

(1)j (n j)!2n j

(2n jj

)

36 - Para um k n fixo qualquer,a) em quantas permutacoes pi Sn e que 1 pertence a um ciclo de compri-

mento k (abreviadamente, um k-ciclo)?

b) quantas permutacoes pi Sn tem (pelo menos) um k-ciclo?

18

Resolucao: a) podemos escolher os outros elementos do ciclo de

(n 1k 1

)maneiras, e ordenar o ciclo de (k 1)! maneiras. Os restantes elementos saopermutados livremente entre si de (n k)! maneiras. Logo a resposta, que eafinal independente de k, e(

n 1k 1

)(k 1)!(n k)! = (n 1)!

b) numa possvel primeira abordagem, poderamos pensar em usar o Princpiode Inclusao-Exclusao do seguinte modo: se, para 1 i n,

Xi = {pi Sn : i pertence a um k-ciclo}queremos calcular

|i

Xi| =nj=1

(1)j1Tj

ondeTj =

|Xi1 Xij |

com esta soma a fazer-se sobre todas as possveis escolhas de ndices 1 i1 < < ij .A dificuldade desta abordagem surge quando tentamos contar o numero de el-ementos dessas interseccoes: os elementos i1, , ij podem pertencer a variosk-ciclos, nao necessariamente diferentes e ha um grande numero de casos dis-tintos.

E prefervel contar permutacoes com um, dois ou mais k-ciclos de outromodo. Notemos antes do mais que pi Sn pode ter, no maximo, bnk c k-ciclos.

Dado um k-ciclo c = (x1, , xk), designe-se por Xc o conjunto das per-mutacoes que contem o ciclo c. Queremos calcular | Xc| em que a uniao se fazsobre todos os possveis k-ciclos.Tem-se obviamente |Xc| = (n k)!, e, do mesmo modo, dados j k-ciclos com-patveis (ou seja, disjuntos dois a dois), c1, , cj temos

|Xc1 ,Xcj | = (n jk)!;por outro lado, podemos escolher j k-ciclos compatveis de

1

j!

(n

k, , k, n jk)

(k 1)!j = n!j!kj(n jk)!

maneiras. Entao o Princpio de Inclusao-Exclusao da

| Xc| =bn/kcj=1

(1)j1 n!j!kj

19

37 - Se pi Sn tem tipo cclico [i1, , in], o que podemos dizer sobre otipo cclico de

pik = pi pi pi, (k vezes)?

Resolucao: Como se vera, nao vamos chegar a uma resposta dada por umaformula simples, valida para qualquer k e qualquer tipo cclico de pi.Podemos analisar a decomposicao cclica de pik, estudando separadamente oque se passa em cada um dos seus ciclos (uma vez que estes sao disjuntos).Consideremos um ciclo de comprimento j n

(x0, , xj1).Na composicao desta permutacao cclica consigo mesma k vezes, cada elementoxi tem como imagem xi+k mod j ; portanto, o comprimento do ciclo de xi em pi

k

e o menor t > 0 tal que kt 0 mod j e depende apenas de k e de j e nao doelemento xi. Ou seja, o ciclo original de comprimento j de pi decompoe-se emj/t ciclos de comprimento t. Ora a menor solucao positiva daquela congruenciae j/d, onde d = mdc(k, j).Por exemplo, um k ciclo de pi da lugar a k 1-ciclos de pik. Por outro lado, se pitem um j-ciclo, em que j e primo com k, pik mantem esse j-ciclo.Fixando um l n, um j-ciclo de pi da origem a l-ciclos de pik se

l =j

mdc(k, j);

se for esse o caso, os ij j-ciclos de pi dao ijmdc(k, j) ciclos de comprimento l depik.Quereramos portanto determinar, em funcao de k e de l, quais os 1 j nque satisfazem aquela igualdade. Deixa-se aos mais persistentes a verificacao deque as solucoes (para cada l) sao os 1 j n da forma j = dl em que

d | k e mdc(kd, l) = 1

Logo, o numero de ciclos de comprimento l de pik, em funcao do tipo cclico depi, e dado por

dild : d | k,mdc(kd, l) = 1, 1 ld n

38 - O sinal de uma permutacao pi de n elementos e definido como 1 se pie par e 1 se e mpar.Mostrar que se pi e do tipo [i1, i2 in] entao o sinal de pi e (1)n+i1+i2++in .

Resolucao: O tipo cclico de pi indica-nos que a permutacao tem i1 1-ciclos,i2 2-ciclos e assim por diante. Como se viu, um k-ciclo pode ser representadocomo a composicao de k 1 transposicoes:

(x1, x2, , xk1, xk) = (x1, x2)(x2, x3) (xk1, xk);

20

portanto pi pode ser obtido como a composicao de

i2 + 2i3 + + (n 1)in =nj=1

(j 1)ij

transposicoes. Mas, por outro lado, sabemos que

nj=1

jij = n,

logo

n+

nj=1

ij =

nj=1

(j + 1)ij =

nj=1

(j 1)ij + 2nj=1

ij

e(1)n+

nj=1 ij = (1)

nj=1(j1)ij

39 - Quantas sequencias de letras podemos formar com 2 M, 4 A, 5 Te 6 O, se cada sequencia e a sua inversa (lida da direita para a esquerda) saoconsideradas a mesma?E de quantas maneiras podemos colocar as mesmas letras nos vertices de umpolgono regular com 17 lados, se arranjos obtidos um do outro por uma simetriado polgono sao considerados iguais?

Resolucao: Este e um problema de contagem com simetria muito simples,em que o grupo de simetria tem apenas dois elementos: a identidade e a reflexaocorrespondente a ler da direita para a esquerda. O numero total de sequenciasque se podem escrever com aquelas letras e(

17

2, 4, 5, 6

)Para contarmos as sequencias que ficam invariantes pela reflexao, notamos quea letra do meio tem que ser um T e que basta contar as sequencias que se podemformar com 1 M, 2 A, 2 T e 3 O, cada uma destas constituindo o princpio deuma sequencia simetrica.O teorema de Frobenius-Burnside da-nos

1

2

((17

2, 4, 5, 6

)+

(8

1, 2, 2, 3

))= 42883680

40 - Quantos cubos diferentes com arestas de comprimento 2 se podemconstruir usando cubos de arestas de comprimento 1 de 5 cores diferentes? E seforem cubos com arestas de comprimento 3?

21

Resolucao: Para construir o cubo com aresta de comprimento 2 usamos8 cubos de aresta 1. Se nao contarmos com as simetrias do cubo, temos 58

cubos diferentes. Para usar o teorema de Frobenius-Burnside, notamos quecada escolha dos 8 cubos corresponde a uma maneira de colorir os vertices docubo maior e vice-versa.Recordemos como actuam os 24 elementos do grupo de simetria do cubo comopermutacoes dos vertices:

1. A identidade tem 8 1-ciclos.

2. Por cada par de faces opostas, ha uma rotacao de pi/2; a permutacaoinduzida e 3 tem 2 4-ciclos, enquanto que 2 tem 4 2-ciclos.

3. Por cada par de vertices opostos, ha uma rotacao de 2pi/3; a permutacao, bem como 2 tem 2 1-ciclos e 2 3-ciclos.

4. Por cada par de arestas opostas, temos uma rotacao de pi que induz umapermutacao com 4 2-ciclos.

Obtemos da formula geral

1

|G|piG|I(pi)| = 1

24

(58 + 6 52 + 17 54) = 16725

O problema de contar cubos com arestas de comprimento 3 pode ser resolvidocontando os ciclos das permutacoes dos 27 cubos pequenos que sao induzidaspelas simetrias do cubo maior:

1. A identidade tem 27 1-ciclos.

2. Por cada par de faces opostas, ha uma rotacao de pi/2; a permutacaoinduzida e 3 tem 3 1-ciclos e 6 4-ciclos, enquanto que 2 tem 3 1-ciclose 12 2-ciclos.

3. Por cada par de vertices opostos, ha uma rotacao de 2pi/3; a permutacao, bem como 2 tem 3 1-ciclos e 8 3-ciclos.

4. Por cada par de arestas opostas, temos uma rotacao de pi que induz umapermutacao com 3 1-ciclos e 12 2-ciclos.

O resultado dest vez e

1

24

(527 + 6 59 + 9 515 + 8 511) = 310440869666015625

Se considerarmos que a cor do cubo interior nao interessa, devemos diminuirum 1-ciclo a cada permutacao e ficamos como

1

24

(526 + 6 58 + 9 514 + 8 510) = 62088173933203125

41 -

22

a) Mostrar, usando o Princpio de Inclusao-Exclusao, que o numero de maneirasde colorir os vertices numerados de um polgono de n vertices com m cores,com a condicao de vertices adjacentes (ou seja, ligados por uma aresta)terem cores diferentes, e igual a

(m 1)n + (1)n(m 1)

b) De quantas maneiras podemos colorir os vertices de um polgono regularde n vertices com m cores, com a condicao de vertices adjacentes teremcores diferentes?

Nota: A condicao na primeira alnea dos vertices estarem numerados, cor-responde a termos um polgono numa posicao fixa. Na segunda alnea, temosja que ter em conta o efeito das simetrias do polgono.

Resolucao: a) Numeramos os vertices do polgono seguindo a sua ordemcclica. Chamamos Xi, para i < n, ao conjunto das coloracoes em que os verticesadjacentes vi e vi+1 tem a mesma cor; e Xn e o conjunto das coloracoes em queos vertices vn e v1 tem a mesma cor.Como existem ao todo mn coloracoes, queremos calcular

mn ni=1

Xi

.Para cada i, |Xi| = mn1. E se escolhermos j < n vertices i1, i2, , ij , temos

|Xi1 Xi2 Xij | = mnj ;podemos visualizar essa contagem, imaginando que colamos cada vertice vilao seu vizinho vil+1; cada colagem diminui o numero de blocos de vertices numaunidade e ficamos portanto com n j blocos de vertices para colorir.E preciso no entanto notar que para j = n, existem m coloracoes (e nao 1 comoa formula acima indicaria). A aplicacao do Princpio de Inclusao-Exclusao da-nos entao que o numero de coloracoes em que vertices adjacentes tem coresdiferentes e

mn n1j=1

(1)j1(n

j

)mnj (1)n1m

Vemos que a soma da primeira parcela com o somatorio se pode escrever

n1j=0

(1)j(n

j

)mnj = (m 1)n (1)n

pelo Teorema do binomio. Portanto a resposta pode ser escrita de forma maisresumida como

(m 1)n (1)n (1)n1m = (m 1)n + (1)n(m 1).

23

b) Um polgono regular com n vertices tem um grupo de simetrias Dn com2n elementos, n rotacoes e n reflexoes. De acordo com o teorema de Frobenius-Burnside, temos que contar quantas coloracoes ficam invariantes por accao decada uma delas, o que so depende, como ja se viu, do numero de ciclos na re-spectiva permutacao dos vertices.Note-se que o calculo destes numeros de ciclos nao interessa apenas para contarcoloracoes com vertices adjacentes de cores diferentes, mas para qualquer prob-lema de contagem com simetria envolvendo os vertices de um polgono regular.Vamos realizar esse calculo e aplica-lo primeiro no caso mais simples de contartodas as coloracoes dos vertices com m cores (sem restricoes sobre as cores dosvertices adjacentes).A identidade tem obviamente n ciclos. A permutacao, chamemos-lhe , resul-tante da rotacao, por um angulo de 2pi/n (por exemplo no sentido retrogrado),tem 1 ciclo. Mas as permutacoes (k) (que correspondem a fazer uma rotacaode 2kpi/n) tem um numero de ciclos que depende de k e n. Estamos num casoespecial do problema 3. desta ficha: (k) tem d ciclos de comprimento n/d, emque d = mdc(k, n); para simplificar a formula final, podemos ver, para cadad | n, para quantos valores de k se tem d = mdc(k, n); mas ha (n/d) inteiros1 j < n/d tais que 1 = mdc(j, n/d); portanto ha tambem (n/d) valores de1 k n com d = mdc(k, n) (k = dj para cada valor de j).Temos tambem que contar o numero de ciclos das n reflexoes; se n e par temosn/2 reflexoes sobre eixos unindo faces opostas do polgono, que induzem umapermutacao dos vertices com n/2 ciclos de comprimento 2; e n/2 reflexoes sobreeixos unindo vertices opostos que induzem uma permutacao dos vertices com 21-ciclos e (n 2)/2 ciclos de comprimento 2. Em resumo, a permutacao associ-ada a cada reflexao tem n/2 ciclos.Se n e mpar, os eixos de simetria unem um vertice a` face oposta e a permutacaodos vertices respectiva tem um 1-ciclo e (n 1)/2 2-ciclos. Se quisermos juntaros dois casos numa unica expressao, podemos dizer que a permutacao induzida

por cada uma das n reflexoes do polgono tem bn+ 12c ciclos.

O teorema de Frobenius-Burnside diz-nos entao que o numero de maneirasde colorir com m cores os vertices de um polgono regular com n lados e

1

|Dn|

( piDn

|I(pi)|)

=1

2n

d|n

md(n/d) + nmb(n+1)/2c

Mas a aplicacao do mesmo resultado a coloracoes em que vertices adjacentes

recebem cores diferentes e mais complicada: desde logo, se numa permutacaoexistirem vertices adjacentes no mesmo ciclo, nenhuma coloracao com aquelapropriedade fica invariante.Para atacar o problema com metodo, podemos considerar para cada permutacaopi Dn, o grafo cujos vertices sao os ciclos da permutacao e em que ha umaaresta do ciclo Ci para o ciclo Cj se existem vertices u Ci e v Cj adjacentes

24

no polgono. Uma coloracao dos vertices do polgono em que vertices adja-centes recebem cores diferentes e que fica invariante por accao da permutacao,corresponde a uma coloracao dos vertices do grafo em que vertices adjacentesno grafo recebem cores diferentes, e vice-versa. O caso referido no paragrafoanterior diz respeito a permutacoes cujo grafo tem lacetes, e que portanto naoadmite nenhuma coloracao.A contagem das coloracoes de cada um desses grafos pode ser feita usando oraciocnio feito na alnea a).

O resultado final e

1

2n

d|n

(n/d)((m 1)d + (1)d(m 1)) + n2m(m 1)n/2

se n e par, e

1

2n

d|n

(n/d)((m 1)d + (1)d(m 1))

se n e mpar.

42 - Dados k e n fixos, determinar o numero de sequencias X1, , Xk desubconjuntos de [n] que satisfazem

X1 Xk = .

Sugestao: Considerar a matriz k n cuja entrada (i, j) e 1 se j Xi e 0 casocontrario.

Resolucao: Dada uma sequencia nas condicoes do enunciado, podemosinterpretar a matriz definida na sugestao de duas maneiras: por um lado, cadalinha i define o conjunto Xi; mas por outro, cada coluna j define um subconjuntoZj [k] (e o conjunto dos ndices i tais que j Xi). A condicao

X1 Xk =

e equivalente aZj 6= [k], j.

E tal como cada escolha de X1, , Xk determina uma sequencia Z1, , Zn desubconjuntos proprios de [k], e obvio que cada sequencia destas determina umasucessao X1, , Xk de subconjuntos de [n] que satisfazem

X1 Xk = .

Existe portanto uma bijeccao entre estes tipos de sucessoes de conjuntos. Masexistem (2k1)n sucessoes Z1, , Zn de subconjuntos proprios de [k], uma vez

25

que podemos escolher cada Zj independentemente dos outros e a unica restricaoe que Zj 6= [k].

Observacao: Um problema mais complicado, que se deixa como desafio,consiste contar nao as sequencias X1, , Xk, mas os conjuntos {X1, , Xk}satisfazendo as mesmas condicoes.

.

26