Italiano
English
Français
Español
16.4. Combinazioni#
Analogamente alle disposizioni, anche le combinazioni descrivono delle tuple di lunghezza prefissata nelle quali occorrono oggetti scelti da un insieme. In questo caso, però, le tuple non sono ordinate: non si tratta di sequenze, bensì di sottoinsiemi dell'insieme di partenza. Pertanto, nel raggruppamento che corrisponde alle combinazioni non è rilevante l'ordine, ma rimane la possibilità di decidere se gli oggetti si possano ripetere oppure no. Le due categorie di combinazioni risultanti sono descritte nei paragrafi che seguono.
16.4.1. Combinazioni semplici#
Quando un oggetto può essere considerato al più una volta, possiamo a tutti gli effetti dire che vi è corrispondenza tra le combinazioni, che vengono dette semplici, e i sottoinsiemi dell'insieme di partenza.
Definizione 6
Consideriamo un insieme \(A = \{ a_1, \ldots, a_n \}\) di \(n\) oggetti e fissiamo un numero naturale \(k \leq n\). Una combinazione semplice (o più semplicemente combinazione) degli \(n\) oggetti in \(k\) posti è una tupla non ordinata \(\{ a_{i_1}, \dots, a_{i_k} \}\) tale che per ogni \(j = 1, \dots, k\) si ha \(a_{i_j} \in A\), e \(a_{i_j} \neq a_{i_l}\) per ogni \(j, l = 1, \dots, k\) con \(j \neq l\). Indichiamo il numero di possibili combinazioni semplici di \(n\) oggetti in \(k\) posti con \(c_{n, k}\).
Indicherò le combinazioni usando le parentesi graffe come delimitatori delle tuple, per sottolineare che l'ordine non è rilevante; inoltre, questa notazione è coerente con il fatto che una combinazione semplice individua un sottoinsieme \(\{ a_{i_1}, \dots, a_{i_k} \}\subseteq A\), così che le descrizioni del sottoinsieme — fatta in modo estensivo — e della combinazione coincidono.
Esempio 15 (Peter Petrelli)
Peter Petrelli è uno dei protagonisti di Heroes, dotato di una straordinaria forma di empatia che gli permette di riprodurre i poteri degli altri supereroi che si trovano nelle sue vicinanze. Ipotizziamo che questo meta-potere sia limitato, e che Peter sia in grado di replicare tre superpoteri alla volta: \(\{ \text{psicocinesi}, \text{telepatia}, \text{invisibilità} \}\) e \(\{ \text{telepatia}, \text{invisibilità}, \text{psicocinesi} \}\) indicano una medesima terna non ordinata, e dunque uno stesso sottoinsieme e una sola combinazione semplice di \(k = 3\) superpoteri. In questo caso, l'insieme da cui estraiamo gli oggetti è l'insieme di tutti i superpoteri, ed è poco rilevante determinarne la cardinalità \(n\).
Per calcolare il numero \(c_{n, k}\) di possibili combinazioni semplici di \(n\) oggetti in \(k\) posti si può sfruttare il legame tra queste e le disposizioni semplici:
ogni combinazione semplice corrisponde a più disposizioni: permutando in tutti i modi possibili i \(k\) oggetti che la compongono si ottengono \(k!\) disposizioni distinte;
di conseguenza, ogni combinazione compare esattamente \(k!\) volte nell'insieme delle \(d_{n, k}\) disposizioni semplici di \(n\) oggetti in \(k\) posti, da cui \(d_{n, k} = c_{n, k} \cdot k!\);
invertendo quetsa relazione si ricava \(c_{n, k} = \frac{d_{n, k}}{k!}\).
Applicando la formula per il calcolo di \(d_{n, k}\) si ottiene infine
Esempio 16 (Peter Petrelli)
Immaginiamo che vi siano in tutto \(n = 477\) possibili superpoteri[1], e che Peter Petrelli (vedi l’Esempio 15) sia in grado di riprodurli tutti. Ciò significa che, a un dato istante, sarà in grado di «ricordarsi» \(c_{477, 3} = \binom{477}{3} = \;\) 17 974 950 diverse configurazioni di tre superpoteri.
16.4.2. Combinazioni con ripetizione#
Quando è possibile inserire uno stesso oggetto più volte in una combinazione, si dice che quest'ultima è una combinazione con ripetizione. In questo caso, la costruzione di una combinazione è analoga a quella di un multiinsieme, una generalizzazione del concetto di insieme nella cui descrizione in forma estensiva gli oggetti possono comparire più volte, così che ogni elemento nel multiinsieme ha anche una molteplicità, intesa come il numero di volte che occorre.
Definizione 7 (Combinazione con ripetizione)
Consideriamo un insieme \(A = \{ a_1, \ldots, a_n \}\) di \(n\) oggetti e fissiamo un numero naturale \(k \in \mathbb N\). Una combinazione semplice (o, più semplicemente, combinazione) degli \(n\) oggetti in \(k\) posti è una tupla non ordinata \(\{ a_{i_1}, \dots, a_{i_k} \}\) tale che per ogni \(j = 1, \dots, k\) si ha \(a_{i_j} \in A\). Indichiamo il numero di tutte le possibili combinazioni con ripetizione di \(n\) oggett in \(k\) posti con \(c_{n, k}\).
Descriverò le combinazioni con ripetizione usando la stessa notazione di quelle semplici, con la differenza che in questo caso la tupla tra parentesi graffe potrà contenere dei doppioni.
Esempio 17
Immaginiamo un ascensore con capienza di quattro persone, pieno di cloni di Dupli-Kate e Multi-Paul (vedi l’Esempio 10), senza che entrambi i gemelli debbano necessariamente essere presenti. La 15 elenca tutti i modi in cui si possono inserire quattro cloni nell'ascensore, dove ogni configurazione corrisponde a una combinazione con ripetizione dei due oggetti \(k\) e \(p\) (Kate e Paul) in quattro posti.
Combinazione |
|---|
\(\{ k, k, k, k \}\) |
\(\{ k, k, k, p \}\) |
\(\{ k, k, p, p \}\) |
\(\{ k, p, p, p \}\) |
\(\{ p, p, p, p \}\) |
Un modo possibile per calcolare il numero \(C_{n, k}\) di combinazioni con ripetizione di \(n\) oggetti di un insieme \(A\) in \(k\) posti consiste nell'associarle univocamente a degli opportuni sottoinsiemi di \(\mathbb N\). Fissata una funzione biunivoca \(r: A \rightarrow \{ 1, \ldots, n \}\), ogni possibile combinazione con ripetizione \(\{ a_{i_1}, \ldots, a_{i_k} \}\) può essere trasformata nell'insieme numerico \(\{r(a_{i_1}), \ldots, r(a_{i_k}) \}\), scambiando ogni elemento con la sua rappresentazione numerica attraverso \(r\). Se indichiamo con \(\sigma^r\) la sequenza ottenuta ordinando quest'ultimo insieme in senso non decrescente, segue che:
\(\sigma^r\) non dipende dal particolare ordine in cui sono elencati gli elementi della combinazione di partenza;
i \(k\) elementi di \(\sigma^r\) sono valori interi compresi tra \(1\) e \(n\), estremi inclusi, ed è possibile che questa sequenza contenga valori contigui che sono identici.
Infine, indichiamo con \(\sigma^r_i\) l’\(i\)-esimo elemento di \(\sigma^r\) e costruiamo un'ultima sequenza
Anche \(\rho\) conterrà \(k\) elementi, ma essi saranno automaticamente ordinati in senso strettamente crescente, perché sono stati ottenuti incrementando di una quantità via via più grande gli elementi di \(\sigma^r\), che è non decrescente. Inoltre, \(\rho\) conterrà valori interi compresi tra \(1\) e \(n + k - 1\), dunque essa può essere messa in corrispondenza biunivoca con un sottoinsieme di \(M = \{ 1, \ldots, n + k - 1 \}\) che contiene \(k\) elementi. Ricapitolando, ogni combinazione con ripetizione di \(n\) oggetti in \(k\) posti può essere messa in relazione con un sottoinsieme di \(M\) di cardinalità \(k\).
D'altro canto, un generico sottoinsieme di \(M\) di cardinalità \(k\) può essere descritto scrivendo i suoi elementi ordinandoli in senso crescente, ottenendo dunque una sequenza \(\rho\). Se ora decrementiamo gli elementi di questa sequenza sottraendo zero al primo elemento, uno al secondo elemento, due al terzo elemento e così via, otteniamo una nuova sequenza \(\sigma^r\) ordinata in senso non decrescente e i cui valori (che possono essere ripetuti), sono compresi tra \(1\) e \(n\) (estremi inclusi). Considerando quindi le preimmagini di questi valori attraverso \(r\) si ottiene una combinazione con ripetizione di \(k\) oggetti di \(A\). Dunque ogni sottoinsieme di \(M\) di \(k\) elementi può essere messo in relazione con una combinazione con ripetizione di \(n\) oggetti in \(k\) posti.
Esempio 18
Riprendendo l’Esempio 17, abbiamo che l'insieme degli oggetti di partenza \(A = \{ k, p \}\), dove \(k\) e \(p\) indicano rispettivamente Kate e Paul, può essere messo in corrispondenza biunivoca con l'insieme \(N = \{ 1, 2 \}\) per esempio ponendo \(r(k) = 2\) e \(r(p) = 1\). La 16 mostra la corrispondenza tra tutte le combinazioni con ripetizione dei due oggetti in \(A\) in quattro posizioni e le sequenze \(\sigma^r\) e \(\rho\).
Combinazione |
\(\sigma^r\) |
\(\rho\) |
|---|---|---|
\(\{ k, k, k, k \}\) |
\(\{ 2, 2, 2, 2 \}\) |
\(\{ 2, 3, 4, 5 \}\) |
\(\{ k, k, k, p \}\) |
\(\{ 1, 2, 2, 2 \}\) |
\(\{ 1, 3, 4, 5 \}\) |
\(\{ k, k, p, p \}\) |
\(\{ 1, 1, 2, 2 \}\) |
\(\{ 1, 2, 4, 5 \}\) |
\(\{ k, p, p, p \}\) |
\(\{ 1, 1, 1, 2 \}\) |
\(\{ 1, 2, 3, 5 \}\) |
\(\{ p, p, p, p \}\) |
\(\{ 1, 1, 1, 1 \}\) |
\(\{ 1, 2, 3, 4 \}\) |
Pertanto, le combinazioni con ripetizione di \(n\) oggetti in \(k\) posti sono in corrispondenza biunivoca con i sottoinsiemi di \(M\) di cardinalità \(k\), e siccome il numero di questi sottoinsiemi è uguale al numero di combinazioni senza ripetizione di \(n + k - 1\) oggetti in \(k\) posti, possiamo concludere che
Vero o falso?#
Analizzate ciascuna delle seguenti affermazioni, che riguardano le combinazioni, e dite se è vera o falsa, motivando il vostro ragionamento. Cliccate su di essa per visualizzare la risposta corretta.
In una combinazione, due selezioni che contengono gli stessi elementi in ordine diverso sono considerate la stessa combinazione.
Vera. Le combinazioni sono tuple non ordinate: l'ordine degli elementi non è rilevante. Come illustrato nell'Esempio 15, \(\{\text{psicocinesi}, \text{telepatia}, \text{invisibilità}\}\) e \(\{\text{telepatia}, \text{invisibilità}, \text{psicocinesi}\}\) indicano la medesima terna di superpoteri e dunque una sola combinazione semplice. Questa è la differenza fondamentale rispetto alle disposizioni.
Il numero di combinazioni semplici di \(n\) oggetti in \(k\) posti coincide con il numero di disposizioni semplici degli stessi oggetti negli stessi posti.
Falsa. Le disposizioni tengono conto dell'ordine, le combinazioni no. Ogni combinazione di \(k\) oggetti corrisponde a \(k!\) disposizioni distinte (le permutazioni dei suoi elementi), per cui \(d_{n,k} = c_{n,k} \cdot k!\), ovvero \(c_{n,k} = d_{n,k}/k!\). Le combinazioni sono quindi sempre in numero minore (o uguale, per \(k \leq 1\)) rispetto alle disposizioni.
Il numero di combinazioni semplici di \(n\) oggetti in \(k\) posti è \(\binom{n}{k}\).
Vera. Dalla relazione \(d_{n,k} = c_{n,k} \cdot k!\) si ricava \(c_{n,k} = d_{n,k}/k! = \frac{n!}{(n-k)!\,k!} = \binom{n}{k}\). Il coefficiente binomiale conta esattamente il numero di sottoinsiemi di cardinalità \(k\) che si possono formare a partire da un insieme di \(n\) elementi.
Se \(k = n\), il numero di combinazioni semplici di \(n\) oggetti è \(n!\).
Falsa. Quando \(k = n\), l'unica combinazione possibile è l'intero insieme di partenza: \(c_{n,n} = \binom{n}{n} = 1\). Scegliere tutti gli \(n\) oggetti da un insieme di \(n\) elementi si può fare in un solo modo, indipendentemente da \(n\). Il valore \(n!\) è invece il numero di permutazioni (o di disposizioni semplici con \(k = n\)), nelle quali l'ordine è rilevante.
Ogni combinazione semplice di \(k\) oggetti corrisponde a esattamente \(k!\) disposizioni semplici.
Vera. Fissata una combinazione \(\{a_{i_1}, \dots, a_{i_k}\}\), si possono ottenere tutte le sequenze ordinate dei suoi \(k\) elementi permutandoli in tutti i modi possibili: le permutazioni di \(k\) oggetti sono \(k!\), e ognuna dà una disposizione semplice distinta. È proprio partendo da questa relazione (\(d_{n,k} = c_{n,k} \cdot k!\)) che si ricava la formula di \(c_{n,k}\).
Le combinazioni con ripetizione di \(n\) oggetti in \(k\) posti si contano come \(\binom{n+k-1}{k}\).
Vera. Ogni combinazione con ripetizione di \(n\) oggetti in \(k\) posti può essere messa in corrispondenza biunivoca con un sottoinsieme di cardinalità \(k\) dell'insieme \(\{1, \ldots, n+k-1\}\). Il numero di tali sottoinsiemi è \(c_{n+k-1,\,k} = \binom{n+k-1}{k}\), da cui \(C_{n,k} = \binom{n+k-1}{k}\).
16.4.3. Esercizi#
Esercizio 63 (••)
Dato l'insieme \(A = \{ a_1,\dots a_n \}\) e indicato con \(\mathcal{P}(A)\) l'insieme delle parti di \(A\), calcolare la cardinalità di \(\mathcal{P}(A)\).
Solution to Esercizio 63 (••)
Ricordiamo che l'insieme delle parti \(\mathcal{P}(A)\) è l'insieme di tutti i sottinsiemi propri e impropri di \(A\): contiene l'insieme vuoto, tutti i sottinsiemi costituiti da un solo elemento di \(A\), tutti i sottinsiemi costituiti da due soli elementi di \(A\) e così via, e contiene anche \(A\) stesso.
Siccome il numero di sottinsiemi costituiti da \(k\) elementi è \(c_{n,k}=\binom{n}{k}\), si ha che la cardinalità di \(\mathcal{P}(A)\) è \(|\mathcal{P}(A)| = 1 + \sum_{k=1}^{n} \binom{n}{k}\), dove il primo addendo è dovuto alla presenza dell'insieme vuoto. Sfruttando le proprietà del coefficiente binomiale otteniamo
dove nell'ultimo passaggio abbiamo utilizzato la formula del binomio di Newton: \((a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^k b^{n-k}\), ponendo \(a=1\) e \(b=1\).
Questo esercizio si può risolvere anche nel modo seguente: se rappresentiamo ogni sottinsieme \(S\) di \(A\) come una \(n\)-upla di elementi binari, in cui nella posizione \(i\)-esima compare il simbolo \(1\) se l'elemento \(a_i\) appartiene a \(S\) e il simbolo \(0\) se l'elemento \(a_i\) non vi appartiene, allora l'insieme delle parti \(\mathcal{P}(A)\) è l'insieme di tutte le \(n\)-uple che costruire a partire dai due simboli \(0\) e \(1\). Quindi
Esercizio 64 (••)
La Justice League deve selezionare una squadra di intervento rapido composta da quattro membri, scegliendoli tra dieci candidati. In quanti modi distinti si può formare la squadra?
Solution to Esercizio 64 (••)
Si tratta di scegliere quattro eroi tra dieci, senza ordine e senza ripetizione. Ciò si può fare in \(c_{10,4} = \binom{10}{4} = 210\) modi.
Esercizio 65 (••)
Gli X-Men devono formare un team di cinque membri su dodici disponibili. Il Professor X deve essere necessariamente incluso. Quante squadre diverse sono possibili?
Solution to Esercizio 65 (••)
Se il Professor X non può mancare, vanno scelti quattro membri tra i rimanenti undici. Il numero di squadre è quindi \(c_{11,4} = \binom{11}{4} = 330\).
Esercizio 66 (•••)
I Defenders hanno nove candidati per una missione alla quale devono partecipare quattro elementi. In quanti modi si può formare la squadra se Daredevil e Jessica Jones non possono comparire insieme?
Solution to Esercizio 66 (•••)
Senza vincoli, le squadre possibili sarebbero \(c_{9, 4} = \binom{9}{4} = 126\). D'altro canto, le squadre in cui sono presenti sia Daredevil che Jessica Jones si contano nel modo seguente: fissata la coppia, vanno scelti altri due membri tra i restanti sette, e questo si può fare in \(c_{7,2} = \binom{7}{2} = 21\) modi. Le squadre valide sono quindi \(126 - 21 = 105\).
Esercizio 67 (••)
I Guardiani della Galassia stanno equipaggiando la Milano (la loro astronave) per una missione. A bordo ci sono cinque alloggiamenti disponibili, ognuno dei quali può essere occupato da uno tra quattro tipi di dispositivo: cannoni laser, scudi energetici, sensori di rilevamento e moduli di supporto vitale. Calcolate il numero di modi diversi per configurare la Milano, tenendo conto che ogni dispositivo può essere installato più volte e che interessa solo quanti dispositivi di ciascun tipo vengono installati (non in quali alloggiamenti specifici).
Solution to Esercizio 67 (••)
A ogni configurazione corrisponde una e una sola combinazione con ripetizione di quattro oggetti (i tipi di dispositivi) in cinque posti (gli alloggiamenti), per un totale di \(C_{4,5} = \binom{4+5-1}{5} = \binom{8}{5} = 56\) configurazioni possibili.
Esercizio 68 (•)
Gli Avengers vogliono scegliere quattro Gemme dell'Infinito tra le sei disponibili, per studiarne il comportamento. Tuttavia, le gemme del Tempo e della Realtà devono essere studiate insieme, perché modificare la sequenza degli eventi senza aggiornare lo stato della realtà può generare incoerenze logiche e paradossi. Quindi queste due gemme devono essere entrambe selezionate, oppure escluse dal gruppo. Calcolate il numero di configurazioni diverse di gemme che possono venire prese in considerazione.
Solution to Esercizio 68 (•)
Siccome le gemme del Tempo e della Realtà devono essere considerate insieme, oppure completamente escluse, possiamo considerare separatamente i due casi, calcolando il numero di scelte possibili e poi sommando.
Ci sono \(c_{4, 2} = \binom{4}{2} = 6\) configurazioni che contengono le due gemme, perché una volta fissate quelle del Tempo e della Realtà, per completare il gruppo bisogna selezionare un sottoinsieme di due elementi dalle quattro gemme rimanenti.
Intuitivamente, se si escludono le due gemme in questione, ne rimangono esattamente quattro, che quindi dovranno essere tutte selezionate. Infatti, in questo caso vanno considerate le combinazioni di queste quattro gemme in quattro posti, che sono \(c_{4, 4} = 1\).
Concludendo, ci sono sette modi possibili di selezionare le gemme per studiarle.
Esercizio 69 (•••)
Batman deve preparare una cintura scegliendo quattro gadget da un elenco di otto, ma due gadget (la granata accecante e il visore notturno) sono incompatibili e non possono essere inclusi insieme. In quanti modi può scegliere la dotazione?
Solution to Esercizio 69 (•••)
Se non ci fosse il vincolo di incompatibilità, le dotazioni sarebbero descritte dalle combinazioni di otto gadget in gruppi di quattro, per un totale di \(c_{8, 4} = \binom{8}{4} = 70\) casi. Da questi dobbiamo sottrarre le configurazioni non permesse. In tali configurazioni, due scelte sono già occupate dalla granata e dal visore, quindi il loro numero coincide con il numero di combinazioni dei sei gadget residui in gruppi di due, cioè \(c_{6, 2} = \binom{6}{2} = 15\). Il totale valido è quindi \(70 - 15 = 55\).
16.4.4. Concetti fondamentali#
Pensate ai concetti fondamentali illustrati in questo paragrafo ed elencateli. Nella lista qui sotto sono già presenti gli stessi concetti, ma nascosti. Cliccate sul pulsante per mostrarli sotto forma di parole chiave, quindi confrontateli con la vostra lista. Provate infine a descrivere ciascun concetto con parole vostre.