Calcolo combinatorio

Page 1

Calcolo Combinatorio Calcolo delle Probabilità Mattia Natali 1 Calcolo Combinatorio  Definizioni:  Calcolo combinatorio: si occupa di contare “stringhe provenienti da un certo alfabeto”.  Principio di enumerazione: supponiamo di avere delle stringhe lunghe r∈. Le varie caselline della stringa le chiamiamo slot.  Nello slot 1 posso scrivere n1 simboli.  Nello slot 2 posso scrivere n2 simboli ∀ scelta dello slot 1.  Nello slot 3 posso scrivere n3 simboli ∀ scelta degli slot 1 e 2.  Nello slot r posso scrivere nr simboli ∀ scelta degli slot n1,n2,...,nr−1. Quante stringhe posso ottenere in questo modo? Il numero di queste stringhe è n1·n2·...·nr. Questo si chiama principio di enumerazione.  Tipologie:  Disposizioni semplici: stringhe lunghe k da un alfabeto di n elementi senza ripetizioni.  Dn,k()=nn−1()...n−k+1().  Caso particolare: le disposizioni di n oggetti presi da n si chiamano permutazioni. • Dn,n()=nn−1()·...·2·1  Disposizioni con ripetizione di k oggetti tra n oggetti: sono le stringhe lunghe k da un alfabeto di n simboli.  n·n·n·...·n=nk.  Combinazioni di k elementi tra n: sono i sottoinsiemi di k elementi presi da un insieme di n elementi. Ricorda che nelle {} non si conta l’ordine mentre () sì.  Cn,k()= numero di combinazioni di k oggetti tra n.  Cn,k()=Dn,k()k!=n!k!n−k()!=nk⎛⎝⎜⎞⎠⎟ si dice n sopra k (o n scelgo k o coefficiente binomiale).  Il numero di E⊂S:S=n,E=k⇒nk⎛⎝⎜⎞⎠⎟.  Nota: n0⎛⎝⎜⎞⎠⎟=n!0!n−0()!=1.  Fattoriali:  Per definizione: 0!=1.  Dn,k()=nn−1()...n−k+1()n−k()n−k−1()·...·1n−k()n−k−1()·...·1=n!n−k()!  n! è il numero di ordinamenti di un insieme di n elementi (è una permutazione).