Baixe o app para aproveitar ainda mais
Prévia do material em texto
Fundamentos Matema´ticos para Computac¸a˜o Sistemas de Informac¸a˜o Luis Antonio Kowada UFF-Instituto de Computac¸a˜o 2017-2 Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 1 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Definic¸a˜o Fatorial de n ∈ N, denotado por n!, e´ o valor dado pela seguinte expressa˜o n! = 1 se n = 0 1 se n = 1 n · (n − 1)! se n > 1 . De forma equivalente temos que 0! = 1 n! = Πni=1i = 1 · 2 · 3 · · · (n − 1) · n. Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 2 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Lembrete Uma Permutac¸a˜o de um conjunto A e´ uma bijec¸a˜o de A para A. Proposic¸a˜o Dado um conjunto A finito, seja n = |A|, tem-se que exisitem n! poss´ıveis permutac¸o˜es de A. Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 3 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Princ´ıpio multiplicativo Se existem n1 poss´ıveis resultados para um primeiro evento e n2 para um segundo, enta˜o existem n1 · n2 resultados poss´ıveis para a sequeˆncia dos dois eventos. Princ´ıpio aditivo Se A e B sa˜o eventos disjuntos com n1 e n2 resultados poss´ıveis, respectivamente, enta˜o o nu´mero total de possibilidades para o evento A ou B e´ n1 + n2. Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 4 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Princ´ıpio das casas de pombo Se mais de k itens sa˜o colocados em k caixas, enta˜o pelo menos uma caixa possui mais de um item. Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 5 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Definic¸a˜o Dado um conjunto A, chama-se arranjo com repetic¸a˜o de A, tomado r a r , a qualquer r -upla ordenada de A× A× · · · × A. A quantidade de poss´ıveis arranjos com repetic¸a˜o de um conjunto com n elementos tomados r a r e´ ARn,r = n r . Definic¸a˜o Dado um conjunto A, chama-se arranjo sem repetic¸a˜o de A, tomado r a r , a qualquer r -upla ordenada de A× A× · · · × A, formada por elementos distintos. A quantidade de poss´ıveis arranjos sem repetic¸a˜o de um conjunto com n elementos tomados r a r e´ ASn,r = n! (n−r)! . Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 6 / 9 Ana´lise Combinato´ria Conceitos e propriedades importantes Definic¸a˜o Seja A um conjunto com n elementos, chama-se combinac¸a˜o dos n elementos, tomado r a r , a qualquer sub-conjunto de A que possua r elementos. A quantidade de poss´ıveis combinac¸o˜es de um conjunto com n elementos tomados r a r e´ ( n r ) := Cn,r = n! r !(n−r)! . Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 7 / 9 Ana´lise Combinato´ria Triaˆngulo de Pascal ( 0 0 ) ( 1 0 )( 1 1 ) ( 2 0 )( 2 1 )( 2 2 ) ( 3 0 )( 3 1 )( 3 2 )( 3 3 ) ...( n 0 ) · · · ( n n ) ... Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 8 / 9 Ana´lise Combinato´ria Algumas propriedades 1 ( n 0 ) = ( n n ) = 1 2 ( n 1 ) = ( n n − 1 ) = n 3 ( n r ) = ( n n − r ) Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 9 / 9 Análise Combinatória
Compartilhar