Relações de Recorrência e Probabilidade

Matematica Discreta DAMCTB01917SA 2a Lista de exercıcios Universidade Federal do ABC Centro de Matematica Computacao e Cognicao Mituhiro Fukuda 1o quadrimestre de 2024 Entrega 29 de abril de 2024 das 10001200 sala S2140 1 Qual a forma geral da solucao cuja existˆencia e garantida pelos Teoremas 56 e 57 da relacao de recorrˆencia nao homogˆenea linear an 6an1 12an2 8an3 n32n 2 Suponha que haja inicialmente um casal de um bode e uma cabra em uma ilha Iremos assumir por aproximacao que o numero de animais dobra todo ano por reproducao natural e alem disso alguns animais sao trazidos ou removidos ao longo do ano a Construa uma relacao de recorrˆencia para o numero de cabrasbodes na ilha no inıcio do nesimo ano assumindo que durante cada ano 70 animais sao adicionados a ilha b Resolva a relacao de recorrˆencia acima para encontrar o numero de cabrasbodes na ilha do inıcio do nesimo ano c Construa uma relacao de recorrˆencia para o numero de cabrasbodes na ilha no inıcio do nesimo ano assumindo que durante cada ano 2n3 animais sao retirados durante o nesimo ano para todo n 3 3 Utilize uma funcao geradora e o site abaixo por exemplo para encontrar o numero de modos diferentes para o valor de R47 reais utilizando notas de R1 R2 R5 R10 R20 e R25 Quando limitamos o numero de notas de R5 para no maximo 3 notas qual seria o numero de modos diferentes httpswwwsymbolabcomsolverexpandcalculato Escolha algebra na opcao a esquerda e ex pand 4 Liste todos os pares ordenados das relacoes de equivalˆencia que definiem as particoes do conjunto a b c d e f g a a c b e d f g b a b c d e f g 5 Uma particao P1 e denominada um refinamento da particao P2 se todo conjunto em P1 for um subcon junto de um dos conjuntos em P2 Sejam s e t uma sequˆencia de bits e s t Rn se e somente se s e t tiverem pelo menos n primeiros caracteres que coincidam Argumente demonstre que a particao do conjunto de todas as sequˆencias de bits formada pelas classes de equivalˆencia de sequˆencias de bits rel ativa a relacao de equivalˆencia R5 e um refinamrento da particao formada pelas classes de equivalˆencia de sequˆencias de bits relativas a relacao de equivalˆencia R3 6 Desenhe o diagrama de Hasse para o divisibilidade dos seguintes conjuntos Dois numeros a e b pertencentes a um conjunto A e divisıvel se o resto da divisao de a por b e zero a 1 2 3 4 5 6 b 3 5 7 11 13 16 17 c 2 3 5 10 11 15 25 d 1 3 9 27 81 243 6 Matemática Discreta 1 A relação de recorrência homogênea associada a an é an 6 an1 12 an2 8 an3 A equação característica desta relação é r³ 6 r² 12 r 8 0 Produto notável x y³ x³ 3x²y 3x y² y³ r 2³ 0 Logo r 2 é raiz da equação característica com multiplicidade de 3 Assim temos pelo Teorema 54 que ahn α₀ α₁ n α₂ n² 2n Agora iremos encontrar uma solução particular Como Fn n³ 2n e 2 não é raiz da equação característica a solução particular é p₃ n³ p₂ n² p₁ n p₀ 2n Os valores de pi podem ser obtidos por recorrência Observe que a₀ p₀ a₁ 2 p₃ p₂ p₁ p₀ a₂ 4 8 p₃ 4 p₂ 2 p₁ p₀ a₃ 8 27 p₃ 9 p₂ 3 p₁ p₀ a₄ 16 64 p₃ 16 p₂ 4 p₁ p₀ a₅ 32 125 p₃ 25 p₂ 5 p₁ p₀ a₆ 64 216 p₃ 36 p₂ 6 p₁ p₀ Mas também temos que a₃ 6 a₂ 12a₁ 8 a₀ 3³ 2³ 216 p₃ 120 p₂ 72 p₁ 56 p₀ 216 a₄ 6 a₃ 12 a₂ 8 a₁ 4³ 2⁴ 1696 p₃ 640 p₂256 p₁ 112 p₀ 1024 a₅ 6 a₄ 12 a₃ 8 a₁ 5³ 2⁵ 8992 p₃ 2528 p₂ 736 p₁ 224 p₀ 4000 a₆ 6 a₅ 12 a₄ 8 a₃ 6³ 2⁶ 38016 p₃ 8448 p₂ 1920 p₁ 448 p₀ 13824 Igualando as equações obtemos um sistema 4 x 4 432 p₃ 197 p₂ 96 p₁ 64 p₀ 216 2720 p₃ 896 p₂ 320 p₁ 128 p₀ 1024 12932 p₃ 3328 p₂ 896 p₁ 256 p₀ 4000 51840 p₃ 10752 p₂ 2304 p₁ 512 p₀ 13824 Cuja solução é p₃ 51388 p₂ 4897 p₁ 151194 p₀ 3151552 A solução geral é an ahn apn 2 a No início do primeiro ano temos duas cabrasbodes logo a₁ 2 Além disso o número de animais dobra por reprodução natural em um ano e 70 animais são adicionados Logo a₁ 2 an 2 an1 70 n 2 b Observe que a₁ 2 a₂ 2 a₁ 70 a₃ 2 a₂ 70 2 2 a₁ 70 70 2² a₁ 3 70 a₄ 2 a₃ 70 2 2² a₁ 3 70 70 2³ a₁ 7 70 p Hipótese de indução recorrência Assim segue por indução que an 2n1 a₁ 2n1 1 70 e como a₁ 2 temos an 2n 2n1 1 70 c an 2 an1 23 n 2 an1 23 n 1n Primeiro vamos calcular a solução da sequência homogênea associada an 2 an1 A equação característica é r 2 0 logo 2 é raiz com multiplicidade 1 Como 1 não é raiz da equação característica temos ahn α₁ n α₀ 2n Visto que a₁ 2 e a₂ 4 temos 2 α₁ 2 α₀ 2 α₁ 0 e α₀ 1 8 α₁ 4 α₀ 4 Para calcular a solução particular observe que Fn 23 n 1n logo apn p₁ n p₀ 1n Assim p₁ p₀ 2 p₁ 2 e p₀ 0 2 p₁ p₀ 4 Portanto an 2 n 2n 3 O número de modos diferentes para o valor de R 4700 com as notas descritas é a quantidade de formas de obter 47 somando 1 2 5 10 20 e 25 Este número será o coeficiente de x47 para o polinômio 1 x x² x471 x² x4 x461 x5 x10 x451 x10 x401 x20 x401 x25 Este número é 4236 Se limitarmos o número de notas de R 500 para no máximo 3 o resultado será o coeficiente de x47 para o polinômio 1 x x471 x² x461 x5 x10 x151 x10 x401 x20 x401 x25 x5n com 0 n 3 Este número é 339 4 a a c a a a c c a c c b e b e e b b b e e d f g d d f f g g d f f d d g g d f g g f b a b c d a a b b c c d d a b b a a c c a a d d a b c c b b d d b c d d c e f e f f e e e f f g g g 5 Seja S uma sequência de bits qualquer Considere a classe de equivalência S5 de R5 Temos que se t S5 então os 5 primeiros bits de t coincidem com os 5 primeiros bits de S Em particular os 3 primeiros dígitos de t coincidem com os três primeiros dígitos de S logo t S3 Assim temos que S5 S3 ou seja a partição relativa a R5 é um refinamento da partição relativa a R3 6 a 4 6 1 2 3 5 1 1 b 3 5 7 11 13 16 17 os números são primos entre si c 10 25 15 2 5 3 11 d 243 81 27 9 3 1