Pagina:Teoria degli errori e fondamenti di statistica.djvu/262

246

Appendice A - Cenni di calcolo combinatorio

che ciascuno di essi contenga tutte e sole quelle disposizioni che differiscano esclusivamente per l’ordine ma siano composte dagli stessi oggetti; ovviamente il numero di questi sottoinsiemi è $C_{K}^{N}$: ed ognuno di essi contiene un numero di elementi che è $P_{K}$.

Da qui ricaviamo

$C_{K}^{N}\;\equiv \;{\binom {N}{K}}\;=\;{\frac {D_{K}^{N}}{P_{K}}}\;=\;{\frac {N\cdot (N-1)\cdots (N-K+1)}{K\cdot (K-1)\cdots 1}}\;=\;{\frac {N!}{K!\,(N-K)!}}$

(A.3)

O, in altre parole, il numero di combinazioni di classe $K$ di $N$ oggetti è uguale al rapporto tra il prodotto di $K$ numeri interi decrescenti a partire da $N$ ed il prodotto di $K$ numeri interi crescenti a partire dall’unità.

Si dimostrano poi facilmente, a partire dalla definizione, due importanti proprietà dei coefficienti binomiali:

${\binom {N}{K}}={\binom {N}{N-K}}$

e

${\binom {N+1}{K}}={\binom {N}{K-1}}+{\binom {N}{K}}$.

È da osservare che, così come sono stati ricavati (dalla definizione delle possibili combinazioni di $N$ oggetti), i coefficienti binomiali hanno senso solo se $N$ e $K$ sono numeri interi; ed inoltre se risulta sia $N>0$ che $0\leq K\leq N$. La definizione (A.3) può comunque essere estesa a valori interi qualunque, ed anche a valori reali di $N$ — ma questo esula dal nostro interesse.

A.7 Partizioni ordinate

Consideriamo un insieme di $N$ oggetti; vogliamo calcolare il numero di maniere in cui essi possono essere divisi in $M$ gruppi che siano composti da $N_{1},N_{2},\ldots ,N_{M}$ oggetti rispettivamente (essendo $N_{1}+N_{2}+\cdots +N_{M}=N$).

Gli $N_{1}$ oggetti che compongono il primo gruppo possono essere scelti in $C_{N_{1}}^{N}$ modi differenti; quelli del secondo gruppo in $C_{N_{2}}^{N-N_{1}}$ modi; e così via. Per il lemma fondamentale del calcolo combinatorio, il numero delle partizioni