Faculdade de Ciências da Universidade do Porto Folha 3
Departamento de Matemática 28.9.2023
Christian Lomp
Exercı́cios de Algoritmos e matemática discreta (M2007)
1. Conjuntos e Funções
(1.13) Uma ordem total (ou linear) de um conjunto A é uma relação R que é reflexiva, anti-
simétrica e transitiva, tal que para quaisquer a, b ∈ A se tem (a, b) ∈ R ou (b, a) ∈ R.
Denota-se (a, b) ∈ R por a ≤ b.
(a) Mostre que para qualquer conjunto finito existe uma ordem total.
(b) Quantas ordens totais tem um conjunto finito?
(1.14) Considere a palavra w = EXERCICIO (ignorando o acento). Um rearranjo da palavra
w é uma palavra do mesmo comprimento que é formada pelas mesmas letras e com a
mesma frequência das mesmas em w, ou seja palavras de comprimento |w| = 9 que são
formadas por duas letras ’E’, duas letras ’C’, duas letras ’I’, e uma letra ’X’,’R’,’O’.
Quantos rearranjos da palavra EXERCICIO existem?
(1.15) Quantos rearranjos da palavra M ISSISSIP P I existem?
(1.16) Doze crianças brincam no recreio de uma escola.
(a) As crianças dividiram-se em grupos de quatro (polı́cias, ladrões e matemáticos). De
quantas formas o poderiam ter feito?
(b) No dia seguinte, as crianças irão dividir-se em três gangues rivais de matemáticos,
com quatro elementos cada um. De quantas formas o poderão fazer?
(1.17) Qual é a probabilidade de obter três pares (distintos) numa mão de póquer com seis
cartas? E contendo pelo menos uma figura (A,K,Q,J)?
(1.18) Duas equipas A e B jogam um torneio de basquet. Em cada jogo, ou A ou B ganha (não
há empates). O torneio termina se uma equipa ganha duas vezes seguidas ou ganha três
jogos. De quantas formas pode decorrer o torneio?
(1.19) Quantas palavras com quatro letras podemos formar usando as letras da palavra BUBBLE
se cada letra B,U,L,E é usada não mais vezes do que a sua occurência em BUBBLE.
(1.20) As partes Ai de uma partição {A1 , . . . , Ak } de um conjunto A chamam-se blocos. Qual é
o número de partições de A = {a, b, c, d} tais que a e b pertencem ao mesmo bloco?
(1.21) Seja A = {a, b, c, d, e}. Denota-se por Wa,b (respetivamente Wa,c ) o conjunto das partições
de A tal que a e b (respetivamente a e c) pertencem ao mesmo bloco. Determine |Wa,b ∩
Wa,c | e |Wa,b ∪ Wa,c |.
(1.22) Mostre que S(n, n − 1) = n2 , para n ≥ 2.
(1.23) Quantas partições com exactamente 10 partes não vazias de um conjunto com 12 elemen-
tos existem?
n
(1.24) Seja n ≥ 5. Mostre que S(n, n − 2) = n3 + 21 2,2,n−4 1
= 24 n(n − 1)(n − 2)(3n − 5).
(1.25) Seja p ≥ 5 um número primo. Mostre que p | S(p, p − 2).