Esercizi per la maturità: Calcolo combinatorio

Home » Esercizi per la maturità: Calcolo combinatorio

Autori e revisori

Leggi...

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

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 di 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}_1$ R $\mathrm{A}_1\mathrm{T}_2\mathrm{T}_3\mathrm{A}_2$ RE” 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$

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

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$

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.$

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

$\quad$

Esercizio 1 $(\bigstar\bigstar\largewhitestar)$ . Quanti numeri pari di tre cifre diverse possono essere scritti utilizzando le cifre dell’insieme $A= \{1,2,3,4,5,7\}$ ?

Svolgimento.

Il numero richiesto di tre cifre deve essere pari quindi l’ultima cifra deve essere neccesariamente 2 o 4. Quindi mantenendo fisso o il 2 o il 4 abbiamo i seguenti insiemi

$\begin{aligned} &B=\{1,3,4,5,7\}\\ &C=\{1,3,2,5,7\}\\ \end{aligned}$

Si osserva che non ci possono essere ripetizioni ed è importante l’ordine perchè bisogna tenere conto del modo in cui viene letto il numero. Quindi abbiamo a che fare con disposizioni semplici dove $n=5\,\, \text{e}\,\,k=2$ , da cui

$D_{n,k}=5 \cdot 4=20$

Le possibilità sono

$\boxcolorato{superiori}{ 20 \cdot 2=40. }$

Fonte: Moduli di lineamenti di matematica N.Dodero-P.Baroncini-R.Manfredi

Esercizio 2 $(\bigstar\bigstar\largewhitestar)$ . Calcolare quante sigle si possono costruire se per i primi cinque posti utilizziamo tre lettere A e due lettere B e per gli altri cinque posti tre cifre 1 e due cifre zero.

Svolgimento.

Possiamo suddividere l’esercizio considerando i seguenti gruppi:

$\begin{aligned} &\mathcal{G}_1=\{A,A,A,B,B\}\\ &\mathcal{G}_2=\{1,1,1,0,0\}\\ \end{aligned}$

Si osserva che abbiamo a che fare, per entrambi gli insiemi, con una permutazione ed inoltre gli elementi si posso ripetere, quindi sono permutazioni con ripetizione. Si conclude che le possibilità sono

$\boxcolorato{superiori}{ P_{5}^{3,2}=\left(\dfrac{5!}{3! \cdot 2!}\right)^2=10^2=100. }$

Fonte: Moduli di lineamenti di matematica N.Dodero-P.Baroncini-R.Manfredi

Esercizio 3 $(\bigstar\largewhitestar\largewhitestar)$ . Calcolare in quanti modi diversi si possono collocare quattro maglioni in sei cassetti in modo che al massimo in ogni cassetto ci sia un maglione.

Svolgimento.

Si osserva che non è importante l’ordine e che gli elementi non si ripetono. Quindi abbiamo a che fare con una combinazione semplice:

$\boxcolorato{superiori}{ D_{6,4}= \begin{pmatrix} 6\\ 4 \end{pmatrix}= \dfrac{6!}{4!\cdot 2!}=15. }$

Fonte: Moduli di lineamenti di matematica N.Dodero-P.Baroncini-R.Manfredi.

Esercizio 4 $(\bigstar\largewhitestar\largewhitestar)$ . In quanti modi diversi nove persone possono sedersi in una fila di sei posti?

Svolgimento.

Per conoscere il numero di modi in cui nove persone possono occupare sei posti distinti basta osservare che l’operazione si compone di due fasi logiche ma che, dal punto di vista del calcolo, confluiscono in un’unica disposizione semplice senza ripetizione. Si devono infatti selezionare sei persone fra nove e, subito dopo, sistemarle in ordine nei sei posti disponibili: l’ordine è rilevante perché posti diversi producono disposizioni diverse, mentre non è permesso che una stessa persona occupi più di un posto. La formula delle disposizioni semplici $D_{n,k}=n!/(n-k)!$ riassume entrambe le operazioni, perciò con $n=9$ e $k=6$ otteniamo

$D_{9,6}=\frac{9!}{(9-6)!}=\frac{9!}{3!} =9\cdot8\cdot7\cdot6\cdot5\cdot4 =\boxcolorato{superiori}{60\,480.}$

Esercizio 5 $(\bigstar\bigstar\largewhitestar)$ . In un torneo di calcio partecipano diciotto squadre. Quante partite devono essere disputate tra girone di andata e di ritorno, sapendo che ogni squadra incontra tutte le altre due volte?

Svolgimento.

In un campionato con $18$ squadre ogni gara si gioca fra due squadre; per ogni coppia di squadre $\{A,B\}$ si gioca sia l’andata $(A,B)$ (in cui la squadra $A$ gioca in casa) che il ritorno $(B,A)$ , in cui è la squadra $B$ a giocare in casa.

Con questa impostazione, il numero di partite giocate è pari al numero di disposizioni semplici di $2$ squadre scelte in un insieme di $18$ , ossia

$D_{18,2}= 18 \cdot 17 = \boxcolorato{superiori}{306.}$

Esercizio 6 $(\bigstar\bigstar\largewhitestar)$ . Quanti numeri interi di tre cifre, permettendo ripetizioni, si possono formare con gli elementi dell’insieme $B=\{0,2,5,7,9\}$ ?

Svolgimento.

Anche in questo caso occorre contare Per costruire numeri di tre cifre con ripetizione di simboli ammessa, partendo dall’insieme $B=\{0,2,5,7,9\}$ , bisogna distinguere la prima posizione dalle altre due: lo zero non può comparire in testa, altrimenti il numero non avrebbe tre cifre.

Per la prima cifra si hanno quindi $4$ possibili scelte; il numero di stringhe composte da seconda e terza cifra si ottiene mediante il numero di disposizioni con ripetizione di $2$ oggetti scelti tra $5$ , ed è dunque pari a $5^2$ . Moltiplicando tra loro il numero di possibilità, si ottiene che il risultato è

$4 \times 5^2 = \boxcolorato{superiori}{ 100. }$

Esercizio 7 $(\bigstar\largewhitestar\largewhitestar)$ . In un concorso a pronostici si devono prevedere i risultati di cinque partite, ognuna con i tre possibili esiti (1, X, 2). Quante colonne (ossia sequenze di pronostici) si possono compilare?

Svolgimento.

Ogni pronostico è identificabile come una sequenza di $5$ simboli scelti dall’insieme $\{1, X, 2\}$ , che ne contiene $3$ , in cui ovviamente i simboli possono ripetersi. Il numero di pronostici richiesto coincide quindi col numero di disposizioni con ripetizioni di $5$ oggetti scelti tra $3$ , ovvero

$R_{3,5}=3^{5}= \boxcolorato{superiori}{ 243. }$

Esercizio 8 $(\bigstar\bigstar\largewhitestar)$ . Quanti numeri di otto cifre diverse si possono scrivere usando le dieci cifre decimali ( $0,1,\dots,9$ ) se la prima cifra non può essere $0$ ?

Svolgimento.

La prima cifra del numero è una tra $\{1,\dots,9\}$ , dunque può essere decisa in $9$ modi distinti. Per decidere quale stringa di $7$ cifre si possa affiancare a tale primo numero, si può pensare di ordinare le $9$ cifre non ancora utilizzate in un modo qualsiasi e prenderne le prime $7$ . Ricordiamo che $9$ cifre si possono permutare in $P_9=9!$ modi diversi; dato che il modo in cui vengono ordinate le ultime due cifre è indifferente ai fini delle prime $7$ cifre, bisogna dividere $9!$ per il numero $P_2=2!=2$ di tali ordinamenti. In definitiva, il numero richiesto è

$\boxcolorato{superiori}{ 9 \cdot \frac{9!}{2}=1\,632\,960. }$

Esercizio 9 $(\bigstar\bigstar\largewhitestar)$ . A un congresso sette persone devono sedere attorno a un tavolo rotondo.

$\quad$

In quanti modi possono prendere posto, considerando identiche due disposizioni che differiscono solo per una rotazione?

Se invece le persone siedono su una fila rettilinea di sette sedie, in quanti modi si possono disporre?

Svolgimento punto 1.

Immaginiamo che le sedie siano numerate con dei numeri da $1$ a $7$ . I partecipanti si possono disporre sulle $7$ sedie in $P_7=7!$ modi distinti. In tale calcolo abbiamo però considerato distinte delle disposizioni che differiscono solo per una rotazione intorno al tavolo. Poiché ogni configurazione ne genera esattamente $7$ effettuando delle rotazioni, occorre dividere $7!$ per questo fattore. Il numero richiesto è quindi

$\frac{7!}{7} = 6! = \boxcolorato{superiori}{ 720. }$

Svolgimento punto 2.

Se invece i partecipanti siedono in una fila rettilinea, in numero di modi in cui si possono disporre è pari al numero delle permutazioni di $7$ oggetti:

$P_7 = 7! = \boxcolorato{superiori}{5\,040.}$

Esercizio 10 $(\bigstar\largewhitestar\largewhitestar)$ . Calcolare quanti anagrammi (anche privi di significato) si possono ottenere con le parole:

$\text{PRESA}, \qquad \text{CAMPOS}, \qquad \text{RUGBISTA}.$

Svolgimento.

Il numero di anagrammi (anche privi di significato) di una parola costituita da $n$ lettere distinte è pari al numero di permutazioni di tali $n$ oggetti, ossia $P_n=n!$ . Dunque poiché le parole in esame hanno rispettivamente $5$ , $6$ e $8$ lettere, la risposta è

$\boxcolorato{superiori}{ 5!, } \qquad \boxcolorato{superiori}{ 6!, } \qquad \boxcolorato{superiori}{ 8!. }$

Esercizio 11 $(\bigstar\bigstar\largewhitestar)$ . Calcola quanti anagrammi, anche senza significato, si possono fare con le parole:

$\text{SERIE}, \qquad \text{VENTO}, \qquad \text{STATISTA}.$

Svolgimento.

Usiamo la formula (3) dimostrata nei richiami teorici.

$\quad$

Nella parola “SERIE” le consonanti sono distinte, mentre vi sono due lettere “E”. Dunque il numero di anagrammi richiesto è
$\frac{5!}{2!} = \boxcolorato{superiori}{ 60. }$

La parola “VENTO” è costituita da cinque lettere distinte, dunque il numero di anagrammi è dato dal numero di permutazioni di cinque oggetti senza ripetizione:
$\boxcolorato{superiori}{ 5!=120. }$

La parola “STATISTA” è costituita da otto lettere, tra cui vi sono tre lettere “T”, due “S” e due “A”. Il numero di anagrammi di tale parola è quindi
$\frac{8!}{3! \cdot 2! \cdot 2!} = \boxcolorato{superiori}{ 1\,680.}$

Esercizio 12 $(\bigstar\bigstar\largewhitestar)$ . Una moneta viene lanciata dieci volte. In quanti modi si può presentare una successione contenente sette teste e tre croci?

Svolgimento.

I dieci lanci generano una sequenza ordinata di simboli $\mathrm{T}$ (testa) e $\mathrm{C}$ (croce). Al fine di contare le sequenze che contengono esattamente $7$ teste e $3$ croci, si può immaginare di dover permutare un gruppo di $10$ lettere, di cui $7$ sono lettere $T$ e $3$ sono lettere $C$ , pertanto grazie a (3), il numero richiesto è

$\frac{10!}{7! \cdot 3!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2} =\boxcolorato{superiori}{ 120. }$

Esercizio 13 $(\bigstar\bigstar\largewhitestar)$ . Eseguire quanto richiesto per i seguenti binomi:

$\quad$

Calcolare il termine simile a $x^4y^4$ nello sviluppo di $(3x - \frac13\,y)^{8}$ .

Determinare i termini simili rispettivamente a $x^9$ , $x^7$ e $x^4$ nello sviluppo di $(x + 2)^{10}$ .

Calcolare il termine simile a $a^{12}b^3$ nello sviluppo di $(2a^{2} - b)^{9}$ .

Determinare $n$ sapendo che il coefficiente del termine simile a $x^{n-2}y^2$ dello sviluppo di $(x - 3y)^{n}$ è $405$ .

Svolgimento.

Utilizziamo la formula (5) per lo sviluppo della potenza $n$ -esima di un binomio.

Svolgimento punto 1.

er sviluppare $\bigl(3x-\frac13\,y\bigr)^{8}$ , poniamo $a=3x$ , $b=-\frac13\,y$ e $n=8$ in (5). Il termine richiesto corrisponde a $k=4$ :

$\binom{8}{4}(3x)^{8-4} \Bigl(-\frac13\,y\Bigr)^{4} = 70\,x^{4}y^{4}.$

Svolgimento punto 2.

I termini richiesti corrispondono alle scelte $k=1$ , $k=3$ e $k=6$ nella formula (5) con $a=x$ , $b=2$ e $n=10$ :

$\begin{gathered} \binom{10}{1}x^{9}2^{1}=20x^{9},\\[4pt] \binom{10}{3}x^{7}2^{3}=960x^{7},\\[4pt] \binom{10}{6}x^{4}2^{6}=13\,440x^{4}. \end{gathered}$

Svolgimento punto 3.

Al fine di ottenere il monomio simile a $a^{12}b^3$ occorre porre $k=3$ nella formula (5) con $2a^2$ al posto di $a$ , $-b$ al posto di $b$ e $n=9$ :

$\binom{9}{3}(2a^{2})^{6}(-b)^{3} = -5\,376\,a^{12}b^{3}.$

Svolgimento punto 4.

Si pone $k=2$ in (5) con $a=x$ e $b=-3y$ :

$\binom{n}{2} x^{n-2}(-3y)^{2} = \frac{n (n-1) \cdot 3^2}{2} x^{n-2} y^2.$

Imponendo che il coefficiente sia pari a $405$ si ottiene

$\frac{405 \cdot 2}{9} = n(n-1) \iff 90 = n(n-1),$

la cui unica soluzione naturale è $n=10$ .

Esercizio 14 $(\bigstar\bigstar\largewhitestar)$ . Verificare le seguenti identità per $0 \leq k \leq n$ :

$\quad$

$\displaystyle \binom{\,n+1\,}{\,k+1\,} =\frac{n+1}{k+1}\, \binom{\,n\,}{\,k\,}, \qquad$ (formula di ricorrenza);

$\displaystyle \binom{\,n\,}{\,k\,}+\binom{\,n\,}{\,k-1\,} = \binom{\,n+1\,}{\,k\,}, \qquad$ (formula di Stifel o identità di Pascal).

Svolgimento punto 1.

Si ha

$\begin{aligned} \binom{n+1}{k+1} &= \frac{(n+1)!}{(k+1)! \cdot (n+1-k-1)!} \\ &= \frac{(n+1) \cdot n!}{(k+1)\cdot k! \cdot (n-k)!} \\ &= \frac{n+1}{k+1} \frac{n!}{k! \cdot (n-k)!} \\ &= \frac{n+1}{k+1} \binom{n}{k}. \end{aligned}$

Svolgimento punto 2.

Per la seconda identità abbiamo

$\begin{aligned} \binom{n}{k} + \binom{n}{k-1} &= \frac{n!}{k! \cdot (n-k)!} + \frac{n!}{(k-1)! \cdot (n-k+1)!} \\ &= \frac{n!}{k \cdot (k-1)! \cdot (n-k)!} + \frac{n!}{(k-1)! \cdot (n-k+1) \cdot (n-k)!} \\ &= \frac{n!}{(k-1)! \cdot (n-k)!} \left ( \frac{1}{k} + \frac{1}{(n-k+1)}\right ) \\ &= \frac{n!}{(k-1)! \cdot (n-k)!} \cdot \frac{n-k+1 + k}{k(n-k+1)} \\ &= \frac{(n+1) \cdot n!}{k! \cdot (n-k+1)!} \\ &= \binom{n+1}{k}. \end{aligned}$

Esercizio 15 $(\bigstar\bigstar\largewhitestar)$ . Dimostrare che, per $n\ge0$ , vale

$\sum_{k=0}^{n}\binom{n}{k} = 2^{n}.$

Svolgimento.

Ponendo $a=b=1$ nella formula (5) del binomio di Newton si ha

$2^n= (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k}.$

Esercizio 16 $(\bigstar\bigstar\bigstar)$ . Dimostrare che, per $n\ge1$ , vale

$\sum_{\substack{k=0\\ k\ \text{\normalfont pari}}}^{n}\binom{n}{k} = \sum_{\substack{k=0\\ k\ \text{\normalfont dispari}}}^{n}\binom{n}{k} =2^{n-1}.$

Svolgimento.

Ponendo $a=b=1$ nella formula (5) del binomio di Newton si ottiene

(10) $\begin{equation*} 2^n= (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} \cdot 1^k = \sum_{k=0}^{n} \binom{n}{k}. \end{equation*}$

Scegliendo invece $a=1$ e $b=-1$ nella medesima formula si ha

$0= (1-1)^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}.$

Sommando le due equazioni otteniamo

$2^n = \sum_{k=0}^{n} \binom{n}{k}\left ( 1+ (-1)^k \right ) = 2\sum_{\substack{k=0\\ k\ \text{\normalfont pari}}}^{n}\binom{n}{k},$

dove l’ultima uguaglianza è dovuta al fatto che i termini con indice $k$ dispari si annullano poiché $(-1)^k=-1$ , mentre quelli con indice $k$ pari raddoppiano, poiché $(-1)^k=1$ . Dividendo per $2$ si ottiene

(11) $\begin{equation*} \sum_{\substack{k=0\\ k\ \text{\normalfont pari}}}^{n}\binom{n}{k} = 2^{n-1}. \end{equation*}$

Sottraendo (11) da (10) si ottiene

$\sum_{\substack{k=0\\ k\ \text{\normalfont dispari}}}^{n}\binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k} -\sum_{\substack{k=0\\ k\ \text{\normalfont pari}}}^{n}\binom{n}{k} = 2^n- 2^{n-1} = 2^{n-1},$

come volevasi dimostrare.

Esercizio 17 $(\bigstar\largewhitestar\largewhitestar)$ . Quante sestine si possono formare scegliendo 6 numeri tra i settanta di un concorso a premi?

Svolgimento.

Una “sestina” è un sottoinsieme di $6$ numeri scelti fra i $70$ disponibili; l’ordine non conta e non ci sono ripetizioni. Il numero dei possibili sottoinsiemi è quindi pari al numero di combinazioni di 6 elementi scelti tra $70$ , ovvero

$C_{70,6} = \binom{70}{6} = \frac{70!}{6!\,64!} = \frac{70\cdot69\cdot68\cdot67\cdot66\cdot65}{6\cdot5\cdot4\cdot3\cdot2\cdot1} = \boxcolorato{superiori}{131\,115\,985.}$

Esercizio 18 $(\bigstar\largewhitestar\largewhitestar)$ . In quanti modi si possono estrarre tre carte da un mazzo che ne contiene trentadue?

Svolgimento.

L’estrazione di tre carte da un mazzo di $32$ carte, senza reinserimento e senza riguardo all’ordine, corrisponde alla scelta di un sottoinsieme di $3$ carte su $32$ , ovvero a una combinazione semplice di $3$ elementi scelti tra $32$ . Il numero dei possibili modi è dunque

$C_{32,3}= \binom{32}{3} = \frac{32!}{3!\,29!} = \frac{32\cdot31\cdot30}{3\cdot2\cdot1} =\boxcolorato{superiori}{ 4\,960.}$

Esercizio 19 $(\bigstar\largewhitestar\largewhitestar)$ . In quanti modi si possono estrarre quattro carte rosse (cuori o quadri) dalle ventisei normalmente contenute in un mazzo di carte francesi?

Svolgimento.

Dovendo estrarre quattro carte distinte in un gruppo di $26$ e senza riguardo per l’ordine, si tratta di determinare il numero di combinazioni semplici

$C_{26,4}= \binom{26}{4} = \frac{26!}{4!\,22!} = \frac{26\cdot25\cdot24\cdot23}{4\cdot3\cdot2\cdot1} = \boxcolorato{superiori}{ 14\,950.}$

Esercizio 20 $(\bigstar\largewhitestar\largewhitestar)$ . In quanti modi diversi si possono distribuire otto tavolette di cioccolato identiche a sei bambini?

Svolgimento.

Distribuire $k=8$ tavolette di cioccolato identiche a sei bambini equivale a suddividere otto oggetti indistinguibili in $n=6$ gruppi ordinati (eventualmente vuoti). Dalla formula (9) provata nei richiami teorici il numero di suddivisioni è pari a

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

Esercizio 21 $(\bigstar\largewhitestar\largewhitestar)$ . In quanti modi si possono collocare dodici palline uguali in sette urne distinte?

Svolgimento.

Il problema è equivalente a suddividere $k=12$ palline identiche in $n=7$ gruppi ordinati, eventualmente vuoti. Da (9) segue che il numero di modi in cui tale suddivisione può essere effettuata è

$\binom{12 + 7 - 1}{7 - 1} = \binom{18}{6} = \frac{18!}{6!\,12!} = \frac{18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \boxcolorato{superiori}{18\,564.}$

Esercizio 22 $(\bigstar\largewhitestar\largewhitestar)$ . Quanti bouquet di dodici fiori si possono formare scegliendo tra cinque tipi di fiore?

Svolgimento.

Indicando con $x_i$ il numero (eventualmente nullo) di fiori di tipo $i$ , con $i \in \{1,\dots,5\}$ , il problema equivale al numero di modi in cui si può ottenere

$x_1 + x_2 + x_3 + x_4 + x_5 = 12.$

Da (9) si ha che il numero di tali combinazioni è

$\binom{12 + 5 - 1}{5 - 1} = \binom{16}{4} = \frac{16!}{4!\,12!} = \frac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = \boxcolorato{superiori}{1820.}$

Esercizio 23 $(\bigstar\bigstar\largewhitestar)$ . Quanti numeri pari di quattro cifre diverse si possono scrivere utilizzando quelle dell’insieme $A=\{0,1,2,3,4,5,6\}$ ?

Svolgimento.

Un numero di quattro cifre è pari se e solo se la cifra delle unità è una cifra pari. Avendo a disposizione solo gli elementi di $A=\{0,1,2,3,4,5,6\}$ , i valori possibili per l’ultima cifra sono

$0,\,2,\,4,\,6,$

ovvero quattro scelte possibili. I quattro posti sono, in ordine, $\,{\Large\blacksquare}\,{\Large\blacksquare}\,{\Large\blacksquare}\,{\Large\blacksquare}$ . Le cifre devono essere tutte diverse e il primo posto non può essere $0$ . Distinguiamo due casi mutualmente esclusivi, in dipendenza dal fatto se l’ultima cifra sia o meno lo $0$ .

Caso 1 – cifra finale $0$ . Se la cifra finale è lo $0$ , rimangono $6$ scelte possibili per la prima cifra, ovvero tutte gli elementi di $A$ meno lo $0$ . Di conseguenza, rimangono $5$ scelte per la seconda cifra e, dunque, $4$ scelte possibili per la terza. In totale si hanno

$6 \cdot 5 \cdot 4 =120$

possibilità.

Caso 2 – cifra finale diversa da $0$ . Assumiamo che l’ultima cifra sia $2$ , $4$ o $6$ , ossia può essere scelta in $3$ modi distinti. In questo caso, la prima cifra deve essere una delle rimanenti $6$ , escludendo lo $0$ , dunque può essere scelta in $5$ modi distinti. Per la seconda cifra, si hanno a disposizione le $5$ cifre non ancora scelte, senza alcun vincolo ulteriore. Conseguentemente, per la terza cifra si hanno $4$ scelte possibili. In totale vi sono

$3 \cdot 5 \cdot 5 \cdot 4 = 300$

possibilità.

Conteggio totale. Sommando le possibilità dei due casi analizzati, troviamo che i numeri diversi che si possono comporre sono

$120 + 300 = \boxcolorato{superiori}{ 420. }$

Esercizio 24 $(\bigstar\bigstar\largewhitestar)$ . In una scuola vi sono tre classi quarte con rispettivamente $24$ , $20$ e $25$ alunni. Si vuole costituire una rappresentanza formata da due alunni per ciascuna classe. In quanti modi distinti la si può scegliere?

Svolgimento.

Occorre scegliere, da ciascuna classe, un sottoinsieme contenente due alunni, ovvero bisogna calcolare il numero di combinazioni semplici di $2$ elementi scelti rispettivamente tra $24$ , $20$ e tra $25$ alunni, dati dai coefficienti binomiali

$\begin{gathered} \binom{24}{2}= \frac{24\cdot23}{2}=276,\\ \binom{20}{2}= \frac{20\cdot19}{2}=190,\\ \binom{25}{2}= \frac{25\cdot24}{2}=300. \end{gathered}$

Poiché le scelte per le tre classi sono indipendenti, il numero complessivo di rappresentanze è dato dal prodotto di tali quantità, ossia

$\boxcolorato{superiori}{ 276 \cdot 190 \cdot 300. }$

Esercizio 25 $(\bigstar\bigstar\largewhitestar)$ . In un’urna vi sono dodici palline numerate da $1$ a $12$ . Tra queste, quattro sono bianche e le altre sono rosse. Calcolare quante sono le cinquine di numeri da $1$ a $12$ che contengono esattamente una pallina bianca.

Svolgimento.

\begin{proof}[Svolgimento] Vi sono $4$ palline bianche e $8$ rosse. La sola pallina bianca della cinquina può essere selezionata in $4$ modi distinti. Per ciascuna di queste scelte, le restanti quattro palline rosse sono un sottoinsieme di $4$ elementi scelti tra $8$ ; il numero di modi in cui tale sottoinsieme può essere selezionato è dato dalle combinazioni semplici di $4$ elementi scelti tra $8$ e si calcola col coefficiente binomiale

$\binom{8}{4} = \frac{8 \cdot 7 \cdot 6 \cdot 5}{4 \cdot 3 \cdot 2 \cdot 1} = 70.$

Moltiplicando tale numero per i $4$ modi in cui è possibile scegliere la pallina bianca si hanno

$4 \cdot 70 = \boxcolorato{superiori}{ 280 }$

cinquine possibili.

Esercizio 26 $(\bigstar\bigstar\largewhitestar)$ . Quanti numeri naturali di cinque cifre si possono formare usando cinque cifre decimali tutte diverse tra loro?

Svolgimento.

La prima cifra di un numero naturale non può essere lo $0$ e quindi questa può essere scelta in $9$ modi distinti. Per ciascuna di queste scelte, occorre selezionare una stringa ordinata di $4$ cifre distinte, scelte tra le restanti $9$ cifre decimali, ossia una disposizione semplice di $4$ elementi scelti tra $9$ : la seconda cifra può essere scelta in $9$ modi diversi, la terza cifra può essere selezionata tra le restanti $8$ cifre, la quarta cifra può essere scelta in $7$ modi e la quinta in $6$ modi diversi. Moltiplicando tra loro queste possibilità, si ottiene che il numero richiesto è pari a

$\boxcolorato{superiori}{ 9 \cdot 9 \cdot 8 \cdot 7 \cdot 6. }$

Esercizio 27 $(\bigstar\bigstar\largewhitestar)$ . Volendo preparare un panino farcendolo con cinque fette di ingredienti a scelta tra salame, prosciutto, formaggio e verdure. Senza considerare l’ordine degli ingredienti, quanti panini distinti si possono preparare?

Svolgimento.

Indichiamo con $x_{1},x_{2},x_{3},x_{4}$ il numero di fette rispettivamente di salame, prosciutto, formaggio e verdure usato per farcire il panino. Il problema equivale a determinare quante sono le possibili scelte di questi numeri (positivi o nulli) in modo che il totale delle fette sia pari a cinque, ovvero

$x_{1}+x_{2}+x_{3}+x_{4}=5.$

Matematicamente, occorre contare le combinazioni con ripetizione di 5 oggetti distribuiti in 4 classi. Tale conteggio può essere effettuato col metodo illustrato nell’articolo sulle combinazioni con ripetizione, che ricordiamo brevemente qui.

Innanzitutto si ottiene un problema equivalente aggiungendo $1$ a ciascun addendo, di modo che essi diventino tutti strettamente positivi e la loro somma debba essere pari a $9$ . La quantità richiesta è dunque pari al numero di modi di scrivere $9$ come somma di quattro addendi ordinati tutti positivi: immaginiamo a tal fine di avere $9$ stelle, tra cui posizioniamo $3$ barrette in modo da suddividerle in $4$ gruppi distinti (corrispondenti ai quattro addendi), ad esempio

$\star \mid \star \star \mid \star \star \mid \star \star \star \star,$

che corrisponde a $1 + 2 +2+4$ . Il numero di modi in cui tale suddivisione può essere effettuata è pari al numero di sottoinsiemi di $3$ spazi tra gli $8$ spazi totali esistenti tra le stelle:

$\binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \boxcolorato{superiori}{ 56. }$