Calcolo Combinatorio - Università San Raffaele - PDF

Docente Veronica Redaelli Lezione Calcolo combinatorio  Veronica Redaelli Sommario üCalcolo combinatorio üPermutazioni üDisposizioni...

Docente Veronica Redaelli Lezione Calcolo combinatorio  Veronica Redaelli Sommario üCalcolo combinatorio üPermutazioni üDisposizioni üCombinazioni Calcolo combinatorio 2 di 18  Veronica Redaelli CALCOLO COMBINATORIO ü L’arte del contare Ø quante parole diverse si possono formare con 4 lettere? Ø dobbiamo scegliere 4 persone tra un gruppo di 10: quante alternative abbiamo? Ø … Calcolo combinatorio 3 di 18  Veronica Redaelli CALCOLO COMBINATORIO ü Quante parole diverse si possono formare con 3 lettere, ad esempio A , I , M ? Ø se non devono ripetersi, ho 6 possibilità AMI, AIM, MAI, MIA, IAM, IMA Ø se si possono ripetere, ne ho 27 AAA AAM AAI AMA AMM AMI AIA AIM AII MAA MAM MAI MMA MMM MMI MIA MIM MII IAA IAM IAI IMA IMM IMI IIA IIM III Calcolo combinatorio 4 di 18  Veronica Redaelli CALCOLO COMBINATORIO ü Quante parole diverse si possono formare con 3 lettere, ad esempio A , I , M senza ripeterle ? Ø per la prima lettera abbiamo tre scelte, per la seconda ne abbiamo solo due e per la terza lettera possiamo usare solamente l’unica lettera rimasta Ø 3·2·1 = 6 parole. Calcolo combinatorio 5 di 18  Veronica Redaelli CALCOLO COMBINATORIO Ø Il numero 3·2·1 si indica con il simbolo : 3! “ tre fattoriale ” es. 2! = 2·1 = 2 6! = 6·5·4·3·2·1 = 720 Calcolo combinatorio 6 di 18  Veronica Redaelli PERMUTAZIONI di un insieme finito, i modi in cui i suoi elementi possono essere messi in ordine Ø Il numero delle permutazioni di n elementi è n! Calcolo combinatorio 7 di 18  Veronica Redaelli DISPOSIZIONI senza ripetizioni di n elementi a gruppi di k, Ø le liste ordinate di k elementi, scelti tra gli n elementi dati e non ripetuti Ø Il loro numero è : 𝑛! 𝑛−𝑘 ! Calcolo combinatorio 8 di 18  Veronica Redaelli DISPOSIZIONI senza ripetizioni es. Lotteria di tre premi su 100 biglietti venduti, quante possibili estrazioni posso avere ? !"" ! !"" ! = = 100 · 99 · 98 = 970200 !""$% ! &' ! Calcolo combinatorio 9 di 18  Veronica Redaelli DISPOSIZIONI con ripetizioni di n elementi a gruppi di k, Ø le liste ordinate di k elementi, scelti tra gli n elementi dati eventualmenti ripetuti Ø Il loro numero è : n k Calcolo combinatorio 10 di 18  Veronica Redaelli ü Ma se l’ordine con cui vengono scelti gli elementi non fosse importante e volessimo trascurarlo ? A, I ,M uguale a A, M, I es. dei tre collaboratori Calcolo combinatorio 11 di 18  Veronica Redaelli COMBINAZIONI senza ripetizioni di n elementi a gruppi di k, Ø I sottoinsiemi di k elementi, scelti tra gli n elementi dati e non ripetuti Ø Il loro numero è : 𝑛! 𝑘! 𝑛−𝑘 ! Calcolo combinatorio 12 di 18  Veronica Redaelli COEFFICIENTE BINOMIALE Ø La formula 𝑛! 𝑘! 𝑛−𝑘 ! Si indica con ! " ü Per convenzione n! = 1 Calcolo combinatorio 13 di 18  Veronica Redaelli COEFFICIENTE BINOMIALE es. Il numero dei gruppi di tre persone tra cinque persone è : ! ! ! % # & = = 10 # ! !$# ! # & & Calcolo combinatorio 14 di 18  Veronica Redaelli COMBINAZIONI con ripetizioni di n elementi a gruppi di k, Ø I sottoinsiemi di k elementi, scelti tra gli n elementi dati e non ripetuti Ø Il loro numero è : !"#$% # Calcolo combinatorio 15 di 18  Veronica Redaelli es. quanti tipi di scatole da 4 cioccolatini posso fare con 3 gusti diversi ? ()*$! %)+$! , * = + = + ' ! ' ! = = 15 % ! '$% ! & Calcolo combinatorio 16 di 18  Veronica Redaelli Riassumendo üCalcolo combinatorio üPermutazioni üDisposizioni üCombinazioni Calcolo combinatorio 17 di 18  Veronica Redaelli F! N ∑ Calcolo combinatorio 18 di 18