Prezzi Registrazione Login
Qui si risolve LOGO
a

Menu

M

Chiudi

Esercizi su combinazioni con ripetizione

Combinazioni

Home » Esercizi su combinazioni con ripetizione

 
 

Sommario

Leggi...

Raccolta di esercizi sulle combinazioni con ripetizione.

 
 

Autori e revisori

Leggi...

Autori: Valerio Brunetti.

Revisori: Daniele Volpe, Luigi De Masi.


 
 

Notazioni

Leggi...

\mathbb{N}    Insieme dei numeri naturali: 0,1,2,\dots;
n!    Fattoriale del numero naturale n, ossia il prodotto dei numeri naturali da 1 a n; si pone 0!=1;
\displaystyle \binom{n}{k}    Coefficiente binomiale n su k.


 
 

Introduzione

Leggi...

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; \item 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 illustreremo di seguito.


 
 

Richiami di teoria

Leggi...

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:

  • 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\]

  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:

    (1) \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. 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

    (2) \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\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 (2) 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 2 (\bigstar\largewhitestar\largewhitestar). Calcolare in quanti modi si possono distribuire cinque caramelle identiche a quattro bambini.

Svolgimento.

Il problema equivale a determinare il numero di modi in cui si può ottenere k=5 come somma di n=4 addendi eventualmente nulli. Da (2) si ottiene che il numero di tali possibilità è

\[ \binom{5 + 4 - 1}{4 - 1} = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1} = \boxcolorato{superiori}{56.} \]


 
 

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

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