Introduzione
Il calcolo combinatorio, premessa indispensabile per lo studio del calcolo delle probabilità, si occupa della determinazione della cardinalità di certi insiemi finiti, assegnati mediante proprietà caratteristica. Il problema è usualmente molto complesso e, soprattutto, non esistono metodi "standard" per risolverlo: forse per questo è ritenuto argomento ostico e difficile.
In queste pagine descriveremo le tecniche fondamentali e soprattutto proporremo molti esempi risolti: l'esame di un gran numero di casi concreti è l'unico modo per acquisire dimestichezza nella risoluzione di questo tipo di problemi.
E' opportuno segnalare fin da subito che esistono situazioni
in cui l'unica strategia che è possibile utilizzare
è quella di scrivere l'insieme in questione e
numerare, uno alla volta, i suoi elementi. L'esempio
più classico è costituito dal seguente problema:
Dato un numero naturale n, determinare la
cardinalità, diciamola π(n), dell'insieme
dei numeri primi minori di n. Non resta altro da fare
che scrivere pazientemente tutti i numeri richiesti e contarli
(almeno per ora, non è escluso che in un futuro -
sicuramente non prossimo - si riesca a trovare una formula che
sostituisca la nota formula approssimata 
,
dovuta a Gauss).
Come già segnalato la risoluzione di problemi di Analisi Combinatoria richiede modi di ragionamento e tecniche usualmente poco familiari e che non si lasciano classificare in schemi standard. Ragionamenti intuitivi portano facilmente a risultati errati ed è opportuno ricondurre i problemi ad alcuni modelli astratti che di solito facilitano la ricerca della tecnica corretta. Utilizzeremo di norma i modelli, classici, dell'estrazione di oggetti da un'urna e della collocazione di oggetti in celle.
- Modello dell'urna. Consiste nell'estrarre da un'urna di composizione nota un certo numero di oggetti. In alcuni casi è prevista la reintroduzione nell'urna dell'oggetto estratto (modello con reimbussolamento), in altri casi no.
- Modello a celle. Si tratta di collocare un determinato numero di oggetti in un dato numero di celle, essendo a volte consentito che più oggetti stiano in una cella, altre volte no.
I due approcci sono assolutamente equivalenti, ma è utile familiarizzare con entrambi: a seconda del tipo di problema può essere più semplice schematizzarlo con uno invece che con l'altro.
Ricordiamo, prima di cominciare, la definizione di alcuni simboli di uso comune nel calcolo combinatorio:
- n! (n fattoriale): è il prodotto di tutti i numeri naturali da 1 ad n. n! = 1·2·3·...·n
- n!! (n semifattoriale): è il prodotto di tutti i naturali da 1 ad n che hanno la stessa parità di n. Se n è pari si ottiene dunque: n!! = 2·4·...·n; se n è dispari: n!! = 1·3·...·n. E' ovvio che n! = n!! · (n-1)!! .
- 0! = 1