Calcolo combinatorio

 1. Generalità.

Sia assegnato un insieme X avente n elementi diversi, che possiamo indicare con lettere distinte oppure, più comodamente, con una stessa lettera munita di un indice:

 

X ={ x₁, x₂, ...x_n }.

 

Gli elementi di X si possono raggruppare in vario modo per formare altri insiemi; il calcolo combinatorio studia appunto il numero e le proprietà di questi nuovi insiemi.

 

2. Disposizioni semplici.

Siano X = { x₁, x₂, ... x_n } un insieme formato da n elementi distinti e k un numero naturale k £ n.

Si dicono disposizioni semplici degli n elementi di classe k, e si indicano con , tutti i sottoinsiemi (detti anche raggruppamenti)  ordinari di X tali che:

·       ogni sottoinsieme contenga k elementi distinti;

·       due qualsiasi raggruppamenti differiscano o per almeno un elemento o per l’ordine con cui sono disposti.

 

Il numero delle disposizioni semplici è uguale al prodotto di k numeri naturali consecutivi decrescenti a partire da n: 

 

 

Il numero delle disposizioni semplici si può calcolare anche con la formula:

 

 

avendo indicato con . Il simbolo  si legge n fattoriale e si pone

 

Esempio 1.- .

 

Esempio 2.- Dati tre elementi a, b, c, determinare il numero delle disposizioni di 3 oggetti  di classe 2.

Si ha:

Per determinarle possiamo costruire il seguente prospetto. Nella figura 1 le disposizioni semplici di classe 2 sono quelle al di sopra e al di sotto della diagonale aa-bb-cc, ossia:

 

{ab, ac, bc, ba, ca, cb}