Slide - Funções Geradoras - 2022-1

Fun¸c˜oes geradoras Jeroen van de Graaf DCC - UFMG 2022/01 Exemplo Vimos como a manipulac¢ao algébrica pode nos ajudar a contar determinadas coisas. Exemplo: contar o numero de combinac6es: (x+y = (xty)(x+y)(«+y) = (x + xy + yx + yy)(x + y) = XXX “Pb XXY bP XYX Pp XYY bh YXX Pb YXY + YYX + yy = (xx) + Dory + xyx + yror) + (xyy + yxy + yyx) + (yyy) = x°43x*y + 3xy?4+y? _ 3\ 3 3\ 2 3\ 2 3\ 3 = (3) «(Jere G)o + 3 y Redescobrindo o coeficiente binomial Determine quantas combina¢des de tamanho 3 podem ser formadas das letras A, B, C, ..., H escolhendo 0 ou 1 de cada letra. Redescobrindo o coeficiente binomial Determine quantas combina¢des de tamanho 3 podem ser formadas das letras A, B, C, ..., H escolhendo 0 ou 1 de cada letra. Isso pode ser calculado multiplicando (1+A)(1+ B)(14+ C)---(1+H), contando os termos de grau 3. Redescobrindo o coeficiente binomial Determine quantas combina¢des de tamanho 3 podem ser formadas das letras A, B, C, ..., H escolhendo 0 ou 1 de cada letra. Isso pode ser calculado multiplicando (14+ A)(1+ B)(1+ C)---(1+H), contando os termos de grau 3. Substituindo A, B, C,...H por X, 0 coeficiente de X? no produto 8 (L+X)(1+X)(1+X)---(1+X)=(1+ XP = SO (7) 0<k<8 nos dard a resposta, sendo 8 3 Redescobrindo o coeficiente binomial Determine quantas combina¢des de tamanho 3 podem ser formadas das letras A, B, C, ..., H escolhendo 0 ou 1 de cada letra. Isso pode ser calculado multiplicando (14+ A)(1+ B)(1+ C)---(1+H), contando os termos de grau 3. Substituindo A, B, C,...H por X, 0 coeficiente de X? no produto 8 (L+X)(1+X)(1+X)---(1+X)=(1+ XP = SO (7) 0<k<8 nos dard a resposta, sendo 8 3 Generalizando para um n qualquer, obtemos o coeficiente binomial (2): que diz quantos subconjuntos de tamanho k existem. Resolver problemas de contagem Determine quantas combina¸c˜oes de tamanho 3 podem ser formadas das letras A, B, C com no m´aximo 1 A, no m´aximo 2 Bs, e no m´aximo 3 Cs. ABB, ABC, ACC, BBC, BCC, CCC Isso pode ser calculado tamb´em multiplicando (1 + A)(1 + B + B2)(1 + C + C 2 + C 3), contando os termos de grau 3. (Por exemplo, B2C = BBC, etc) Substituindo A, B, C por X, o coeficiente de X 3 no produto (1 + X)(1 + X + X 2)(1 + X + X 2 + X 3) nos dar´a a resposta. Resolver problemas de contagem Determine quantas combina¸c˜oes de tamanho 3 podem ser formadas das letras A, B, C com no m´aximo 1 A, no m´aximo 2 Bs, e no m´aximo 3 Cs. ABB, ABC, ACC, BBC, BCC, CCC Isso pode ser calculado tamb´em multiplicando (1 + A)(1 + B + B2)(1 + C + C 2 + C 3), contando os termos de grau 3. (Por exemplo, B2C = BBC, etc) Substituindo A, B, C por X, o coeficiente de X 3 no produto (1 + X)(1 + X + X 2)(1 + X + X 2 + X 3) nos dar´a a resposta. Resolver problemas de contagem Determine quantas combina¸c˜oes de tamanho 3 podem ser formadas das letras A, B, C com no m´aximo 1 A, no m´aximo 2 Bs, e no m´aximo 3 Cs. ABB, ABC, ACC, BBC, BCC, CCC Isso pode ser calculado tamb´em multiplicando (1 + A)(1 + B + B2)(1 + C + C 2 + C 3), contando os termos de grau 3. (Por exemplo, B2C = BBC, etc) Substituindo A, B, C por X, o coeficiente de X 3 no produto (1 + X)(1 + X + X 2)(1 + X + X 2 + X 3) nos dar´a a resposta. Resolver problemas de contagem Determine quantas combina¸c˜oes de tamanho 3 podem ser formadas das letras A, B, C com no m´aximo 1 A, no m´aximo 2 Bs, e no m´aximo 3 Cs. ABB, ABC, ACC, BBC, BCC, CCC Isso pode ser calculado tamb´em multiplicando (1 + A)(1 + B + B2)(1 + C + C 2 + C 3), contando os termos de grau 3. (Por exemplo, B2C = BBC, etc) Substituindo A, B, C por X, o coeficiente de X 3 no produto (1 + X)(1 + X + X 2)(1 + X + X 2 + X 3) nos dar´a a resposta. Multiplica¸c˜ao manual de polinˆomios A multiplica¸c˜ao de polinˆomios pode ser calculada igual a multiplica¸c˜ao de dois inteiros, mas sem o vai-um. Exemplo: (1 + X) · (1 + X + X 2) d´a X 3 X 2 X 1 X 0 1 1 1 1 1 1 1 X 1 2 2 1 produto Exemplo: (1 + 2X + 2X 2 + X 3) · (1 + X + X 2 + X 3) d´a X 6 X 5 X 4 X 3 X 2 X 1 X 0 1 2 2 1 1 1 2 2 1 X 1 2 2 1 X 2 1 2 2 1 X 3 1 3 5 6 5 3 1 produto Multiplica¸c˜ao manual de polinˆomios A multiplica¸c˜ao de polinˆomios pode ser calculada igual a multiplica¸c˜ao de dois inteiros, mas sem o vai-um. Exemplo: (1 + X) · (1 + X + X 2) d´a X 3 X 2 X 1 X 0 1 1 1 1 1 1 1 X 1 2 2 1 produto Exemplo: (1 + 2X + 2X 2 + X 3) · (1 + X + X 2 + X 3) d´a X 6 X 5 X 4 X 3 X 2 X 1 X 0 1 2 2 1 1 1 2 2 1 X 1 2 2 1 X 2 1 2 2 1 X 3 1 3 5 6 5 3 1 produto Multiplica¸c˜ao manual de polinˆomios Atalho: somente calcule as potˆencias que vc precisa: (1 + X) (1 + X + X 2) (1 + X + X 2 + X 3) 1 1 X 3 1 X X 2 1 X 2 X X 1 X 2 X X X X X 2 1 Para c´alculos maiores podemos usar uma ferramenta, por ex. Maple, Matlab, IPython ou Wolfram Alpha. Para GRANDES c´alculos temos que trabalhar mais para encontrar a solu¸c˜ao. Multiplica¸c˜ao manual de polinˆomios Atalho: somente calcule as potˆencias que vc precisa: (1 + X) (1 + X + X 2) (1 + X + X 2 + X 3) 1 1 X 3 1 X X 2 1 X 2 X X 1 X 2 X X X X X 2 1 Para c´alculos maiores podemos usar uma ferramenta, por ex. Maple, Matlab, IPython ou Wolfram Alpha. Para GRANDES c´alculos temos que trabalhar mais para encontrar a solu¸c˜ao. Multiplica¸c˜ao manual de polinˆomios Atalho: somente calcule as potˆencias que vc precisa: (1 + X) (1 + X + X 2) (1 + X + X 2 + X 3) 1 1 X 3 1 X X 2 1 X 2 X X 1 X 2 X X X X X 2 1 Para c´alculos maiores podemos usar uma ferramenta, por ex. Maple, Matlab, IPython ou Wolfram Alpha. Para GRANDES c´alculos temos que trabalhar mais para encontrar a solu¸c˜ao. Resolver problemas de contagem Pergunta: Encontre o n´umero de solu¸c˜oes de x1 + x2 + x3 = 17 com 2 ≤ x1 ≤ 5, 3 ≤ x2 ≤ 6 e 4 ≤ x3 ≤ 7. Resposta: O n´umero de solu¸c˜oes ´e o coeficiente de x17 na expans˜ao de (x2 + x3 + x4 + x5)(x3 + x4 + x5 + x6)(x4 + x5 + x6 + x7) A resposta ´e 3, correspondendo `a soma de x4x6x7, x5x5x7 e x5x6x6. Resolver problemas de contagem Pergunta: Encontre o n´umero de solu¸c˜oes de x1 + x2 + x3 = 17 com 2 ≤ x1 ≤ 5, 3 ≤ x2 ≤ 6 e 4 ≤ x3 ≤ 7. Resposta: O n´umero de solu¸c˜oes ´e o coeficiente de x17 na expans˜ao de (x2 + x3 + x4 + x5)(x3 + x4 + x5 + x6)(x4 + x5 + x6 + x7) A resposta ´e 3, correspondendo `a soma de x4x6x7, x5x5x7 e x5x6x6. Resolver problemas de contagem Exemplo 7.4.11 Pergunta: De quantas maneiras diferentes oito biscoitos idˆenticos podem ser distribu´ıdos entre trˆes crian¸cas se cada crian¸ca tem no m´ınimo dois e no m´aximo quatro biscoitos? Resposta: O n´umero de maneiras ´e o coeficiente de x8 na expans˜ao de (x2 + x3 + x4)3 A resposta ´e 6, correspondendo `a soma de x2x2x4, x2x3x3, x2x4x2, x3x2x3, x3x3x2, x4x2x2. Formas de pagar com moedas Exemplo (livro Daniel Marcus) As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar 50 cents? Considere (1 + Q + Q2)(1 + D + D2 + D3 + D4 + D5)(1 + N + N2 + . . . + N10) Podemos substituir Q → X 25, D → X 10, N → X 5 e procurar o coeficiente de X 50 Formas de pagar com moedas Exemplo (livro Daniel Marcus) As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar 50 cents? Considere (1 + Q + Q2)(1 + D + D2 + D3 + D4 + D5)(1 + N + N2 + . . . + N10) Podemos substituir Q → X 25, D → X 10, N → X 5 e procurar o coeficiente de X 50 Formas de pagar com moedas As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar 50 cents? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10)(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10)(1 + Y + Y 2 + . . . + Y 10) Figura: Formas de pagar com moedas As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar 50 cents? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10)(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10)(1 + Y + Y 2 + . . . + Y 10) Figura: Formas de pagar com moedas As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar 50 cents? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10)(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10)(1 + Y + Y 2 + . . . + Y 10) Figura: Formas de pagar com moedas As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar r cents, para um r qualquer? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10 + · · · )(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10 + · · · )(1 + Y + Y 2 + . . . + Y 10 + · · · ) Formas de pagar com moedas As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar r cents, para um r qualquer? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10 + · · · )(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10 + · · · )(1 + Y + Y 2 + . . . + Y 10 + · · · ) Fun¸c˜ao geradora Exemplo 7.4.4 – Podemos provar que A(x) := 1 + x + x2 + x3 + · · · = 1 (1 − x) j´a que A(x) = 1 + x + x2 + x3 + x4 + . . . xA(x) = x + x2 + x3 + x4 + . . . A(x) − xA(x) = 1 ISSO ´E DOIDO. Podemos representar uma sequˆencia infinita por uma soma, calcular a f´ormula da soma, e a matem´atica continua dando certo!! Fun¸c˜ao geradora Exemplo 7.4.4 – Podemos provar que A(x) := 1 + x + x2 + x3 + · · · = 1 (1 − x) j´a que A(x) = 1 + x + x2 + x3 + x4 + . . . xA(x) = x + x2 + x3 + x4 + . . . A(x) − xA(x) = 1 ISSO ´E DOIDO. Podemos representar uma sequˆencia infinita por uma soma, calcular a f´ormula da soma, e a matem´atica continua dando certo!! Fun¸c˜ao geradora Exemplo 7.4.4 – Podemos provar que A(x) := 1 + x + x2 + x3 + · · · = 1 (1 − x) j´a que A(x) = 1 + x + x2 + x3 + x4 + . . . xA(x) = x + x2 + x3 + x4 + . . . A(x) − xA(x) = 1 ISSO ´E DOIDO. Podemos representar uma sequˆencia infinita por uma soma, calcular a f´ormula da soma, e a matem´atica continua dando certo!! Formas de pagar com moedas – voltando As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar r cents, para um r qualquer? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10 + · · · )(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10 + · · · )(1 + Y + Y 2 + . . . + Y 10 + · · · ) equivale 1 (1 − Y 5) 1 (1 − Y 2) 1 (1 − Y ) Formas de pagar com moedas – voltando As moedas americanas s˜ao: Nickle 5 cents Dime 10 cents Quarter 25 cents Existem quantas maneiras de pagar r cents, para um r qualquer? Abordagem mais f´acil: deixe Y representar 5 cents. Agora podemos substituir Q → Y 5, D → Y 2, N → Y e procurar o coeficiente de Y 10: (1 + Y 5 + Y 10 + · · · )(1 + Y 2 + Y 4 + Y 6 + Y 8 + Y 10 + · · · )(1 + Y + Y 2 + . . . + Y 10 + · · · ) equivale 1 (1 − Y 5) 1 (1 − Y 2) 1 (1 − Y ) Funcao geradora Definicao Seja (ax)k>o uma sequéncia de nimeros. A fun¢ao geradora™ asociada a essa sequéncia é a série 2 k A(x) = ao + ax + ax +--+. = > a,x. k>0 onde deve se entender A(x) como uma soma formal. O simbolo x no significa nada, sd serve como marcador para o coeficiente de x“. wai . . . . = . . ko co k O indice da somatoria vai sobre todos os inteiros nado negativos: >), AX" = doy g akX: Funcao geradora Definicao Seja (ax)k>o uma sequéncia de nimeros. A fun¢ao geradora™ asociada a essa sequéncia é a série 2 k A(x) = ao + ax + ax +--+. = a,x. k>0 onde deve se entender A(x) como uma soma formal. O simbolo x no significa nada, sd serve como marcador para o coeficiente de x“. wai . . . . = . . ko co k O indice da somatoria vai sobre todos os inteiros nado negativos: >), AX" = doy g akX: ObservacGes: > Podemos usar uma fun¢do para representar uma sequéncia, finita e infinita > E como um varal para pendurar os termos da sequéncia > Ja que se trata de um objeto formal, ndo estamos precupados com a convergéncia do somatorio. Funcdo geradora Exemplo 7.4.1: (%)=1,1,11... @ A(x) =1t let)? t1O4 = Yor =k (ax) = 3,3,3,3... A(x) =343x43x° 43X74 ---= Vy 3x* = (ax) = 1,2,3,4,... © A(x) = 1+ 2x +.3x? +438 + = Dysg (k + Dx* = Gap (ax) = 1,2,4,8,... © A(x) = 1+ 2x + 4x? + 8x9 4 ++ = yay 2kx* Exemplo 7.4.2: (ax) = 1,1,1,1,1,1,0,0,0,... > A(x) =1L4x $x? 4x9 + x4 $2 = Do cpes x" (ax) =1,1,1,...,1,0,0,0,... A(x) =14x4+x74x94...4 x4 7 = Voce 1 x“ eS Sks N Exemplo 7.4.4: (ax) =1,1,1,1,1,... © A(xe)=14x4x°4x34--- Formas de pagar com moedas Exemplo 7.4.12 Pergunta: De quantas maneiras diferentes pode se inserir moedas de 1 , 2 , e 5 euros numa m´aquina para pagar r euros. Considere o caso quando a ordem importa sim, e quando a ordem n˜ao importa. Exemplo: se r = 5, ordem importa sim 1. 5 × 1 : H´a 1 maneira: 1 1 1 1 1 2. 3 × 1 + 2 : H´a 4 maneiras: 1 1 1 2 , 1 1 2 1 , 1 2 1 1 , 2 1 1 1 3. 1 + 2 × 2 : H´a 3 maneiras: 1 2 2 , 2 1 2 , 2 2 1 , 4. 5 : H´a 1 maneira Total: 9 maneiras ordem n˜ao importa 1. 5 × 1 , 2. 3 × 1 + 2 , 3. 1 + 2 × 2 , 4. 5 Total: 4 maneiras Formas de pagar com moedas Exemplo 7.4.12 Pergunta: De quantas maneiras diferentes pode se inserir moedas de 1 , 2 , e 5 euros numa m´aquina para pagar r euros. Considere o caso quando a ordem importa sim, e quando a ordem n˜ao importa. Exemplo: se r = 5, ordem importa sim 1. 5 × 1 : H´a 1 maneira: 1 1 1 1 1 2. 3 × 1 + 2 : H´a 4 maneiras: 1 1 1 2 , 1 1 2 1 , 1 2 1 1 , 2 1 1 1 3. 1 + 2 × 2 : H´a 3 maneiras: 1 2 2 , 2 1 2 , 2 2 1 , 4. 5 : H´a 1 maneira Total: 9 maneiras ordem n˜ao importa 1. 5 × 1 , 2. 3 × 1 + 2 , 3. 1 + 2 × 2 , 4. 5 Total: 4 maneiras Formas de pagar com moedas Exemplo 7.4.12 Pergunta: De quantas maneiras diferentes pode se inserir moedas de 1 , 2 , e 5 euros numa m´aquina para pagar r euros. Considere o caso quando a ordem importa sim, e quando a ordem n˜ao importa. Exemplo: se r = 5, ordem importa sim 1. 5 × 1 : H´a 1 maneira: 1 1 1 1 1 2. 3 × 1 + 2 : H´a 4 maneiras: 1 1 1 2 , 1 1 2 1 , 1 2 1 1 , 2 1 1 1 3. 1 + 2 × 2 : H´a 3 maneiras: 1 2 2 , 2 1 2 , 2 2 1 , 4. 5 : H´a 1 maneira Total: 9 maneiras ordem n˜ao importa 1. 5 × 1 , 2. 3 × 1 + 2 , 3. 1 + 2 × 2 , 4. 5 Total: 4 maneiras Referˆencias complementares No [GKP], os autores calculam o n´umero exato de maneiras de se fazer 1 000 000 de d´olares com moedas de 1 , 5 , 10 , 25 e 50 (???) cents (pg. 313-316, 331-332). O valor ´e 66666793333412666685000001 Livros de referˆencia: ▶ “Concrete Mathematics” de R. Graham, D. Knuth, e O. Patashnik, 2da. edi¸c˜ao, Addison-Wesley, 1994. Em particular, cap´ıtulos 1 e 2. ▶ “Generatingfunctionology”, de Herbert S. Wilf. Dispon´ıvel em https://www.math.upenn.edu/~wilf/DownldGF.html, 1994. Redescobrindo o coeficiente binomial Determine quantas combina¢des de tamanho 3 podem ser formadas das letras A, B, C, ..., H escolhendo 0 ou 1 de cada letra. Isso pode ser calculado multiplicando (14+ A)(1+ B)(1+ C)---(1+H), contando os termos de grau 3. Substituindo A,B, C,...H por X, 0 coeficiente de X?° no produto (1 4 xy _ S> 8 xk k O<k<8 nos dard a resposta. Generalizando para um n qualquer, obtemos o coeficiente binomial (2), que diz quantos subconjuntos de tamanho k existem.