P2_12.1_Gabarito

Prévia do material em texto

UFSC - CTC - INE5403 - Fundams. de Mat. Discreta para a Computac¸a˜o - Sem. 12.1 - 04/jun/2012 - Prof. Daniel S. Freitas - T. 01208A
Segunda prova
1. (2 pontos) Marque V ou F:
(F) E´ preciso selecionar no mı´nimo 4 nu´meros do conjunto {1, 3, 5, 7, 9, 11, 13, 15} para garantir que pelo menos um par destes nu´meros
selecionados fornec¸a uma soma igual a 16.
Resp.: F. E´ preciso selecionar pelo menos 5 destes nu´meros para ter esta garantia
(V) A relac¸a˜o de recorreˆncia cn = −2.cn−1, com c1 = 1, pode ser resolvida pelo me´todo das equac¸o˜es caracter´ısticas.
Resp.: V, pois trata-se de uma relac¸a˜o de recorreˆncia homogeˆnea linear de ordem 1
(V) Se R e´ uma relac¸a˜o de equivaleˆncia, enta˜o R−1 e´ uma relac¸a˜o reflexiva e sime´trica.
Resp.: V, pois se R e´ de equivaleˆncia, R e´ reflexiva, sime´trica e transitiva. Da´ı, a inversa de toda relac¸a˜o reflexiva tambe´m e´ reflexiva
(F) A partir do Teorema Binomial, temos que
∑n
i=1
(n
i
)
= (n− i)!
Resp.: F, o teorema (ver formula´rio) indica que e´ 2n−1
(V) Se uma relac¸a˜o R sobre um conjunto A e´ transitiva, enta˜o sempre devera´ ocorrer R3 ⊆ R
Resp.: V, vimos em aula que, se R sobre A e´ transitiva, enta˜o, ∀n ∈ Z+ Rn ⊆ R
(F) Dada uma relac¸a˜o R sobre um conjunto A, temos que R∞ e´ transitiva se, e somente se, R e´ transitiva.
Resp.: F, pois, independente de R, temos que R∞ sempre e´ transitiva
(V) Sejam f(n) e g(n) func¸o˜es cujos domı´nios sa˜o subconjuntos de Z+ e assuma que f(n) = 128× n5 e g(n) = 127× n5. Enta˜o e´ correto
dizer que f e´ O(g).
Resp.: V, pois |f(n)| ≤ c.|g(n)|, para, por exemplo, c = 2 e n ≥ 1
(F) Para calcular a quantidade de maneiras diferentes de atribuir 5 tarefas a 4 alunos, de maneira que cada aluno receba pelo menos uma
tarefa, e de maneira que nenhuma tarefa seja atribu´ıda a mais do que um aluno, e´ necessa´rio utilizar o Princ´ıpio do Pombal Estendido
Resp.: F. Este e´ um problema de “ca´lculo de quantidade de func¸o˜es sobrejetoras”, o qual e´ resolvido pelo Princ´ıpio da Inclusa˜o-Exclusa˜o
generalizado
2. (1 ponto) Considere as seguintes relac¸o˜es sobre o conjunto A = {1, 2, 3} :
R = {(2, 1), (3, 1), (3, 3)}, S = {(1, 1), (2, 2)}, T = {(1, 2), (1, 3)} e U = {(2, 3), (3, 2)}
e as seguintes afirmativas:
I. Somente S e´ reflexiva.
II. Somente U na˜o e´ transitiva.
III. Somente U e´ sime´trica.
IV. Nenhuma delas e´ antissime´trica.
V. R ∪ S e´ reflexiva, antissime´trica e transitiva.
VI. S ∪ U na˜o e´ reflexiva, mas e´ transitiva e sime´trica.
VII. R ∪ S ∪ T e´ reflexiva e sime´trica, mas na˜o e´ transitiva.
A ana´lise permite concluir que sa˜o VERDADEIRAS:
Resposta: somente as afirmativas II, V e VII.
Justificativa:
• Para comec¸ar, a relac¸a˜o S na˜o e´ reflexiva (falta o par (3, 3)), de modo que as respostas que inclu´ıssem a alternativa I poderiam ser
eliminadas
– com isto, treˆs alternativas das seis eram imediatamente eliminadas (“b”, “d” e “f”)
• em seguida, constata-se que a alternativa III tambe´m e´ falsa, pois S tambe´m e´ sime´trica
– com isto, a alternativa “c” tambe´m era eliminada
• finalmente, observa-se que a alternativa VII e´ verdadeira (ver logo abaixo)
• com estas 3 observac¸o˜es, chegava-se a` conclusa˜o de que a u´nica alternativa correta seria: “somente as afirmativas II, V e VII sa˜o
verdadeiras”
• Uma outra possibilidade seria verificar diretamente que:
– a afirmativa II e´ verdadeira pois:
∗ U na˜o e´ mesmo transitiva (faltam os pares (2, 2) e (3, 3))
∗ no caso da relac¸a˜o R, a u´nica possibilidade de verificac¸a˜o da transitividade envolve os pares (3, 3) e (3, 1), o que leva ao
pro´prio par (3, 1), de modo que R e´ transitiva
∗ no caso de S e T , temos a situac¸a˜o em que na˜o e´ poss´ıvel provar que a relac¸a˜o na˜o e´ transitiva, de modo que, por definic¸a˜o,
elas sa˜o transitivas
– a afirmativa V e´ verdadeira pois:
∗ R ∪ S = {(2, 1), (3, 1), (3, 3), (1, 1), (2, 2)}
∗ R ∪ S e´ reflexiva, pois (1, 1) ∈ R ∪ S, (2, 2) ∈ R ∪ S e (3, 3) ∈ R ∪ S, de modo que ∀a ∈ {1, 2, 3}, temos que (a, a) ∈ R ∪ S
∗ R∪S e´ antissime´trica, pois os u´nicos pares (a, b) ∈ R∪S tais que a 6= b sa˜o (2, 1) e (3, 1) e os pares (1, 2) e (1, 3) na˜o fazem
parte de R ∪ S, de modo que ∀a, b ∈ {1, 2, 3}, tais que a 6= b, temos que (a, b) ∈ R ∪ S ⇒ (b, a) /∈ R ∪ S
∗ R ∪ S e´ transitiva, pois as u´nicas possibilidades de verificac¸a˜o da transitividade envolvem as duplas de pares (2, 2) e (2, 1),
(2, 1) e (1, 1), (3, 3) e (3, 1), (3, 1) e (1, 1), o que leva aos pro´prios pares (2, 1) e (3, 1), de modo que, ∀a, b, c ∈ R ∪ S, temos
que ((a, b) ∈ R ∪ S ∧ (b, c) ∈ R ∪ S)⇒ (a, c) ∈ R ∪ S
– para completar, nota-se que a afirmativa VII e´ verdadeira pois:
∗ R ∪ S ∪ T = {(2, 1), (3, 1), (3, 3), (1, 1), (2, 2), (1, 2), (1, 3)}
∗ R ∪ S ∪ T e´ reflexiva, pois (1, 1) ∈ R ∪ S ∪ T , (2, 2) ∈ R ∪ S ∪ T e (3, 3) ∈ R ∪ S ∪ T , de modo que ∀a ∈ {1, 2, 3}, temos
que (a, a) ∈ R ∪ S ∪ T
∗ R ∪ S ∪ T e´ sime´trica, pois ∀(a, b) ∈ R ∪ S ∪ T , vemos que (a, b) ∈ R ∪ S ∪ T e (b, a) ∈ R ∪ S ∪ T
∗ mas R ∪ S ∪ T na˜o e´ transitiva, pois (3, 1) ∈ R ∪ S ∪ T e (1, 2) ∈ R ∪ S ∪ T , mas (3, 2) /∈ R ∪ S ∪ T
1
3. (1 ponto) Quantos inteiros positivos de treˆs algarismos, todos diferentes de zero, teˆm pelo menos dois algarismos iguais?
Resposta: 225
Justificativa:
• Ha´ 9× 9× 9 = 729 inteiros positivos de treˆs algarismos na˜o nulos.
• Destes, exatamente 9× 8× 7 = 504 possuem os treˆs algarismos distintos.
• Portanto, ha´ 729− 504 = 225 inteiros positivos, com todos os algarismos diferentes de zero, com pelo menos dois algarismos iguais. �
4. (1 ponto) Quantas permutac¸o˜es de 10 d´ıgitos decimais (0, 1, 2, . . . , 9) comec¸am com os 3 d´ıgitos 765 ou conteˆm os d´ıgitos 89 na quinta e na
sexta posic¸o˜es ou terminam com os 3 d´ıgitos 321? (Dica: note, por exemplo, que algumas das que comec¸am com 765 terminam com 321.)
Resposta: 50138 = 7! + 8! + 7!− 5!− 4!− 5! + 2! permutac¸o˜es
Justificativa:
• Sejam:
A = conjunto das permutac¸o˜es com 10 d´ıgitos decimais que comec¸am com 765
B = conjunto das permutac¸o˜es com 10 d´ıgitos decimais que conteˆm os d´ıgitos 89 na quinta e na sexta posic¸o˜es
C = conjunto das permutac¸o˜es com 10 d´ıgitos decimais que terminam com 321
• o que esta´ sendo pedido e´: |A ∪B ∪ C|
• ora, visto que existem intersecc¸o˜es entre estes 3 conjuntos (por exemplo, algumas permutac¸o˜es que comec¸am com 765 tambe´m terminam
com 321), fica evidente que e´ preciso utilizar o princ´ıpio da inclusa˜o-exclusa˜o, o qual no caso da unia˜o de 3 conjuntos, e´ dado por (ver
formula´rio):
|A ∪B ∪ C| = |A|+ |B|+ |C| − |A ∩B| − |A ∩ C| − |B ∩ C|+ |A ∩B ∩ C|
• enta˜o e´ necessa´rio calcular individualmente cada uma das parcelas:
* |A| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que comec¸am com 765:
∗ as 3 primeiras posic¸o˜es esta˜o fixas, de modo que apenas as 7 u´ltimas podem ser permutadas
∗ o que pode ser feito de: 7! maneiras diferentes
* |B| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que conteˆm os d´ıgitos 89 na quinta e na sexta posic¸o˜es
∗ a quinta e a sexta posic¸o˜es esta˜o fixas, de modo que apenas as outras 8 podem ser permutadas
∗ o que pode ser feito de: 8! maneiras diferentes
* |C| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que terminam com 321:
∗ as 3 u´ltimas posic¸o˜es esta˜o fixas, de modo que apenas as 7 primeiras podem ser permutadas
∗ o que pode ser feito de: 7! maneiras diferentes
* |A∩B| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que comec¸am com 765 E conteˆm os d´ıgitos 89 na quinta e na sexta
posic¸o˜es:
∗ as posic¸o˜es 1, 2, 3, 5 e 6 esta˜o fixas, de modo que apenas as outras 5 podem ser permutadas
∗ o que pode ser feito de: 5! maneiras diferentes
* |A ∩ C| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que comec¸am com 765 E terminam com 321:
∗ as 3 primeiras e as 3 u´ltimas posic¸o˜es esta˜o fixas, de modo que apenas as outras 4 podem ser permutadas
∗ o que pode ser feito de: 4! maneiras diferentes
* |B∩C| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que conteˆm os d´ıgitos 89 na quinta ena sexta posic¸o˜es E terminam
com 321:
∗ as posic¸o˜es 5, 6, 8, 9 e 10 esta˜o fixas, de modo que apenas as outras 5 podem ser permutadas
∗ o que pode ser feito de: 5! maneiras diferentes
* |A ∩B ∩ C| = quantidade de permutac¸o˜es com 10 d´ıgitos decimais que comec¸am com 765 E conteˆm os d´ıgitos 89 na quinta e na
sexta posic¸o˜es E terminam com 321:
∗ as posic¸o˜es 1, 2, 3, 5, 6, 8, 9 e 10 esta˜o fixas, de modo que apenas as outras 2 podem ser permutadas
∗ o que pode ser feito de: 2! maneiras diferentes
• juntando tudo, temos que: |A ∪B ∪ C| = 7! + 8! + 7!− 5!− 4!− 5! + 2! = 50138 �
5. (1 ponto) O nu´mero de strings de bits de comprimento 10 que conteˆm no ma´ximo treˆs 1’s e´ dado por:
Resposta: 176
Justificativa:
• Sejam:
A = conjunto de strings bina´rias de comprimento 10 que na˜o conteˆm 1’s
B = conjunto de strings bina´rias de comprimento 10 que conteˆm exatamente um 1
C = conjunto de strings bina´rias de comprimento 10 que conteˆm exatamente dois 1’s
D = conjunto de strings bina´rias de comprimento 10 que conteˆm exatamente treˆs 1’s
• O que esta´ sendo pedido e´: |A ∪B ∪ C ∪D| = |A|+ |B|+ |C|+ |D| (pois na˜o ha´ intersecc¸o˜es)
• Calculando cada uma das parcelas:
* primeiro, note que, em relac¸a˜o ao posicionamento dos 1’s, trata-se de um problema de combinac¸a˜o, pois qualquer string que
contenha 1’s, por exemplo, nas posic¸o˜es x e y, e´ ideˆntica a uma string que contenha 1’s nas posic¸o˜es y e x
* |A| = quantidade de strings bina´rias de comprimento 10 que na˜o conteˆm 1’s :
∗ entre as 10 posic¸o˜es da string, nenhuma e´ escolhida para se colocar 1
∗ o que pode ser feito de: C(10, 0) maneiras diferentes
∗ para as posic¸o˜es que sobram, existem 110 permutac¸o˜es diferentes
∗ (de fato, neste caso, a u´nica possibilidade e´: 0000000000)
* |B| = quantidade de strings bina´rias de comprimento 10 que conteˆm exatamente um 1 :
∗ entre as 10 posic¸o˜es da string, pode-se escolher qualquer uma para colocar um 1
∗ o que pode ser feito de: C(10, 1) maneiras diferentes
∗ para as posic¸o˜es que sobram, existem 19 permutac¸o˜es diferentes
* |C| = quantidade de strings bina´rias de comprimento 10 que conteˆm exatamente dois 1’s :
∗ entre as 10 posic¸o˜es da string, deve-se escolher quaisquer duas para colocar dois 1’s (a ordem de colocac¸a˜o dos 1’s na˜o
importa)
∗ o que pode ser feito de: C(10, 2) maneiras distintas
∗ para as posic¸o˜es que sobram, existem 18 permutac¸o˜es diferentes
2
* |D| = quantidade de strings bina´rias de comprimento 10 que conteˆm exatamente treˆs 1’s :
∗ entre as 10 posic¸o˜es da string, deve-se escolher treˆs para colocar treˆs 1’s (a ordem de colocac¸a˜o dos 1’s e´ irrelevante)
∗ o que pode ser feito de: C(10, 3) maneiras distintas
∗ para as posic¸o˜es que sobram, existem 17 permutac¸o˜es diferentes
• O que leva a: C(10, 3)× 110 + C(10, 2)× 19 + C(10, 1)× 18 + C(10, 0)× 17 = 120 + 45 + 10 + 1 = 176 strings �
6. (1 ponto) Sabendo que uma certa padaria vende pa˜es temperados, pa˜es com gergelim, pa˜es integrais, pa˜es salgados, pa˜es de centeio, pa˜es
com uvas passas, pa˜es com erva doce e pa˜es comuns, determine quantos modos diferentes existem para escolher uma du´zia de pa˜es com, no
mı´nimo, um de cada tipo:
Resposta: 330
Justificativa:
• Temos 8 opc¸o˜es de pa˜es a escolher e e´ necessa´rio escolher uma du´zia deles
• Claramente, a ordem das escolhas na˜o importa, de modo que se trata de um problema de combinac¸a˜o
• Temos que escolher mais pa˜es do que a quantidade de opc¸o˜es oferecida, de modo que se trata, mais precisamente, de “combinac¸a˜o com
repetic¸a˜o”
• “Pelo menos um pa˜o de cada tipo devera´ ser escolhido”, de modo que temos ja´ decidida a escolha de 8 do total de 12 pa˜es
• Sobra o problema de escolher 4 pa˜es entre as 8 opc¸o˜es, com possibilidade de repetic¸a˜o, para completar uma du´zia, o que pode ser feito
de (ver formula´rio):
C(8 + 4− 1, 4) = C(11, 4) = C(11, 7) maneiras diferentes �
7. (1 ponto) Seja o conjunto A = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), 4, 3), (4, 4)} e seja R a
relac¸a˜o bina´ria sobre A definida por (a, b)R(c, d) se e somente se a× b = c× d. Sabendo que R e´ uma relac¸a˜o de equivaleˆncia, obtenha A/R,
ou seja, compute as classes de equivaleˆncia geradas pela relac¸a˜o em A.
Resp.: os pares (x, y) equivalentes a (a, b) sa˜o aqueles cujo produto x× y e´ igual a a× b
• Ora, existem apenas 9 produtos diferentes, dados por: 1× 1, 1× 2, 1× 3, 1× 4, 2× 3, 2× 4, 3× 3, 3× 4 e 4× 4
• Enta˜o as (9) classes de equivaleˆncia sa˜o:
R((1, 1)) = {(1, 1)}
R((1, 2)) = {(1, 2), (2, 1)}
R((1, 3)) = {(1, 3), (3, 1)}
R((1, 4)) = {(1, 4), (2, 2), (4, 1)}
R((2, 3)) = {(2, 3), (3, 2)}
R((2, 4)) = {(2, 4), (4, 2)}
R((3, 3)) = {(3, 3)}
R((3, 4)) = {(3, 4), (4, 3)}
R((4, 4)) = {(4, 4)}
• De modo que A/R e´ dado por:
A/R = {{(1, 1)}, {(1, 2), (2, 1)}, {(1, 3), (3, 1)}, {(1, 4), (2, 2), (4, 1)}, {(2, 3), (3, 2)}, {(2, 4), (4, 2)}, {(3, 3)}, {(3, 4), (4, 3)}, {(4, 4)}}
8. (1 ponto). Seja A = {a1, a2, a3, a4, a5} e seja R uma relac¸a˜o sobre A cuja matriz e´:
MR = W0 =

1 0 0 1 0
0 1 0 0 0
0 0 0 1 1
1 0 0 0 0
0 1 0 0 1

(a) Compute as matrizes W1, W2 e W3 que seriam geradas pelo algoritmo de Warshall neste caso.
Resposta:
• Analisando a matriz W0 acima, vemos que, ale´m das posic¸o˜es ja´ marcadas, seriam marcadas tambe´m as seguintes posic¸o˜es, na
obtenc¸a˜o de W1 pelo algoritmo de Warshall:
– linhas 1 e 4 combinadas com colunas 1 e 4 (a linha e a coluna relevantes esta˜o marcadas em vermelho em W0)
– ou seja: (1, 1), (1, 4), (4, 1), (4, 4) devem ser adicionados (se ja´ na˜o estiverem marcados)
• de modo que a matriz W1 e´ dada por:
W1 =

1 0 0 1 0
0 1 0 0 0
0 0 0 1 1
1 0 0 1 0
0 1 0 0 1

• da mesma forma, notamos que as posic¸o˜es (2, 2), (5, 2) devem ser adicionadas (se ja´ na˜o estiverem marcadas), para passar para
W2 :
W2 =

1 0 0 1 0
0 1 0 0 0
0 0 0 1 1
1 0 0 1 0
0 1 0 0 1
 = W1
• em seguida, observando que a coluna 3 e´ formada apenas de zeros, conclu´ımos que W3 deve ficar igual a W2, ou seja:
W3 =

1 0 0 1 0
0 1 0 0 0
0 0 0 1 1
1 0 0 1 0
0 1 0 0 1
 = W2 �
3
(b) Encontre R∞ para esta relac¸a˜o.
Resposta:
• Pelo algoritmo de Warshall, temos que R∞ = W5 de modo que ainda e´ preciso calcular W4 e W5:
W4 =

1 0 0 1 0
0 1 0 0 0
1 0 0 1 1
1 0 0 1 0
0 1 0 0 1

W5 =

1 0 0 1 0
0 1 0 0 0
1 1 0 1 1
1 0 0 1 0
0 1 0 0 1
 = MR∞
• de modo que R∞ e´ dado por: R∞ = {(1, 1), (1, 4), (2, 2), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 4), (5, 2), (5, 5)} �
9. (1 ponto) Seja A = {0, 1}.
(a) Fornec¸a uma relac¸a˜o de recorreˆncia para cn, o nu´mero de strings de comprimento n em A∗ que na˜o possuem 01. Justifique sua resposta.
(Dica: c1 = 2 e c2 = 3)
Resposta: c1 = 2 e, para n > 1: cn = cn−1 + 1
Justificativa:
• Dada uma string “boa” (sem 01) com tamanho n− 1, pode-se produzir uma string boa de tamanho n de duas formas:
– colocando um 1 na frente da string boa de tamanho n− 1: com certeza, na˜o ha´ risco de se gerar algum 01
– colocando um 0 na frente da string boa de tamanho n− 1: somente no caso de uma string de tamanho n− 1 toda de 0s
• Logo, pelo racioc´ınio anterior, temos que: cn = cn−1 + 1
– caso base: para n = 1, nenhuma das duas strings poss´ıveis (0 e 1) possuem a subsequeˆncia 01 �
(b) Resolva a relac¸a˜o de recorreˆncia que voceˆ encontrou no item anterior.
Resposta: cn = n+ 1
Justificativa:
• por backtracking: cn = cn−1 + 1 = (cn−2 + 1) + 1 = ... = c1 + (n− 1) = 2 + (n− 1) = n+ 1
• confirmando: cn−1 + 1 = ((n− 1) + 1) + 1 = n+ 1 = cn �
4
Formula´rio (definic¸o˜es e fo´rmulas possivelmente u´teis):
• Uma relac¸a˜o bina´ria de um conjunto na˜o vazio A em um B e´ um subconjunto de A×B
• Relac¸a˜o R sobre um conjunto A e´ reflexiva sse: ∀a ∈ A, (a, a) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ sime´trica sse: ∀a, b ∈ A, (a, b) ∈ R→ (b, a) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ assime´trica sse: ∀a, b ∈ A, (a, b) ∈ R→ (b, a) /∈ R
• Relac¸a˜o R sobre um conjuntoA e´ antissime´trica sse: sea 6= b, ∀a, b ∈ A, (a, b) ∈ R→ (b, a) /∈ R
• Relac¸a˜o R sobre um conjunto A e´ transitiva sse: ∀a, b, c ∈ A, (a, b) ∈ R ∧ (b, c) ∈ R→ (a, c) ∈ R
• Relac¸a˜o R sobre um conjunto A e´ uma relac¸a˜o de equivaleˆncia sse R e´ reflexiva, sime´trica e transitiva
• Algoritmo WARSHALL:
FECHO = MR
for k = 1 to n
for i = 1 to n
for j = 1 to n
FECHO[i,j ] = FECHO[i,j ] ∨ (FECHO[i,k ] ∧ FECHO[k,j ])
• Uma func¸a˜o f : A→ B e´ injetora sse ∀a, b ∈ A, a 6= b→ f(a) 6= f(b)
• Uma func¸a˜o f : A→ B e´ sobrejetora sse ∀b ∈ B, ∃a ∈ A tal que f(a) = b
• Uma func¸a˜o f : A→ B e´ bijetora sse for injetora e sobrejetora
• f e´ O(g) se existem constantes c e k tais que: |f(n)| ≤ c · |g(n)|, ∀n ≥ k
• f e´ de ordem mais baixa do que g se f e´ O(g) mas g na˜o e´ O(f)
• Princ´ıpio da Multiplicac¸a˜o: Suponha que duas tarefas devem ser executadas em sequeˆncia. Se ha´ n1 modos de executar a tarefa T1 e se, para
um destes modos, T2 pode ser realizada de n2 maneiras, enta˜o a sequeˆncia T1T2 pode ser realizada de n1 × n2 formas diferentes.
• Se 1 ≤ r ≤ n, enta˜o o nu´mero de arranjos de n objetos tomados r a r e´: P (n, r) = n!
(n−r)!
• Seja A um conjunto com |A| = n e seja 1 ≤ r ≤ n. O nu´mero de sequeˆncias de comprimento r que podem ser formadas com elementos de A,
permitindo repetic¸o˜es, e´ nr
• Seja A um conjunto com |A| = n e 0 ≤ r ≤ n. O nu´mero de combinac¸o˜es dos elementos de A tomados r a r e´ dado por: C(n, r) = n!
r!(n−r)!
• Existem C(n+ r − 1, r) = C(n+ r − 1, n− 1) combinac¸o˜es r a r de um conjunto com n elementos quando a repetic¸a˜o e´ permitida.
• O nro de permutac¸o˜es distintas que podem ser formadas com uma colec¸a˜o de n objetos, aonde o 1o objeto aparece k1 vezes, o 2o objeto
aparece k2 vezes, etc..., e´ dado por:
n!
k1!k2!···kt! , aonde k1 + k2 + · · ·+ kt = n
• Princ´ıpio do pombal: Se n pombos sa˜o acomodados em m cub´ıculos de um pombal, enta˜o um dos cub´ıculos deve conter pelo menos
b(n− 1)/mc+ 1 pombos.
• Teorema Binomial: Sejam x e y varia´veis e n um inteiro na˜o-negativo. Enta˜o: (x+ y)n = ∑nj=0 (nj)xn−jyj
• Identidade de Pascal: (n+1
k
)
=
( n
k−1
)
+
(n
k
)
• Sequeˆncia dos Nu´meros de Catala˜o: C0 = 1, C1 = 1, Cn =
∑n−1
k=0 CkCn−k−1 (para n ≥ 2)
• 1 + a+ a2 + a3 + · · ·+ an−1 = an−1
a−1 1 + 2 + 3 + · · ·+ n =
n(n+1)
2
• Suponha que a equac¸a˜o caracter´ıstica rk − c1.rk−1 − · · · − ck = 0 tem k ra´ızes distintas r1, r2, . . . , rk. Enta˜o uma sequeˆncia {an} e´ uma
soluc¸a˜o da relac¸a˜o de recorreˆncia: an = c1.an−1 + c2.an−2 + · · · + ck.an−k sse an = α1.r1n + α2.r2n + · · · + αk.rkn, aonde α1, α2, . . . , αk
sa˜o constantes.
• Recorreˆncias Dividir-e-Conquistar: f(n) = a.f(n/b) + c e´ O(log n), se a = 1 e O(nlogba), se a > 1 (f crescente e n divis´ıvel por b).
• an pode ser expresso como polinoˆmio sse houver um natural k tal que ∀n ≥ 0, ∆k+1an = 0
Neste caso: an = a0
(n
0
)
+ (∆a0)
(n
1
)
+ (∆2a0)
(n
2
)
+ · · ·+ (∆ka0)
(n
k
)
onde: ∆a e´ a sequeˆncia cujo n-e´simo termo e´: ∆an = an+1 − an
• Princ´ıpio da Inclusa˜o-Exclusa˜o: Sejam A1, A2, . . . , An conjuntos finitos. Enta˜o:
|A1 ∪A2 ∪ · · · ∪An| =
∑
1≤i≤n |Ai| −
∑
1≤i<j≤n |Ai ∩Aj |+
∑
1≤i<j<k≤n |Ai ∩Aj ∩Ak| − · · · + (−1)n+1|A1 ∩A2 ∩ · · · ∩An|
5