Calcolo combinatorio

CALCOLO COMBINATORIO

Disposizioni semplici di n oggetti

DEFINIZIONE - Dati n elementi distinti, si chiama "disposizione semplice" degli n elementi, presi a k a k, (k n), o della classe k, in gruppo ordinato di k degli n elementi.

Due di tali disposizioni si ritengono diverse quando differiscono per almeno un elemento, oppure l'ordine con cui gli elementi si presentano.

TEOREMA - Il numero di disposizioni semplici di n elementi (distinti), della classe k, è uguale al prodotto di k numeri interi, decrescenti, dei quali il primo è n; cioè:

Disposizioni con ripetizione

DEFINIZIONE - Dati n elementi distinti, si dice "disposizione con ripetizione" degli n elementi a k a k (con k numero intero qualunque) un gruppo ordinato formato con k degli n elementi, potendo uno stesso elemento figurare nel gruppo fino a k volte.

Due di tali disposizioni si ritengono diverse quando esistono due elementi distinti che occupano nelle disposizioni il medesimo posto.

TEOREMA - Il numero delle disposizioni con ripetizione (o complete) di n elementi distinti della classe k è uguale alla potenza di base n ed esponente k; cioè:

Permutazioni semplici

DEFINIZIONE - Si chiamano "permutazioni semplici" di n elementi distinti le disposizioni semplici degli n elementi, presi ad n ad n.

Le permutazioni di n elementi distinti sono tutti i gruppi di n elementi che si possono formare con gli elementi dati, e che differiscono tra loro soltanto per l'ordine degli elementi.

e quindi, cioè il numero delle permutazioni di n elementi distinti è uguale al prodotto dei primi n numeri naturali (diversi da zero).

DEFINIZIONE - Se k è un numero naturale maggiore di 1, si chiama fattoriale del numero k, e si indica con k!, il prodotto dei primi k numeri naturali, cioè:

Da cui si ha che

Combinazioni semplici

DEFINIZIONE - Dati n elementi distinti, si chiama "combinazione semplice" degli n elementi, presi a k a k, o della classe k, (k n), un qualunque gruppo formato da k degli n elementi dati.

Due di tali combinazioni si ritengono distinte quando differiscono tra loro per almeno un elemento.

Questa formula dà il numero delle combinazioni semplici di n elementi, presi a k a k. L'ultimo simbolo si legge "n su k" o "n sopra k" in cui, n si dice ordine e k si dice classe (o indice).

In particolare: e

Coefficienti binomiali e loro proprietà

Il simbolo si chiama coefficiente binomiale (o simbolo combinatorio), gode di molte proprietà:

da cui si deduce che

3) Formula di Stifel: da cui segue:

4) Proprietà di ricorrenza:

Formula del binomio di Newton

FORMULA DI TARTAGLIA-NEWTON - Qualunque siano i due numeri a e b e l'intero positivo n, si ha: