Il Calcolo combinatorio è una branca della matematica orientata allo sviluppo di formule che permettono di ottenere il numero di casi distinti che si possono presentare in un esperimento, od il numero di elementi che compongono un insieme, senza ricorrere alla loro enumerazione esplicita.
Qualcuno ha definito la combinatoria come "l'arte di contare ... senza contare"mettendo in evidenza la maggiore importanza che in combinatoria ha la conoscenza del numero di combinazioni, rispetto alla conoscenza delle combinazioni stesse.
Serve conoscere prima i seguenti dati:
1) PERMUTAZIONI SEMPLICI DI n OGGETTI sono le combinazioni di nelementi in cui conta l'ordine in cui gli elementi sono disposti e non si possono ripetere gli stessi elementi all'interno di ogni permutazione.
Si chiama FATTORIALE di un numero naturale n il prodotto di tutti i numeri naturali compresi fra 1 e n: n fattori interi decrescenti da n ad 1. Il fattoriale di un numero naturale n si indica col simbolo: n! e indica il numero di permutazioni semplici o ordinamenti di n oggetti:
n! = n⋅ (n-1)⋅(n-2)⋅...⋅2⋅1
2) PERMUTAZIONI CON RIPETIZIONE
Una permutazione di n oggetti di cui h uguali tra loro e distinti dai precedenti, kuguali tra loro e distinti dai precedenti, ..., p uguali tra loro e distinti dai precedenti con h+k+...+p=n è:
3) DISPOSIZIONI SEMPLICI DI n OGGETTI DI CLASSE k
Si dice "disposizione semplice di n oggetti a k a k" o anche "di classe k" (con k ≤ n) ogni allineamento con oggetti tutti distinti, di n oggetti a gruppi di k. Il numero totale di n oggetti a gruppi di k è dato da:
Possiamo infatti scegliere in n modi diversi l'oggetto da mettere al primo posto, in n-1 modi quello da mettere al secondo posto (vanno bene tutti, tranne quello messo al primo posto), in n-2 modi quello da mettere al terzo posto e così via fino all'ultimo posto; poiché i posti sono k, all'ultimo posto potremo scegliere tra n-(k-1)oggetti (tutti meno i (k-1) già utilizzati).
4) DISPOSIZIONI CON RIPETIZIONE
Una disposizione con ripetizione di n oggetti distinti presi k alla volta è un possibile modo di scegliere k oggetti eventualmente ripetuti dagli n e ordinarli.
5) COMBINAZIONI SEMPLICI
Le combinazioni di n oggetti presi a k a k, sono il numero dei campioni non ordinati di numerosità k. Non conta l'ordine, quindi (a,b) sarà lo stesso campione di (b,a).
Il simbolo usato per le combinazioni semplici si legge "n su k" e prende il nome, per motivi storici, di coefficiente binomiale. Esprime il numero di sottoinsiemi distinti di cardinalità k che si possono formare con gli elementi di un insieme di cardinalità n, praticamente si risponde alla domanda:"dati n oggetti, in quanti modi ne posso scegliere k?"
(abbiamo sempre k ≤ n)
6) COMBINAZIONI CON RIPETIZIONE
Una combinazione con ripetizione è una combinazione che può avere anche ripetizioni di uno stesso elemento. Il numero di combinazioni con ripetizione di n oggetti di classe k sono tutti i possibili raggruppamenti che si possono formare con n oggetti, presi k alla volta, considerando differenti due raggruppamenti che differiscano:
– per qualche elemento
– per il numero di volte in cui un dato oggetto viene ripetuto
In tal caso, come si capisce facilmente, l’ordine in cui compaiono gli elementi non è più significativo e ovviamente in questo caso k può essere maggiore, minore o uguale ad n.
C'è un modo tradizionale di enunciare questo problema noto come "problema della pasticceria": nel banco della pasticceria ci sono n tipi diversi di paste e io voglio riempire un vassoio con k paste (con eventuali ripetizioni, cioè posso prendere due o più o, al limite, tutte le k paste dello stesso tipo). In quanti modi diversi posso riempire il vassoio? La risposta è:
