Matematicamente
|
|
Ti trovi in: Home 
Formulario Calcolo combinatorio
| Calcolo combinatorio | di Gianni Sammito |
Coefficiente binomiale
Dati $n, k \in \mathbb{N}$, con $n \ge k$, si definisce coefficiente binomiale di $n$ su $k$
$((n),(k)) = \frac{n!}{k! (n-k)!}$
Esempio: $((4),(2)) = \frac{4!}{2! (4-2)!} = \frac{4!}{2! \cdot 2!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1 \cdot 2 \cdot 1} = 6$
Proprietà del coefficiente binomialeI coefficienti binomiali rispettano le seguenti proprietà
$((n),(0)) = ((n),(n)) = 1 \quad \forall n \in \mathbb{N}$
$((n),(1)) = ((n),(n - 1)) = n \quad \forall n \in \mathbb{N}$
$((n),(k)) = ((n),(n-k)) \quad \forall n,k \in \mathbb{N}$, $n \ge k$
$((n+1),(k+1)) = ((n),(k+1)) + ((n),(k)) \quad \forall n,k \in \mathbb{N}$, $n \ge k$
$\sum_{k=0}^n ((n),(k)) a^k b^{n-k} = (a+b)^n$
In particolare, dall'ultima proprietà discende che
$\sum_{k=0}^n ((n),(k)) = 2^n \quad \forall n \in \mathbb{N}$
Coefficiente multinomialeDati $r+1$ numeri naturali, $n, k_1, k_2, \ldots, k_r \in \mathbb{N}$, tali che $k_1 + k_2 + \ldots + k_r = n$, si definisce coefficiente multinomiale
$((n),(k_1"," k_2"," \ldots"," k_r)) = \frac{n!}{k_{1}! \cdot k_{2}! \cdot \ldots \cdot k_{r}!} = \frac{n!}{\prod_{i=1}^r k_{i}!}$
e comunque si scelgano i numeri naturali $n, k_1, k_2, \ldots, k_r$ (purché $k_1 + k_2 + \ldots + k_r = n$), risulta
$((n),(k_1"," k_2"," \ldots"," k_r)) \in \mathbb{N}$
Proprietà del coefficiente multinomialeFissato $n \in \mathbb{N}$, e detto $A_n \subset \mathbb{N}^r$ l'insieme di tutte le $r$-ple di naturali $(k_1, k_2, \ldots, k_r)$ tali che $k_1 + k_2 + \ldots + k_r = n$, risulta
$(x_1
+ x_2 + \ldots + x_r)^n = \sum_{(k_1, k_2, \ldots, k_r) \in A_n}
((n),(k_1"," k_2"," \ldots"," k_r)) \cdot x_1^{k_1} \cdot x_2^{k_2} \cdot
\ldots \cdot x_r^{k_r}$
Permutazioni sempliciDato un insieme $X$ con $n$ elementi, si chiama permutazione ogni ordinamento dell'insieme $X$. Equivalentemente, dati $n$ oggetti distinti, il numero di permutazioni $P_n$ è il numero di tutti i possibili ordinamenti degli $n$ oggetti, e risulta
$P_n = n!$
Esempio: in quanti modi diversi si possono disporre $10$ persone in fila? Risposta: $10!$ Permutazioni con ripetizioneDati $n$ oggetti non tutti distinti fra di loro, un ordinamento di tali oggeti si chiama permutazione con ripetizione. Supponiamo di poter suddividere gli $n$ oggetti in $h$ tipi diversi (ovviamente $h \le n$). Siano $n_i$ il numero di elementi di tipo $i$, per ogni $i=1, 2, \ldots, h$, allora $n = n_1 + n_2 + \ldots + n_h$. Indicando con $P_{n_1, n_2, \ldots, n_h}^{**}$ il numero delle permutazioni con ripetizione, ovvero il numero di tutti i possibili ordinamenti degli $n$ oggetti, risulta
$P_{n_1, n_2, \ldots, n_h}^{**} = \frac{n!}{n_{1}! \cdot n_{2}! \cdot \ldots \cdot n_{h}!}$
Esempio: Quanti sono i possibili anagrammi della parola matematica? Si hanno in totale $10$ elementi, visto che la parola matematica è costituita da $10$ lettere. Tali lettere non sono tutte distinte, ma possono essere partizionate in $6$ tipi diversi
1° tipo: lettera m, $n_1 = 2$
2° tipo: lettera a, $n_2 = 3$
3° tipo: lettera t, $n_3 = 2$
4° tipo: lettera e, $n_4 = 1$
5° tipo: lettera i, $n_5 = 1$
6° tipo: lettera c, $n_6 = 1$
Per determinare il numero di tutti i possibili anagrammi della parola matematica basta calcolare le permutazioni con ripetizione
$\frac{10!}{2! \cdot 3 ! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151200$
Combinazioni sempliciDato un insieme $X$ con cardinalità $n$ (quindi contenente $n$ elementi distinti), ogni sottoinsieme di $X$ con $k$ elementi ($0 \le k \le n$) viene detto combinazione di $n$ oggetti di classe $k$, e si indica con $C_{n,k}$. $C_{n,k}$ rappresenta il numero di tutti possibili modi con cui si possono scegliere $k$ elementi fra $n$ oggetti dati, e risulta
$C_{n,k} = ((n),(k)) = \frac{n!}{k! (n-k)!}$
ed inoltre
$C_{n,k} = \frac{n!}{k! (n-k)!} = P_{k, n-k}^{**}$
Esempio: Quanti sono i possibili sottoinsiemi di un insieme $n$ elementi? I possibili sottoinsiemi possono essere l'insieme vuoto, gli insiemi con $1$ elemento, gli insiemi con $2$ elementi, etc. Quindi il numero di tutti i possibili sottoinsiemi è
$\sum_{k=0}^n ((n),(k)) = 2^n$
Combinazioni con ripetizioneDato un insieme $X$ di cardinalità $n$, ossia dati $n$ oggetti distinti, ogni raggruppamento di $k$ elementi di $X$, ammettendo anche ripetizioni di oggetti, viene detto combinazione con ripetizione di $n$ oggetti di classe $k$. Notare che $k$ può essere maggiore di $n$, e in ogni raggruppamento non conta l'ordine con cui vengono elencati gli elementi. Indicando con $C_{n,k}^{**}$ il numero di tutte le possibili combinazioni con ripetizione di $n$ oggetti di classe $k$, risulta
$C_{n,k}^{**} = ((n+k-1),(k))$
Esempio: Dato
$X = \{a, b, c, d\}$, quante sono le possibili coppie formate da
elementi di $X$, ammettendo anche ripetizioni, senza contare l'ordine
con cui tali elementi sono elencati? Risposta: $C_{4,2} = ((4+2-1),(2))
= ((5),(2)) = 10$. E infatti tutte le coppie possibili sono 
Esempio: In quanti modi si possono scegliere $5$ carte da un mazzo di $40$ con rimpiazzo? Risposta: $C_{40,5}^{**} = ((40 + 5 - 1),(5)) = ((44),(5))$ Disposizioni sempliciDati $n$ oggetti, ogni ordinamento di $k$ oggetti ($0 \le k \le n)$ comunque scelti fra gli $n$ si chiama disposizione di $n$ oggetti di classe $k$. Notare che due disposizioni possono differire o per gli oggetti contenuti o per l'ordine degli oggetti. Il numero di tutte le possibili disposizioni di $n$ oggetti di classe $k$ si indica con $D_{n,k}$ e risulta
$D_{n,k} = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$
Esempio: Da un'urna contenente $90$ palline numerate, quante sono le possibili sequenze di $5$ numeri che si possono ottenere estraendo, senza rimpiazzo, cinque palline? Risposta: $D_{90,5} = \frac{90!}{85!}$ Disposizioni con ripetizioneDati $n$ oggetti, ogni ordinamento di $k$ oggetti in cui sono ammesse anche ripetizioni (quindi $k$ può essere qualsiai) si chiama disposizione con ripetizione di $n$ oggetti di classe $k$. Indicando con $D_{n,k}^{**}$ il numero di tutte le possibili disposizioni con ripetizioni di $n$ oggetti di classe $k$, risulta
$D_{n,k}^{**} = n^k$
Esempio: Da un'urna contenente $90$ palline numerate, quante sono le possibili sequenze di $5$ numeri che si possono ottenere estraendo, con rimpiazzo, cinque palline? Risposta: $D_{90,5}^{**} = 90^5$ Esempio: quante sono le parole di $4$ lettere che si possono formare utilizzando le lettere $\{a,b,c,d,e\}$? Risposta: $D_{5,4}^{**} = 5^4$.
Scritto da , il 16-07-2009 07:33 Ottimo Scrivi Commento
Powered by AkoComment Tweaked Special Edition v.1.4.6 |
||||||
| < Prec. | Pros. > |
|---|
|
Iniziative editoriali
|
Test - quiz - simulazione |
Gioca con la matematica |
 |
|
|
|
|