Calcolo combinatorio: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 42:
=== Combinazioni ===
==== Configurazioni non ordinate di dimensione k senza ripetizioni ====
Si chiama '''combinazione semplice''' una configurazione in cui non ha importanza l'ordine degli elementi e non si può riperete lo stesso elemento più volte. Potendo scegliere <math>k</math> elementi da <math>n</math> oggetti distintiti si devono calcolare le permutazioni dei <math>k</math> oggetti e togliere tutte le sequenze uguali a meno di un ordinamento. Le prime sono esattamente le disposizioni semplici mentre le ultime sono le permutazioni possibili della sequenza, ovvero <math>k!</math>:
<math>C^{k}_{n} = {n \choose k} = \frac{D^{k}_{n}}{k!} = \frac{n!}{k!(n-k)!}</math>
Esempio:
==== Configurazioni non ordinate di dimensione k con ripetizioni ====
Quando l'ordine non è importante ma è possibile avere ripetizione degli elementi si parla di combinazioni con ripetizione. In questo caso un elemento <math>n</math> può essere ripetuto fino a <math>k</math> volte ma bisogna sempre eliminare tutte le sequenze simili a meno di un ordinamento:
<math>
CR^{k}_{n} = \frac{DR^{k}_{n}}{k!}
= \frac{ {\underbrace{n_{1} \times \dots \times n_{k}} \atop {k-volte}} } {k!}
= \frac{ n \times (n-1)+1 \times (n-2)+2 \times \dots \times (n-k)+k} {k!}
= \frac{(n+k-1)!}{k!(n-1)!} = \frac{(n+k-1)!}{k!(n+k-1-k)!}
</math>
riscrivibile quindi come
<math>
CR^{k}_{n} = {n + k -1 \choose k}
</math>
Esempio:
| |||