Calcolo combinatorio

Il calcolo combinatorio è la branca della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti. Il calcolo combinatorio si interessa soprattutto di contare tali modi, ossia le configurazioni.

Definizione

Dato un insieme ${\displaystyle S}$ di ${\displaystyle n}$ oggetti si vogliono contare le configurazioni che possono assumere ${\displaystyle k}$ oggetti tratti da questo insieme, e per far ciò bisogna precisare due punti importanti:

• se l'ordinamento è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento;^[1]
• se si possono avere più ripetizioni di uno stesso oggetto, ovvero se uno stesso oggetto dell'insieme può o meno essere riusato più volte all'interno di una stessa configurazione.

Permutazioni

Permutazioni semplici (senza ripetizioni)

Una permutazione di un insieme di oggetti è una presentazione ordinata, cioè una sequenza, dei suoi elementi nella quale ogni oggetto viene presentato una ed una sola volta. Per contare quante siano le permutazioni di un insieme con ${\displaystyle n}$ oggetti, si osservi che il primo elemento della configurazione può essere scelto in ${\displaystyle n}$ modi diversi, il secondo in ${\displaystyle (n-1)}$, il terzo in ${\displaystyle (n-2)}$ e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con ${\displaystyle P_{n}}$ il numero delle possibili permutazioni di un insieme di ${\displaystyle n}$ elementi, si ottiene che esse sono esattamente ${\displaystyle n!}$ (${\displaystyle n}$ fattoriale):

${\displaystyle P_{n}=n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 1=n!}$

Da cui si deduce come caso particolare ${\displaystyle P_{1}=1!=1}$. Per completare la definizione di fattoriale mantenendone le proprietà si pone: ${\displaystyle P_{0}=0!=1}$^[2]

Esempi

• Le permutazioni degli elementi dell'insieme ${\displaystyle \left\{a,\,b,\,c\right\}}$ sono ${\displaystyle 3!=3\cdot 2\cdot 1=6}$: ${\displaystyle abc,\,bac,\,bca,\,cab,\,cba,\,acb}$.
• In quanti modi possibili si può anagrammare la parola "MONTE"^[3], contando anche le parole prive di significato?

La parola MONTE è composta da ${\displaystyle 5}$ lettere diverse tra loro, quindi ${\displaystyle n=5}$;

Le permutazioni possibili sono:

${\displaystyle P_{5}=5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120}$ modi di anagrammare la parola MONTE.

Permutazioni con ripetizioni

In alcuni casi un insieme può contenere elementi che si ripetono. In questo caso alcune permutazioni di tali elementi saranno uguali tra loro. Indicando con ${\displaystyle k_{1}}$, ${\displaystyle k_{2}}$ fino a ${\displaystyle k_{r}}$ il numero di volte che si ripetono rispettivamente gli elementi ${\displaystyle 1,\,2,}$ fino a ${\displaystyle r}$, dove ${\displaystyle r\leq n}$, le permutazioni uniche (non ripetute) divengono:

${\displaystyle P_{n}^{k_{1},k_{2},\dots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}}$^[4][5]

Si tratta, infatti, di dividere il numero delle distinte permutazioni di ${\displaystyle n}$ oggetti per il numero delle permutazioni di ${\displaystyle k_{1}!}$ presenze di uno stesso elemento, tutte uguali tra loro, poi per il numero delle permutazioni di ${\displaystyle k_{2}!}$ presenze di uno stesso elemento, ecc.

La formula vale in realtà per qualsiasi permutazione, anche senza ripetizioni di elementi. Infatti, se si assume ${\displaystyle k_{1},\,k_{2}}$ fino a ${\displaystyle k_{r}}$ uguali ad ${\displaystyle 1}$ (cioè gli elementi si ripetono una sola volta), si ottiene esattamente la formula delle permutazioni semplici, perché si ha:

${\displaystyle P_{n}^{k_{1},k_{2},\dots ,k_{r}}={\frac {n!}{k_{1}!\cdots k_{r}!}}={\frac {n!}{1!\cdots 1!}}=n!}$

Esempi

• Le permutazioni di ${\displaystyle \left\{a,\,a,\,b\right\}}$ sono: ${\displaystyle {\frac {3!}{2!\cdot 1!}}=3}$, ossia: ${\displaystyle aab,\,aba,\,baa}$.
• In quanti modi è possibile anagrammare la parola "FARFALLA"?

Le lettere contenute nella parola sono ${\displaystyle n=8}$; gli elementi che si ripetono sono:

la lettera F ${\displaystyle (k_{1}=2)}$

la lettera A ${\displaystyle (k_{2}=3)}$

la lettera L ${\displaystyle (k_{3}=2)}$

Utilizzando la formula, avremo:

${\displaystyle P_{8}^{k_{1},k_{2},k_{3}}={\frac {8!}{2!3!2!}}={\frac {40320}{24}}=1680}$

Dismutazioni

Sono dette dismutazioni le permutazioni prive di punti fissi, il cui valore approssimato è dato da:

${\displaystyle \sum _{i=0}^{n}\left(-1\right)^{i}{\frac {n!}{i!}}\sim {\frac {n!}{e}}}$

Disposizioni (sequenze ordinate)

Disposizioni semplici (senza ripetizioni)

Una disposizione semplice di lunghezza ${\displaystyle k}$ di elementi di un insieme ${\displaystyle S}$ di ${\displaystyle n}$ oggetti, con ${\displaystyle k\leq n}$, è una presentazione ordinata di ${\displaystyle k}$ elementi di ${\displaystyle S}$ nella quale non si possono avere ripetizioni di uno stesso oggetto.

Per avere il numero di queste configurazioni si considera che il primo componente di una tale sequenza può essere scelto in ${\displaystyle n}$ modi diversi, il secondo in ${\displaystyle (n-1)}$ e così via, sino al ${\displaystyle k-}$esimo che può essere scelto in ${\displaystyle (n-k+1)}$ modi diversi. Pertanto il numero ${\displaystyle D_{n,\,k}}$ di disposizioni semplici di ${\displaystyle k}$ oggetti estratti da un insieme di ${\displaystyle n}$ oggetti è dato da:

${\displaystyle D_{n,k}=n\cdot (n-1)\cdot \dots \cdot (n-k+1)={\frac {n\cdot (n-1)\cdot \dots \cdot 1}{(n-k)\cdot (n-k-1)\cdot \dots \cdot 1}}={\frac {n!}{(n-k)!}}}$

Si osserva che le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di ${\displaystyle n}$ oggetti sono le disposizioni semplici di tali oggetti di lunghezza ${\displaystyle n}$. In effetti per il loro numero:

${\displaystyle P_{n}=D_{n,n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}={\frac {n!}{1}}=n!}$^[2]

Esempi

• Le disposizioni semplici di lunghezza 2 degli elementi dell'insieme ${\displaystyle \left\{1,\,2,\,3,\,4,\,5\right\}}$ sono ${\displaystyle {\frac {5!}{(5-2)!}}={\frac {5!}{3!}}={\frac {120}{6}}=20}$, ossia sono i numeri: ${\displaystyle 12,\,13,\,14,\,15,\,21,\,23,\,24,\,25,\,31,\,32,\,34,\,35,\,41,\,42,\,43,\,45,\,51,\,52,\,53,\,54}$.

Disposizioni con ripetizioni

Una presentazione ordinata di elementi di un insieme nella quale si possono avere ripetizioni di uno stesso elemento si dice disposizione con ripetizioni. Si cerchi ora il numero delle possibili sequenze di ${\displaystyle k}$ oggetti estratti dagli elementi di un insieme di ${\displaystyle n}$ oggetti, ognuno dei quali può essere preso più volte. Si hanno ${\displaystyle n}$ possibilità per scegliere il primo componente, ${\displaystyle n}$ per il secondo, altrettante per il terzo e così via, sino al ${\displaystyle k-}$esimo che completa la configurazione. Il numero cercato è pertanto:

${\displaystyle D'_{n,k}={\underbrace {n\cdot n\cdot \dots \cdot n} \atop {k{\mbox{ volte}}}}=n^{k}}$^[6]

Si fa notare che può anche essere ${\displaystyle k>n}$.

Esempi

• Le disposizioni con ripetizione di lunghezza ${\displaystyle 2}$ degli elementi di ${\displaystyle \left\{1,\,2,\,3,\,4,\,5\right\}}$ sono: ${\displaystyle 5^{2}=25}$,

ossia: ${\displaystyle 11,\,12,\,13,\,14,\,15,\,21,\,22,\,23,\,24,\,25,\,31,\,32,\,33,\,34,\,35,\,41,\,42,\,43,\,44,\,45,\,51,\,52,\,53,\,54,\,55}$.

• I byte usati in informatica sono disposizioni di ${\displaystyle 8}$ oggetti sugli elementi ${\displaystyle \left\{0,\,1\right\}}$ che possono quindi assumere ${\displaystyle 2^{8}=256}$ valori distinti: ${\displaystyle 00000000,\,00000001,\,00000010,\,\ldots \,,11111111}$.

Combinazioni (sequenze non ordinate)

Combinazioni semplici (senza ripetizioni)

Si chiama combinazione semplice una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti e non si può ripetere lo stesso elemento più volte. La collezione delle combinazioni di ${\displaystyle k}$ elementi estratti da un insieme ${\displaystyle S}$ di ${\displaystyle n}$ oggetti distinti si può considerare ottenuta dalla collezione delle disposizioni semplici di lunghezza ${\displaystyle k}$ degli elementi di ${\displaystyle S}$ ripartendo tali sequenze nelle classi delle sequenze che presentano lo stesso sottoinsieme di ${\displaystyle S}$ e scegliendo una sola sequenza da ciascuna di queste classi. Ciascuna delle suddette classi di sequenza di lunghezza ${\displaystyle k}$ contiene ${\displaystyle k!}$ sequenze, in quanto accanto a una sequenza ${\displaystyle \sigma }$ si hanno tutte e sole quelle ottenibili permutando i componenti della ${\displaystyle \sigma }$. Quindi il numero delle combinazioni semplici di ${\displaystyle n}$ elementi di lunghezza ${\displaystyle k}$ si ottiene dividendo per ${\displaystyle k!}$ il numero delle disposizioni semplici di ${\displaystyle n}$ elementi di lunghezza ${\displaystyle k}$:

${\displaystyle C_{n,k}={\frac {D_{n,k}}{P_{k}}}={\frac {n!}{k!(n-k)!}}={n \choose k}}$^[2]

Di solito tra le diverse disposizioni semplici di una classe si sceglie come combinazione rappresentativa la sequenza nella quale i componenti compaiono in ordine crescente (tutti gli insiemi finiti possono avere gli elementi ordinati totalmente, ovvero associati biunivocamente ai primi interi positivi).

Esempio

• Le combinazioni semplici di lunghezza ${\displaystyle 4}$ degli elementi di ${\displaystyle \left\{1,\,2,\,3,\,4,\,5,\,6\right\}}$ sono:

${\displaystyle {\frac {6!}{4!(6-4)!}}={\frac {6!}{4!\cdot 2!}}=15}$,

cioè: ${\displaystyle 1234,\,1235,\,1236,\,1245,\,1246,\,1256,\,1345,\,1346,\,1356,\,1456,\,2345,\,2346,\,2356,\,2456,\,3456.}$

Combinazioni con ripetizioni

Quando l'ordine non è importante, ma è possibile avere componenti ripetute, si parla di combinazioni con ripetizione. Il numero di combinazioni con ripetizione di ${\displaystyle n}$ oggetti di classe ${\displaystyle k}$ è uguale a quello delle combinazioni senza ripetizione di ${\displaystyle n+k-1}$ oggetti di classe ${\displaystyle k}$ ed è quindi uguale a:

${\displaystyle C'_{n,k}={\binom {n+k-1}{k}}}$^[2]

Esempio

• Vi sono ${\displaystyle {\binom {2+4-1}{4}}={\binom {5}{4}}=5}$ modi di distribuire a 2 bambini distinguibili 4 caramelle indistinguibili, contando anche i casi in cui uno dei bambini non riceva alcuna caramella: ${\displaystyle 0-4,\,1-3,\,2-2,\,3-1,\,4-0}$. Equivalentemente, le combinazioni con ripetizioni informano sul numero di possibili ${\displaystyle n-}$uple di addendi non negativi la cui somma sia ${\displaystyle k}$ (considerando diverse ${\displaystyle n-}$uple in cui eguali addendi compaiano in ordine differente); nel suddetto esempio, sono mostrate le cinque diverse coppie di somma ${\displaystyle 4}$.

Note

Bibliografia

• Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988, ISBN 978-88-08-03858-6.
• Sheldon M. Ross, Calcolo delle probabilità, Milano, Apogeo, 2013, ISBN 978-88-38-78860-4.

Voci correlate

• Combinatoria
• Permutazione
• Disposizione
• Combinazione
• Dismutazione
• Teorema binomiale
• Fattoriale

Altri progetti

• Wikimedia Commons contiene immagini o altri file sul calcolo combinatorio

Collegamenti esterni

• càlcolo combinatòrio, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• calcolo combinatorio, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

Controllo di autorità	Thesaurus BNCF 25713 · GND (DE) 4031824-2