Prezzi Registrazione Login
Qui si risolve LOGO
a

Menu

M

Chiudi

Esercizi misti sul calcolo combinatorio per la preparazione alla maturità

Preparazione alla maturità

Home » Esercizi misti sul calcolo combinatorio per la preparazione alla maturità

 
 

Autori e revisori

Leggi...

Autori: Daniele Bjørn Malesani, Valerio Brunetti, Donato Ciampa, Federico Fallucca.

Revisori: Sergio Fiorucci.


 
 

Introduzione

Leggi...

In questo articolo proponiamo 27 esercizi di ripasso sul calcolo combinatorio in vista dell’esame di maturità. Il calcolo combinatorio costituisce un importante requisito e un utile strumento per il maturando, che spesso trova nelle tracce dell’esame di maturità alcuni problemi che possono essere risolti con l’ausilio di queste tecniche.

Per questa ragione, proponiamo questi esercizi, raccolti a grandi linee per argomenti e completamente risolti, insieme a dei richiami teorici su ciascuno degli strumenti che utilizziamo.


 
 

Richiami di teoria

Disposizioni semplici.

Il concetto di disposizione semplice, come suggerito dal nome stesso, consiste nel disporre n oggetti in k posti distinti, senza che vi siano delle ripetizioni, cioè in modo che ogni oggetto occupi al più un posto. In generale, dunque, vale n \geq k.

Ad esempio, quante parole di k=3 lettere possono comporsi usando le n=5 presenti in “LIBRO”, ciascuna al più una volta sola? La risposta è semplice: per la prima lettera si hanno 5 scelte distinte; per ciascuna di tali scelte, la seconda lettera della parola può essere scelta in 4 modi diversi; infine, per ciascuna delle 5\cdot 4=20 scelte delle prime due lettere, si hanno 3 scelte diverse per la terza lettera. In definitiva, il numero richiesto è

\[ 5 \cdot 4 \cdot 3= 60. \]

Nel caso generale di disporre k oggetti scelti in un insieme di n oggetti, il ragionamento è identico: n scelte per l’oggetto da porre nella posizione 1, n-1 scelte per l’oggetto da porre nella posizione 2, …, fino a n-k+1 scelte per l’oggetto da porre nella posizione k. Quindi il numero totale di disposizioni di k oggetti scelti in un insieme di n è

(1) \begin{equation*} \boxcolorato{superiori}{ D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdots (n-k+1). } \end{equation*}

Si può riscrivere questa formula in maniera più compatta moltiplicando e dividendo per i fattori necessari a ottenere il prodotto dei numeri da 1 a n:

\[ D_{n,k} = n \cdot (n-1) \cdot (n-2) \cdots (n-k+1) \cdot \frac{(n-k) \cdot (n-k-1) \cdots 2 \cdot 1}{(n-k) \cdot (n-k-1) \cdots 2 \cdot 1} = \frac{n!}{(n-k)!}. \]

Ricordando che il prodotto dei numeri naturali da 1 a n si chiama fattoriale di n e si indica col simbolo n!, si può dedurne la formula

(2) \begin{equation*} \boxcolorato{superiori}{ D_{n,k} = \frac{n!}{(n-k)!}. } \end{equation*}

Osserviamo che, in virtù del ragionamento fatto, il numero di disposizioni semplici di k oggetti scelti tra un insieme di n è pari al numero di funzioni iniettive da un insieme di cardinalità k a un insieme con n elementi.


Disposizioni con ripetizione.

Le disposizioni con ripetizione di k oggetti scelti da un insieme di n oggetti, consistono nei modi di scegliere appunto k oggetti, da un gruppo che ne contiene n, potendo selezionare più volte lo stesso oggetto. Dunque, poiché per il primo oggetto si hanno n scelte, per il secondo oggetto si hanno nuovamente a disposizione n scelte diverse, e così via fino al k-esimo oggetto, il numero delle disposizioni con ripetizione di k oggetti, scelti tra n, è pari a

\[\boxcolorato{superiori}{ R_{n,k}= n^k. } \]

Dal ragionamento appena fatto, si vede che R_{n,k} coincide col numero delle funzioni da un insieme con k elementi a valori in un insieme di n elementi.


Permutazioni.

Una permutazione di n oggetti distinti consiste in un loro particolare ordinamento, ossia costruire una “stringa” ordinata costituita dagli n oggetti. Se essi sono tutti distinti, si parla di permutazione semplice e il numero di tali riordinamenti si vede subito essere pari a

\[ n!=n \cdot (n-1) \cdots 2 \cdot 1, \]

in quanto il primo oggetto può essere scelto in n modi, per ciascuna di tali scelte il secondo oggetto può essere scelto in n-1 modi, e così via, fino all’ultimo oggetto che può essere scelto in un unico modo in quanto è l’ultimo rimasto.

Se invece tra gli oggetti da riordinare ve ne sono però alcuni identici, o che è possibile considerare intercambiabili, si parla di permutazioni con ripetizione. Il ragionamento appena concluso non produce il numero corretto dei riordinamenti: ad esempio l’unico numero che si può formare con due cifre 6 è 66, mentre con le cifre 4 e 5 si possono formare i numeri 45 e 54.

In questo caso è semplice effettuare il calcolo, ma come calcolare, ad esempio, il numero di anagrammi della parola “TRATTARE”, in cui si presentano tre lettere “T” e due “A”?

Supponiamo per un attimo che le tre “T” e le due “A” siano distinte tra loro, ovvero chiamiamole \mathrm{T}_1, \mathrm{T}_2 e \mathrm{T}_3 le tre “T” e \mathrm{A}_1 e \mathrm{A}_2 le due “A”.

Per lo stesso ragionamento di prima, le permutazioni delle otto lettere “\mathrm{T}_1R\mathrm{A}_1\mathrm{T}_2\mathrm{T}_3\mathrm{A}_2RE” sono 8!. In questo computo, abbiamo considerato diversi gli anagrammi che differiscono solo per un riordinamento delle tre lettere “T” e le due “A”. Occorre quindi determinare quanti sono questi “doppioni” di ciascun anagramma e dividere 8! per tale numero. A tal fine, osserviamo che, fissato un anagramma, le tre “T” si possono riordinare in 3! modi distinti; per ciascuno di tali riordinamenti, le due “A” si possono riordinare in 2 modi distinti. Moltiplicando tra loro queste possibilità indipendenti, otteniamo che, da ciascun riordinamento, gli anagrammi che differiscono solo per le posizioni dei pedici sono 3! \cdot 2!= 12.

Concludiamo che gli anagrammi della parola trattare sono

\[ \frac{8!}{3! \cdot 2!}. \]

Generalizzando, avendo a disposizione n oggetti tra cui vi sono k gruppi, ciascuno dei quali sia costituito da m_1,\dots m_k oggetti identici, il numero di permutazioni con ripetizione di tali oggetti è

(3) \begin{equation*} \boxcolorato{superiori}{ \frac{n!}{(m_1)! \cdots (m_k)!}. } \end{equation*}


Coefficiente binomiale.

Il coefficiente binomiale è un importante strumento del calcolo combinatorio: dati n e k con 0 \leq k \leq n esso è definito come

(4) \begin{equation*} \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!} \end{equation*}

e rappresenta, come il nome stesso suggerisce, il coefficiente che, nello sviluppo del binomio (a+b)^n, possiede il termine a^{n-k} b^k. Ciò conduce alla formulazione dell’equazione nota come binomio di Newton:

(5) \begin{equation*} (a+b)^n = \sum_{k=0}^{n} \binom{n}{k}a^{n-k} b^{k}. \end{equation*}

La nozione di coefficiente binomiale, oltre alla sua utilità algebrica, deve la sua continua presenza nella matematica alle numerose proprietà combinatorie che descrive: il numero di sottoinsiemi di k elementi di un insieme avente n elementi è dato proprio dal coefficiente binomiale \binom{n}{k}, come si può vedere nell’articolo sulle combinazioni semplici. Poiché, come è noto 2^n= \sum_{k=0}^n \binom{n}{k}, tale interpretazione di \binom{n}{k} implica che 2^n è il numero dei sottoinsiemi di un insieme di n elementi, ossia la cardinalità del suo insieme delle parti.


Combinazioni semplici.

Una combinazione semplice di k elementi scelti in un insieme A che ne contiene n, con 0 \leq k \leq n, è un sottoinsieme di A costituito da k elementi distinti. Questa idea si applica a numerose situazioni pratiche in cui occorre selezionare alcuni elementi di un insieme senza riguardo all’ordine in cui questi sono scelti, ad esempio dovendo selezionare una squadra di 5 persone tra 8, oppure nel caso delle estrazioni del lotto, dove contano solamente i numeri estratti (tutti distinti) e non il loro ordine.

Un interessante problema del calcolo combinatorio consiste nel determinare il numero C_{n,k} di tali combinazioni: fissati n e k, quante sono le combinazioni semplici di k elementi scelti tra n disponibili? Si può ragionare in primo luogo considerando anche l’ordine di scelta: il primo elemento può essere scelto in n modi; il secondo, dovendo essere diverso dal primo, può essere scelto in (n-1) modi, e così via, fino al k-esimo, che può essere scelto in n-k+1 modi diversi. Si hanno cioè n(n-1) \cdots (n-k+1) modi diversi di selezionare questo sottoinsieme “ordinato” (detto anche disposizione semplice).

In questo modo, però, stiamo considerando distinti due sottoinsiemi che differiscono solo per l’ordine di scelta degli elementi. Poiché ogni insieme di k elementi può essere ordinato (o permutato) in k! modi diversi, per determinare il numero di combinazioni cercato occorre dividere n(n-1) \cdots (n-k+1) per k!, ossia:

(6) \begin{equation*} C_{n,k} = \frac{n(n-1) \cdots (n-k+1)}{k!}. \end{equation*}

Moltiplicando numeratore e denominatore per (n-k)!, al numeratore si ottiene il fattoriale di n e la formula diventa

(7) \begin{equation*} \boxcolorato{superiori}{ C_{n,k} = \frac{n!}{k! \cdot (n-k)!} = \binom{n}{k}, } \end{equation*}

dove il simbolo \binom{n}{k} è detto coefficiente binomiale di n su k. Come osservato anche nell’articolo sui coefficienti binomiali, poiché \sum_{k=0}^n \binom{n}{k}=2^n, la formula (7) implica che il numero totale di sottoinsiemi (senza vincoli sulla cardinalità) di un insieme di n elementi è pari a 2^n.


Combinazioni con ripetizione.

Una combinazione con ripetizione di k elementi scelti tra n è il modo di scegliere, partendo da un campione di n elementi, k di essi non necessariamente distinti. I casi tipici di tale problema sono i seguenti (equivalenti tra loro):

\[\quad\]

  • disporre k oggetti identici in n scatole distinte, in modo che ogni scatola contenga nessuno, uno o più oggetti;

    •  

  • suddividere una stringa di k oggetti in n gruppi, ciascuno costituito da 0 o più elementi;

    •  

  • determinare n numeri non-negativi la cui somma sia pari a k:

    \[ x_1+ x_2+ \cdots + x_n= k. \]

Determinare il numero di tali combinazioni è un interessante problema del calcolo combinatorio, che può essere agevolmente risolto come ci accingiamo a illustrare.

Come abbiamo detto, tutti i problemi sopra elencati sono tra loro equivalenti, come si può verificare ragionandoci un attimo. Osserviamo che il problema può richiedere:

\[\quad\]

  1. che ciascuno degli n gruppi debba essere non vuoto, nel qual caso ovviamente deve aversi n \leq k;

    2.  

  2. oppure che i gruppi possono anche essere vuoti, nel qual caso n e k non devono avere alcuna relazione d’ordine.

Vediamo come calcolare il numero di combinazioni in entrambe le configurazioni.

\[\quad\]

  1. Addendi positivi. Cominciamo dal caso in cui i gruppi devono contenere almeno un elemento. Consideriamo la stringa di k oggetti, che possiamo pensare come stelle, e suddividiamo in n gruppi posizionando n-1 barrette tra di essi. Il problema viene perciò detto stars and bars. Poiché i gruppi non devono essere vuoti, le barrette devono essere messe in posizioni distinte e, dato che tra k oggetti vi sono k-1 spazi vuoti, il problema è equivalente a quello di scegliere n-1 oggetti distinti in un insieme di k-1. In altre parole, il problema equivale al numero di combinazioni semplici di n-1 elementi scelti tra k-1:

    (8) \begin{equation*} \boxcolorato{superiori}{ \binom{k-1}{n-1} = \frac{(k-1)!}{(n-1)! \cdot (k-n)!}.} \end{equation*}

    Tale ragionamento concorda col fatto che in questa fattispecie si deve avere n \leq k.

    Facciamo un esempio: vogliamo determinare in quanti modi il numero 7 può essere ottenuto come somma di 3 numeri positivi x_1, x_2 e x_3. Si tratta di suddividere una stringa di 7 stelle in 3 gruppi, piazzando 2 barrette in 2 posizioni intermedie distinte, ad esempio

    \[ \star \star \mid \star \mid \star \star \star \star. \]

    In questa configurazione, ad esempio x_1=2, x_2=1 e x_3=4. Poiché tra le 7 stelle vi sono 6 spazi vuoti, il numero di modi di effettuare la suddivisione corrisponde a scegliere alle combinazioni di 2 posizioni in un set di 6, ovvero

    \[ \binom{6}{2} = \frac{6 \cdot 5}{2} = 15. \]

    2.  

  2. Addendi non-negativi. Il caso in cui ciascuno degli n gruppi può anche essere vuoto può teoricamente essere trattato con una tecnica analoga. In questa configurazione, si hanno k stelle e occorre posizionare n-1 barrette tra di esse. Osserviamo però che, poiché ognuno degli n gruppi può anche essere vuoto, le barrette possono essere posizionate anche prima della prima stella e dopo l’ultima, ossia in k+1 posizioni distinte, e inoltre possono esserci più barrette nella stessa posizione. Facciamo un esempio: vogliamo ottenere il numero 8 come somma di 6 addendi non-negativi x_1, x_2, x_3, x_4, x_5 e x_6 Come abbiamo detto posizioniamo 5 barrette tra le 8 stelle:

    \[ \mid \mid \star \star \mid \star \mid \mid \star \star \star \star. \]

    In questa configurazione si ha x_1=0, x_2=0, x_3=2, x_4=1, x_5=0 e x_6=4.

    Come calcolare il numero di tali configurazioni? Le combinazioni semplici non sembrano essere più di aiuto, poiché più barrette possono occupare la medesima posizione.

    C’è però un artificio che consente di ricondursi al caso precedente: i gruppi vuoti possono essere ottenuti a partire da gruppi non vuoti sottraendo 1. In altre parole, se a ogni addendo si aggiunge 1, si ottengono n addendi strettamente positivi la cui somma è pari a n+k. Il problema è cioè equivalente a quello di ottenere n+k come somma di n addendi strettamente positivi. Il numero di modi in cui ciò può essere eseguito è pari a

    (9) \begin{equation*} \boxcolorato{superiori}{ \binom{k+n-1}{n-1} = \frac{(k+n-1)!}{(n-1)!\cdot k!}.} \end{equation*}

    Nell’esempio precedente dunque, il numero di modi in cui si può ottenere k=8 come somma di n=6 addendi non-negativi è

    \[ \binom{8+6-1}{5} = \frac{13!}{5! \cdot 8!} = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}{5 \cdot 4 \cdot 3 \cdot 2} = 1287. \]

Con ragionamenti simili si possono ad esempio trattare anche i problemi in cui ciascun addendo deve essere maggiore o uguale a una quantità fissata diversa da 0 o 1.


 
 

Esercizi

Questa parte è riservata agli abbonati

per continuare a leggere, attiva un abbonamento.

• Mensile: 7,99€ / mese • Trimestrale: 19,99€ / 3 mesi • Annuale: 79,99€ / anno

Attiva abbonamento

Già abbonato? Accedi