Il calcolo combinatorio si occupa di calcolare il numero di elementi in insiemi finiti e il numero dei diversi ordinamenti possibili sotto opportune condizioni. Il numero degli elementi di un insieme $A$ è detto cardinalità e si indica con $\vert A\vert$.
Principio di addizione. Se $H$ è un insieme, unione di $k$ sottoinsiemi a due a due disgiunti $S_i$ con $i{\bf =}1,\dots, k$, cioè $H{\bf =}\bigcup_{i{\bf =}1}^k S_i$ e $S_i\cap S_j{\bf =}\emptyset$ $\forall\ i{\bf \not=} j$, allora $\vert H\vert {\bf =}\sum_{i{\bf =}1}^k\vert S_i\vert$.
Principio di moltiplicazione. Si supponga di realizzare $r$ esperimenti tali che:
Allora il numero totale di esiti possibili è $n_{tot}{\bf =}n_1\cdot n_2\cdot\ldots\cdot n_r$.
Esempio. Il direttore di una rete televisiva deve stabilire il palinsesto della prima serata per la prossima settimana. In prima serata la sua rete trasmette sempre un film e in magazzino ce ne sono $36$. In quanti modi il direttore può fare la sua scelta settimanale?
Può scegliere prima il film del lunedì fra i $28$ disponibili, poi quello del martedì fra i rimanenti $27$ e così via fino alla scelta per la domenica fra gli ultimi $22{\bf =}28{\bf -}7{\bf +}1$ film. Il numero delle scelte possibili sarà dunque $28\cdot 27\cdot\ldots\cdot 22$, cioè quasi $6$ miliardi!
Esempio astratto. Consideriamo il prodotto cartesiano $A_1\times\ldots\times A_N$ di $N$ insiemi finiti, con $\vert A_i\vert {\bf =}n_i$ $\forall\ i{\bf =}1,\dots ,N$. Un elemento di questo prodotto cartesiano è una $N$-upla ordinata $(a_1,\dots, a_N)$ con $a_i\in A_i$ $\forall\ i{\bf =}1,\dots, N$. Possiamo scegliere prima $a_1\in A_1$ in $n_1$ modi, poi $a_2\in A_2$ in $n_2$ modi e così via fino ad $a_N$ in $n_N$ modi. Le possibili scelte sono quindi
$\vert A_1\times\ldots\times A_N\vert {\bf =}$ $\vert A_1\vert\cdot\vert A_2\vert\cdot\ldots\cdot\vert A_N\vert {\bf =}$ $n_1\cdot n_2\cdot\ldots\cdot n_N$.Esempio concreto. Da un mazzo $M$ di $52$ carte se ne estraggono in sequenza $r\geq 2$, reiserendo la carta nel mazzo dopo ogni estrazione. Ricavare il numero di possibili estrazioni ordinate nelle quali le prime due carte sono degli assi.
Sia $A\subseteq M$ l'insieme degli assi, avente cardinalità 4: si tratta di contare le sequenze ordinate $(m_1,\dots, m_r)$ con $m_1$, $m_2$ $\in A$ e $m_i\in M$ per $i\geq 3$, cioè gli elementi del prodotto cartesiano $A$ $\times$ $A$ $\times$ $M$ $\times$ $\ldots$ $\times$ $M$, che ha cardinalità $4\cdot 4\cdot 52\cdot\ldots\cdot 52$ ${\bf =}$ $16\cdot 52^{r{\bf -}2}$.
Osservazione. La condizione 3 del principio di moltiplicazione è fondamentale e la sua mancata verifica causa la maggior parte degli errori nel calcolo combinatorio. Si voglia per esempio eleggere un comitato di due persone in un gruppo costituito da un uomo $U$ e due donne $A$ e $B$: i possibili comitati sono evidentemente $3$, cioè $\{U,A\}$, $\{U,B\}$, $\{A,B\}$. Proviamo a realizzare il comitato attraverso due esperimenti consecutivi:
Applicando il principio di moltiplicazione, risulterebbero $4$ possibili comitati, ma in questo esperimento il principio non è applicabile in quanto la scelta di $A$ nel primo esperimento e di $B$ nel secondo esperimento conduce allo stesso esito $\{A,B\}$ ottenuto scegliendo $B$ nel primo esperimento e $A$ nel secondo.
Principio del quoziente. Sia $\sim$ una qualsiasi relazione di equivalenza tra gli elementi di un insieme $H$ di cardinalità $n$. Se $\forall\ s\in H$ risulta $\vert[s]\vert {\bf =}k$ (dove $[s]$ indica la classe di equivalenza di $s$), allora $\vert H/_\sim\vert {\bf =} n/k$.