Slide - Permutações e Combinações Generalizadas - Matemática Discreta - 2023-2

Permuta¸c˜oes e combina¸c˜oes generalizadas Jeroen van de Graaf DCC - UFMG ; Permuta¸c˜oes e combina¸c˜oes generalizadas § 5.3 de Rosen: 1 Permuta¸c˜oes sem repeti¸c˜ao P(n, r) 2 Combina¸c˜oes sem repeti¸c˜ao C(n, r) § 5.5 de Rosen: 3 Permuta¸c˜oes com repeti¸c˜ao ? 4 Combina¸c˜oes com repeti¸c˜ao ? 5 Permuta¸c˜oes com objetos idˆenticos ? 6 Objetos distintos em caixas distintas ? 7 Objetos idˆenticos em caixas distintas ? 8 Objetos distintos em caixas idˆenticas ? 9 Objetos idˆenticos em caixas idˆenticas ? An´alise Combinat´oria PERMUTAC¸ ˜OES COM REPETIC¸ ˜AO/REPOSIC¸ ˜AO Permuta¸c˜oes sem e com repeti¸c˜ao/reposi¸c˜ao ▶ Numa permuta¸c˜ao-r padr˜ao, a repeti¸c˜ao dos objetos n˜ao ´e permitido. ▶ A f´ormula ´e P(n, r) = n! r! . ▶ Q: Quantas sequˆencias de extens˜ao r podem ser formadas com letras e d´ıgitos, se a repeti¸c˜ao (reposi¸c˜ao) ´e permita? ▶ R: 36r. TEOREMA: A f´ormula para uma permuta¸c˜ao-r com repeti¸c˜ao ´e nr . Permuta¸c˜oes e combina¸c˜oes com repeti¸c˜ao Quantas maneiras h´a de escolher r objetos de n tipos diferentes, se • a ordem dos objetos ´e importante Sim/N˜ao, e • a repeti¸c˜ao de objetos do mesmo tipo ´e permitida Sim/N˜ao. Ordem sim n˜ao sim AB̸= BA, AA OK AB=BA, AA OK permuta¸c˜ao-r com repeti¸c˜ao combina¸c˜ao-r com repeti¸c˜ao nr ??? Repeti¸c˜ao AB̸= BA, AA NOK AB=BA, AA NOK n˜ao permuta¸c˜ao-r combina¸c˜ao-r P(n, r) C(n, r) An´alise Combinat´oria COMBINAC¸ ˜OES COM REPETIC¸ ˜AO/REPOSIC¸ ˜AO Exemplo • (Rosen exemplo 5.5.2) Quantas maneiras existem de escolhar 4 frutas de uma cesta contendo laranjas, ma¸c˜as e pˆeras? • A ordem n˜ao ´e importante. • A repeti¸c˜ao ´e permitida. Exemplo • (Rosen exemplo 5.5.2) Quantas maneiras existem de escolhar 4 frutas de uma cesta contendo laranjas, ma¸c˜as e pˆeras? • A ordem n˜ao ´e importante. • A repeti¸c˜ao ´e permitida. • [L, L, L, L], [M, M, M, M], [P, P, P, P], (com 4) [L, L, L, M], [L, L, L, P], [M, M, M, L], (com 3) [M, M, M, P], [P, P, P, L], [P, P, P, M], [L, L, M, M], [L, L, M, P], [L, L, P, P], (com 2) [M, M, L, P], [M, M, P, P], [P, P, L, M] • Estutura de dados conhecida como um multiset ou bag, a generaliza¸c˜ao de um conjunto onde a repeti¸c˜ao de elementos tem significado. Exemplo • (Rosen exemplo 5.5.3) Numa uma caixa h´a notas de 1, 2, 5, 10, 20, 50 e 100 reais. Quantas quantias pode-se formar com cinco notas? • Podemos tranformar cada poss´ıvel sele¸c˜ao de notas num string: 1 | 2 | 5 | 10 | 20 | 50 | 100 | * | ** | | * | | * • H´a um separador a menos que denomina¸c˜oes, portanto o tamanho da string ´e 7 − 1 + 5. • A correpondˆencia ´e um-a-um, portanto basta responder a seguinte quest˜ao: No alfabeto com s´ımbolos | e *, quantas string de tamanho 11 com 5 s´ımbolos * podemos formar? C(11, 5) • tipos = denomina¸c˜oes; n´umero de possibilidades n = 7 objetos = notas; n´umero de sele¸c˜oes r = 5 C((n − 1) + r, n − 1) Exemplo • (Rosen exemplo 5.5.5) Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 = 11 com x1, x2, x3 ≥ 0 • A solu¸c˜ao x1 = 2, x2 = 4, x3 = 5 pode ser representada como: **|****|***** onde cada * representa uma unidade. • A corresponˆencia ´e um-a-um, portanto basta responder a seguinte quest˜ao: No alfabeto com s´ımbolos | e *, quantas string de tamanho 13 com 11 s´ımbolos * podemos formar? • tipos = x1; x2; x3; n´umero de possibilidades n = 3 objetos = unidades; n´umero de sele¸c˜oes r = 11 C((n − 1) + r, n − 1) = C(13, 2) Teorema: Combina¸c˜ao-r com repeti¸c˜ao Quantas maneiras h´a de escolher r objetos de n tipos diferentes, se • a ordem dos objetos n˜ao ´e importante, e • a repeti¸c˜ao de s´ımbolos do mesmo tipo ´e permitida sim. Resposta: C((n − 1) + r, n − 1) • Observe que, j´a que repeti¸c˜ao ´e permitida, r pode ser maior que n. O n´umero de separadores ´e n − 1 !!! Exemplo • (Rosen exemplo 5.5.2) Quantas maneiras existem de escolhar 4 frutas de uma cesta contendo laranjas, ma¸c˜as e pˆeras? • tipos = tipos de fruta; n´umero de possibilidades n = 3 objetos = frutas; n´umero de sele¸c˜oes r = 4 C(n − 1 + r, r) = C(6, 4) = 6! 4!2! = 6 · 5 2 = 15 Exemplo • (Rosen exemplo 5.5.4) Uma loja vende 4 tipos de biscoitos. Quantas diferentes escolhas de 6 biscoitos tem? • tipos = tipos de biscoito; n´umero de possibilidades n = 4 objetos = biscoitos; n´umero de sele¸c˜oes r = 6 C((n − 1) + r, n − 1) = C(9, 3) • Observe que, j´a que repeti¸c˜ao ´e permitida, r pode ser maior que n. Exemplo • Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 = 11 com x1 ≥ 0; x2 ≥ 1; x3 ≥ 2 • De antem˜ao, atribua uma unidade a x2, e duas unidades a x3. Sobram portanto 11 − 3 = 8 para distribuir entre y1, y2 e y3. • A equa¸c˜ao y1 + y2 + y3 = 8 com y1, y2, y3 ≥ 0 tem C((n − 1) + r, n − 1) = C(11, 3) solu¸c˜oes. Mais formal, aplicamos a transforma¸c˜ao      x1 = y1 x2 = y2 + 1 x3 = y3 + 2 Exemplo • Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 = 11 com x1 ≥ 0; x2 ≥ 1; x3 ≥ 2 • De antem˜ao, atribua uma unidade a x2, e duas unidades a x3. Sobram portanto 11 − 3 = 8 para distribuir entre y1, y2 e y3. • A equa¸c˜ao y1 + y2 + y3 = 8 com y1, y2, y3 ≥ 0 tem C((n − 1) + r, n − 1) = C(11, 3) solu¸c˜oes. Mais formal, aplicamos a transforma¸c˜ao      x1 = y1 x2 = y2 + 1 x3 = y3 + 2 Exemplo • Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 ≤ 11 com x1, x2, x3 ≥ 0 • Introduza uma quarta vari´avel que representa o que falta para chegar a 11. Assim obt´em-se a equa¸c˜ao y1 + y2 + y3 + y4 = 11 com yi ≥ 0 portanto tipos = y1; y2; y3; y4; n´umero de tipos n = 4 objetos = unidades; n´umero de sele¸c˜oes r = 11 C((n − 1) + r, n − 1) = C(14, 3) Objetos idˆenticos em caixas distintas • (Rosen exemplo 5.5.9) Quantas maneiras existem para colocar 10 bolas idˆenticas em 8 caixas distingu´ıveis? • Idˆentico a: Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 . . . x8 = 10 com xi ≥ 0 • tipos = caixas; n´umero de caixas ´e n = 8 objetos = bolas; n´umero de bolas ´e r = 10 C((n − 1) + r, n − 1) = C(17, 7) Objetos idˆenticos em caixas distintas • Quantas maneiras existem para colocar r bolas idˆenticas em n caixas distingu´ıveis? • Idˆentico a: Quantas solu¸c˜oes tem a equa¸c˜ao x1 + x2 + x3 . . . xn = r com xi ≥ 0 • Ou seja, equivalente `a combina¸c˜ao com repeti¸c˜ao: • tipos = caixas; n´umero de caixas ´e n objetos = bolas; n´umero de bolas ´e r C((n − 1) + r, n − 1) Permuta¸c˜oes e combina¸c˜oes com repeti¸c˜ao Quantas maneiras h´a de escolher r objetos de n tipos diferentes, se • a ordem dos objetos ´e importante Sim/N˜ao, e • a repeti¸c˜ao de objetos do mesmo tipo ´e permitida Sim/N˜ao. Ordem sim n˜ao sim AB̸= BA, AA OK AB=BA, AA OK permuta¸c˜ao-r com repeti¸c˜ao combina¸c˜ao-r com repeti¸c˜ao nr C(n + r − 1, r) Repeti¸c˜ao AB̸= BA, AA NOK AB=BA, AA NOK n˜ao permuta¸c˜ao-r combina¸c˜ao-r P(n, r) C(n, r) An´alise Combinat´oria PERMUTAC¸ ˜OES DE OBJETOS IDˆENTICOS Permuta¸c˜oes de objetos idˆenticos • (Rosen exemplo 5.5.7) Quantas strings pode se formar a partir da palavra SUCCESS? • Primeira abordagem: S1UC1C2ES2S3 Temos 3! permuta¸c˜oes entre S1, S2e S3e temos 2! permuta¸c˜oes entre C1e C2. Portanto a resposta ´e 7! 3!2! Permuta¸c˜oes de objetos idˆenticos • (Rosen exemplo 5.5.7) Quantas strings pode se formar a partir da palavra SUCCESS? • Segunda abordagem: imponha uma ordem sequncial: Coloque os 3 Ss em 7 posi¸c˜oes: C(7, 3) Coloque os 2 Cs nas 4 posi¸c˜oes restantes: C(4, 2) Coloque o U nas 2 posi¸c˜oes restantes: C(2, 1) Coloque o E na posi¸c˜ao restante: C(1, 1) • Observe que C(7, 3)C(4, 2)C(2, 1)(C(1, 1)) = 7! 3!4! 4! 2!2! 2! 1!1! 1! 1!0! = 7! 3!2! Permutacoes de objetos idénticos e (Rosen teorema 5.5.3) Suponha que haja n, objetos indistinguiveis de tipo 1, nz objetos indistinguiveis de tipo 2, nx objetos indistinguiveis de tipo k, onde m +:--nm, =n. O ntmero de permutacées é n _ n! m,N2,...,Mk ~~ mlinol... ng! onde (, ” _ ) € 0 coeficiente multinomial. Ny MQ, +++) Mk . . wg . fom \ (n\ (ny 22 _ e O coeficiente binomial é um caso particular: (nnn) = ) = ) ja quen+m=n An´alise Combinat´oria OBJETOS DISTINTOS EM CAIXAS DISTINTAS Objetos em caixas ▶ Muitos problemas combinat´orios correspondem a colocar objetos em caixas (onde a ordem dos objetos n˜ao ´e importante) ▶ Os objetos podem ser distintos (distingu´ıveis) ou idˆenticos. ▶ Da mesma forma, as caixas podem ser distintas (distingu´ıveis) ou idˆenticas. item Vamos analisar as 4 possibilidades, come¸cando por objetos distintos em caixas distintas Objetos distintos em caixas distintas e Rosen exemplo 5.5.8 — Abordagem 1 Quantas maneiras existem para distribuir 5 cartas entre quatro jogadores? e Abordagem errada: 52! 551515! As cartas nao distribuidas permitem 32! permutacoes. e Abordagem certa: impor uma ordem sequencial: Escolher 5 cartas de 52 cartas; Escolher 5 cartas das 47 cartas restantes; Escolher 5 cartas das 42 cartas restantes; Escolher 5 cartas das 37 cartas restantes: 52 52! C(52, 5) C(47, 5) C(42, 5) C(37,5) = = — ( cl )C( )C( ) (s.5.25.3.) 5I5I515132! Objetos distintos em caixas distintas e Rosen exemplo 5.5.8 — Abordagem 2 Quantas maneiras existem para distribuir 5 cartas entre quatro jogadores? e Outra maneira de formular esta questdo: 5 caixas Caixa A com 5 objetos Caixa B com 5 objetos Caixa C com 5 objetos Caixa D com 5 objetos Caixa E com 32 objetos Quantas maneiras existem para distribuir 52 objetos distintos (as cartas) entre as 5 caixas? 52 52! C(52, 5)C(47, 5) C(42, 5) C(37, 5) = (s.5.25.3.) ~ 5151515132! Objetos distintos em caixas distintas e Rosen teorema 5.5.4 Suponha que haja n objetos distinguiveis, e k caixas distinguiveis, com n, objetos em caixa 1, nz objetos em caixa 2, nx objetos em caixa k, onde n +:--nm, =n. O ntmero de maneiras para distribuir os objetos nas caixas é n _ n! M1, M2,...,Mk mint... ny! Objetos distintos em caixas distintas e (Rosen exemplo 5.5.7) Quantas strings terndrias pode se formar com quatro Os, cinco 1s, seis 2s? e Equivalente a: Quantas strings pode se formar a partir da palavra AAAABBBBBCCCCCC? e Resposta: 15 _ 15! 4,5,6] 41516! Objetos distintos em caixas distintas • (Rosen exemplo 5.5.7) Quantas strings pode se formar a partir da palavra SUCCESS? • Resolvendo com objetos distingu´ıves em caixas, teremos quatro caixas: Caixa S, com espa¸co para 3 n´umeros, Caixa C, com espa¸co para 2 n´umeros, Caixa U, com espa¸co para 1 n´umeros, Caixa E, com espa¸co para 1 n´umeros, e devemos distribuir os n´umeros 1,2,3,4,5,6,7 entre as caixas, correspondendo `a posi¸c˜ao da letra na palavra. An´alise Combinat´oria OBJETOS IDˆENTICOS EM CAIXAS DISTINTAS An´alise Combinat´oria OBJETOS DISTINTOS EM CAIXAS IDˆENTICAS Objetos distintos em caixas id´enticas • (Rosen exemplo 5.5.10) H´a quantas maneiras de colocar quatro funcion´arios em trˆes escrit´orios id´enticos? • ABCD|-|- ABC|D|- ABD|C|- ACD|B|- BCD|A|- AB|CD|- AC|BC|- AD|BC|- AB|C|D AC|B|D AD|B|C BC|A|D BD|A|C CD|A|B • N˜ao tem f´ormula simples nesse caso. An´alise Combinat´oria OBJETOS IDˆENTICOS EM CAIXAS IDˆENTICAS Objetos id´enticos em caixas id´enticas – parti¸c˜ao • (Rosen exemplo 5.5.11) H´a quantas maneiras de colocar seis livros idˆenticos em quatro caixas id´enticas? • H´a quantas maneiras de escrever o inteiro seis como uma soma? • 6 5+1 4+2 4+1+1 3+3 3+2+1 3+1+1+1 2+2+2 2+2+1+1 (2+1+1+1+1) (1+1+1+1+1+1) • N˜ao tem f´ormula simples nesse caso. Objetos id´enticos em caixas id´enticas – parti¸c˜ao An´alise Combinat´oria OBJETOS EM CAIXAS – RESUMO Objetos e caixas - RESUMO Colocar objetos em caixas e as caixas sdo distintas (distinguiveis) Sim/Nao e os objetos sdo distintos (distinguiveis) Sim/Nao Caixas distintas sim nao sim nao tem férmula simples YQ 2 ~ Z . g nao | C(n—r+1,r) | nado tem formula simples S 2 3 wo ° ~~ ‘o = © Permutacdes e combinacées generalizadas - RESUMAO 1 Permutacées sem repeticao P(n, r) 2 Combinacées sem repeticao C(n, r) 3 Permuta¢des com repeticao n 4 Combinacées com repeticao C(n—1+45¢,r) 5 Permuta¢des com objetos idénticos (naman) 6 Objetos distintos em caixas distintas — (5) 7 Objetos idénticos em caixas distintas — (4) 8 Objetos distintos em caixas idénticas nao tem formula simples 9 Objetos idénticos em caixas idénticas nao tem formula simples