Analisi combinatoria Flashcards
Principio fondamentale del calcolo combinatorio.
Si realizzino 2 esperimenti. Si supponga che il primo esperimento abbia m esiti possibili, e che per ognuno di questi il secondo esperimento abbia n esiti possibili.
Se sequenze distinte di esiti dei due esperimenti producono esiti finali distinti, allora vi sono in tutto mn esiti possibili.
Dimostrazione del principio fondamentale del calcolo combinatorio.
Elencando tutti gli esiti dei due esperimenti, come risultato sia ha una matrice di coppie del tipo (i, j), dove i è l’esito del primo esperimento e j è l’esito del secondo esperimento. L’insieme dei possibili esiti consiste di m righe e n colonne. Quindi in tutto vi sono mn esiti possibili.
Si noti che sequenze distinte di esiti dei due esperimenti producono esiti finali distinti.
Principio fondamentale (generalizzato) del calcolo combinatorio.
Si realizzino r esperimenti. Si supponga che il primo esperimento abbia n1 esiti possibili, e che per ognuno di questi il secondo esperimento abbia n2 esiti possibili, e ancora che per ognuno degli esiti dei primi 2 esperimenti il terzo esperimento abbia n3 esiti possibili, ecc. Allora, se sequenze distinte di esiti degli r esperimenti producono esiti finali distinti, allora gli r esperimenti producono in tutto n1·n2···nr esiti possibili.
Definizione di permutazione.
Le permutazioni di n oggetti distinti sono tutte le sequenze ordinate ottenibili scambiando gli oggetti in tutti i modi possibili.
Come si calcolano le permutazioni di n oggetti.
Le permutazioni distinte di n oggetti sono
n(n−1)(n−2)···3·2·1 =n!
Definizione di disposizione semplice.
Le disposizioni semplici di n oggetti sono tutti gli insiemi ordinati costituiti da r degli n oggetti, in cui non sono ammesse ripetizioni.
Definizione di disposizioni con ripetizioni
Le disposizioni con ripetizioni di n oggetti sono tutti gli insiemi ordinati di r dei n oggetti, nei quali sono ammesse ripetizioni.
Come si calcolano il numero di disposizioni semplici di n oggetti?
Dn,r = n(n − 1)(n − 2)· · ·(n − r + 1) = n! / (n − r)! = (n)_r
(n)_r è detto fattoriale discendente.
Come si calcolano il numero di disposizioni con ripetizioni di n oggetti?
D′n,r = n · n · n · · · n = n^r
Definizione di combinazione semplice.
Le combinazioni semplici di n oggetti sono tutti gli insiemi non ordinati costituiti da r degli n oggetti, in cui non sono ammesse ripetizioni.
Definizione di combinazione con ripetizioni.
Le combinazioni con ripetizioni di n oggetti sono tutti gli insiemi non ordinati costituiti da r degli n oggetti, in cui sono ammesse ripetizioni.
Come si calcolano il numero di combinazioni semplici di n oggetti?
Cn,r = n(n-1)…(n-r+1)/r! = n!/(n-r)!r! = (n)_r/r!
Definizione di coefficiente binomiale
n!/(n-r)r! = (n)r/r! > 0
Come si calcolano il numero di combinazioni con ripetizioni di n oggetti?
C’n,r = (n + r -1)! / (n-1)!r!
Formula di ricorrenza dei coefficienti binomiali.
(n r) = (n-1 r-1) + (n-1 r) 1 <= r <= n
