Calcolo Combinatorio: Esercizi Risolti Spiegati Passo Passo (Disposizioni, Inclusione-Esclusione)

Cerca nel sito

Altri risultati..

Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

Cerca nelle Categorie

Esercizi Calcolo Combinatorio

Esercizi e Principi di Calcolo Combinatorio

Di seguito sono presentati alcuni esercizi di calcolo combinatorio con soluzioni e approfondimenti sui principi teorici utilizzati.


👉Calcolo Combinatorio: Esercizi Risolti, Formule e Spiegazioni Dettagliate

Esercizio 1: Codici alfanumerici con vincoli

Problema:

Quanti codici alfanumerici di 4 caratteri si possono formare usando:

  • Lettere maiuscole (A-Z, 26 lettere),
  • Cifre (0-9, 10 cifre),

con i vincoli:

  • Il primo carattere è una lettera.
  • L’ultimo carattere è una cifra pari (0, 2, 4, 6, 8).

Soluzione:

Analizziamo le possibilità per ciascuna delle 4 posizioni del codice:

  • Primo carattere: Deve essere una lettera. Ci sono [math]26[/math] scelte.
  • Secondo e terzo carattere: Possono essere una lettera o una cifra. Il totale di opzioni è 26 + 10 = [math]36[/math] scelte per ciascuna di queste due posizioni.
  • Quarto carattere: Deve essere una cifra pari. Le cifre pari sono 0, 2, 4, 6, 8, quindi ci sono [math]5[/math] scelte.

Poiché la scelta per ogni posizione è indipendente dalle altre, applichiamo il principio di moltiplicazione per trovare il numero totale di codici possibili:

[math]26 \times 36 \times 36 \times 5 = 168.480[/math]

Risposta:

Si possono formare [math]168.480[/math] codici alfanumerici che rispettano i vincoli dati.

Approfondimento teorico:

  • Principio di Moltiplicazione: Se un evento può accadere in [math]m[/math] modi e un secondo evento può accadere in [math]n[/math] modi indipendentemente dal primo, allora i due eventi possono accadere in sequenza in [math]m \times n[/math] modi.
  • Disposizioni con ripetizione: Riguardano gli ordinamenti di [math]k[/math] elementi scelti da un insieme di [math]n[/math] elementi, dove l’ordine conta e gli elementi possono ripetersi. La formula generale è [math]n^k[/math], dove [math]n[/math] è il numero di opzioni disponibili per ogni “posto” e [math]k[/math] è il numero totale di “posti” nella sequenza. Nell’esercizio, il secondo e terzo carattere sono disposizioni con ripetizione ([math]36^2[/math]), ma il problema generale combina questo con scelte vincolate per le altre posizioni.

Esercizio 2: Password con vincoli

Problema:

Quante password di 6 caratteri si possono formare con:

  • Lettere minuscole (a-z, 26),
  • Cifre (0-9, 10),
  • Simboli speciali (!, @, #, 3 simboli),

sapendo che devono contenere almeno un simbolo e almeno una cifra?

Soluzione:

Utilizziamo il principio di inclusione-esclusione. Calcoliamo il numero totale di password possibili e sottraiamo quelle che non soddisfano i vincoli.

Il set totale di caratteri disponibili è 26 (lettere) + 10 (cifre) + 3 (simboli) = [math]39[/math]. Le password sono lunghe 6 caratteri, con ripetizione ammessa.

  • Totale senza vincoli: Il numero totale di password possibili è [math]39^6[/math].
  • Casi da escludere: Dobbiamo escludere le password che:
    • Non contengono simboli: Possono usare solo lettere e cifre (26 + 10 = 36 caratteri). Ci sono [math]36^6[/math] tali password.
    • Non contengono cifre: Possono usare solo lettere e simboli (26 + 3 = 29 caratteri). Ci sono [math]29^6[/math] tali password.

Le password che non contengono simboli E non contengono cifre sono quelle composte solo da lettere (26 caratteri). Ci sono [math]26^6[/math] tali password. Queste sono state sottratte due volte nei passi precedenti (una volta nel set “senza simboli” e una volta nel set “senza cifre”).

Applichiamo il principio di inclusione-esclusione per trovare il numero di password valide (che contengono almeno un simbolo E almeno una cifra). Questo è il Totale meno (Senza Simboli) meno (Senza Cifre) più (Senza Simboli E Senza Cifre):

[math]39^6 – 36^6 – 29^6 + 26^6[/math]

Calcoliamo i valori e il risultato:

[math]39^6 = 3.518.743.761[/math]

[math]36^6 = 2.176.782.336[/math]

[math]29^6 = 594.823.321[/math]

[math]26^6 = 308.915.776[/math]

Eseguiamo il calcolo finale. Spezziamo la formula lunga su due righe per chiarezza:

[math]3.518.743.761 – 2.176.782.336[/math]

[math]- 594.823.321 + 308.915.776 = 1.056.053.880[/math]

Risposta:

Ci sono [math]1.056.053.880[/math] password possibili che soddisfano i vincoli.

Approfondimento teorico:

  • Principio di Inclusione-Esclusione: Utile per contare gli elementi in un’unione di insiemi. Per due insiemi [math]A[/math] e [math]B[/math], la cardinalità dell’unione è data da [math]|A \cup B| = |A| + |B| – |A \cap B|[/math]. Nel nostro caso, stavamo cercando il complemento di questa unione (elementi che non sono in “senza simboli” E non sono in “senza cifre”), che si calcola come [math]\text{Totale} – |A \cup B| = \text{Totale} – (|A| + |B| – |A \cap B|) = \text{Totale} – |A| – |B| + |A \cap B|[/math].

Esercizio 3: Anagrammi con ripetizioni condizionate

Problema:

Quante parole di 5 lettere si possono formare con le lettere di “MATEMATICA” (M=2, A=3, T=2, E=1, I=1, C=1), con almeno due M?

Ti potrebbe interessare anche:  Curvatura: Cos'è e Come Calcolarla per Curve nel Piano (con Esempi Pratici)

Soluzione:

Analizziamo le lettere disponibili e le loro frequenze: M=2, A=3, T=2, E=1, I=1, C=1. Dobbiamo formare parole di 5 lettere con “almeno due M”. Poiché ci sono solo due M in “MATEMATICA”, “almeno due M” significa che la parola di 5 lettere deve contenere esattamente due M.

Procediamo in due passaggi:

  1. Step 1: Posizionare le due M. Scegliamo 2 delle 5 posizioni nella parola di 5 lettere in cui inserire le due M identiche. Il numero di modi per farlo è dato dal coefficiente binomiale: [math]\binom{5}{2} = 10[/math] modi.
  2. Step 2: Riempire le restanti 3 posizioni. Le 3 posizioni rimanenti devono essere riempite con 3 lettere scelte dall’insieme {A:3, T:2, E:1, I:1, C:1} (le lettere di “MATEMATICA” meno le due M già usate). Questo è un problema di conteggio di parole di 3 lettere da un multiset. Dobbiamo considerare le possibili composizioni delle 3 lettere rimanenti:
    • Caso 1: Tre lettere diverse. Scegliamo 3 tipi di lettere diverse tra A, T, E, I, C (5 opzioni). Il numero di combinazioni è [math]\binom{5}{3} = 10[/math]. Per ogni combinazione di 3 lettere diverse, ci sono [math]3![/math] modi di disporle. Quindi, [math]\binom{5}{3} \times 3! = 10 \times 6 = 60[/math] parole.
    • Caso 2: Due lettere uguali e una diversa. La coppia di lettere uguali può essere AA (da A:3) o TT (da T:2). Ci sono 2 scelte per la lettera che si ripete due volte. La terza lettera deve essere diversa dalla coppia scelta. Se la coppia è AA, la terza lettera può essere T, E, I, C (4 opzioni). Se la coppia è TT, la terza lettera può essere A, E, I, C (4 opzioni).
      Per una scelta specifica (es. AAT), il numero di anagrammi è [math]\frac{3!}{2!}[/math].
      Numero di modi per scegliere le lettere: 2 (tipo di coppia) × 4 (tipo di terza lettera) = 8.
      Numero totale di parole in questo caso: [math]8 \times \frac{3!}{2!} = 8 \times 3 = 24[/math] parole.
    • Caso 3: Tre lettere uguali. L’unica lettera che può ripetersi tre volte è A (da A:3). Quindi, la combinazione è AAA. C’è [math]1[/math] modo di scegliere queste lettere, e 1 modo di disporle. Quindi, [math]1[/math] parola (AAA).

    Il numero totale di modi per riempire le restanti 3 posizioni è la somma dei casi: [math]60 + 24 + 1 = 85[/math] modi.

Il numero totale di parole di 5 lettere con esattamente due M è il prodotto dei modi per posizionare le M e dei modi per riempire le restanti posizioni:

[math]10 \times 85 = 850[/math]

Risposta:

Si possono formare [math]850[/math] parole di 5 lettere con almeno due M utilizzando le lettere di “MATEMATICA”.

Approfondimento teorico:

  • Permutazioni con ripetizione: Il numero di permutazioni distinte di un multiset di [math]n[/math] elementi, dove l’elemento [math]i[/math] si ripete [math]k_i[/math] volte (con [math]\sum k_i = n[/math]), è dato da [math]\frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_r!}[/math]. Questo principio è stato usato implicitamente nel Caso 2 dello Step 2 per contare gli anagrammi delle terne di lettere (es. AAT).

Esercizio 4: Numeri binari con vincoli

Problema:

Quanti numeri binari di 8 bit hanno esattamente tre “1” e almeno due “0” consecutivi?

Soluzione:

Un numero binario di 8 bit con esattamente tre “1” deve avere necessariamente [math]8 – 3 = 5[/math] “0”.

Il numero totale di numeri binari di 8 bit con esattamente tre “1” (e quindi cinque “0”) è dato dal numero di modi di scegliere 3 posizioni su 8 per gli “1”:

[math]\binom{8}{3} = \frac{8!}{3!5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56[/math]

Ora consideriamo il vincolo “almeno due ‘0’ consecutivi”. Questo significa che dobbiamo escludere le sequenze in cui *non* ci sono due “0” consecutivi, ovvero quelle in cui tutti i “0” sono separati.

Per separare i 5 “0” in una sequenza di 8 bit con tre “1”, gli “0” dovrebbero essere posizionati nelle “fessure” create dagli “1”. Con tre “1”, ci sono al massimo 4 “fessure” disponibili (prima del primo 1, tra il primo e il secondo, tra il secondo e il terzo, dopo il terzo):

[math]\_ 1 \_ 1 \_ 1 \_[/math]

Per evitare che ci siano due “0” consecutivi, ogni fessura può contenere al massimo un “0”. Tuttavia, dobbiamo posizionare 5 “0” in queste 4 fessure.

Secondo il Principio dei Cassetti, se abbiamo 5 oggetti (gli “0”) da posizionare in 4 contenitori (le “fessure”), allora almeno un contenitore deve contenere più di un oggetto. Questo significa che almeno una fessura conterrà due o più “0” consecutivi.

Pertanto, è impossibile avere una sequenza di 8 bit con tre “1” e cinque “0” in cui tutti i “0” siano separati. Tutte le 56 sequenze con tre “1” e cinque “0” devono avere almeno due “0” consecutivi.

Risposta:

Ci sono [math]56[/math] numeri binari di 8 bit con esattamente tre “1” e almeno due “0” consecutivi.

Approfondimento teorico:

  • Principio dei Cassetti (o Principio di Dirichlet): Se [math]n[/math] oggetti vengono distribuiti in [math]m[/math] contenitori, con [math]n > m[/math], allora almeno un contenitore deve contenere più di un oggetto. Questo principio è stato cruciale qui per dimostrare che con 5 zeri e 4 possibili posizioni separate da uni, i zeri consecutivi sono inevitabili.

Esercizio 5: Segmenti su una griglia

Problema:

Quanti segmenti orientati si possono tracciare su una griglia 5×5, con estremi distinti e allineati orizzontalmente, verticalmente o in diagonale (pendenza [math]\pm 1[/math])?

Soluzione:

Una griglia 5×5 ha [math]5 \times 5 = 25[/math] punti. Un segmento orientato congiunge due punti distinti. Consideriamo i segmenti in base al loro allineamento:

  • Segmenti Orizzontali: Ci sono 5 righe. Su ogni riga, ci sono 5 punti. Un segmento orizzontale congiunge due punti distinti sulla stessa riga. Il numero di coppie di punti distinti su una riga è [math]\binom{5}{2}[/math]. Poiché i segmenti sono orientati (l’ordine dei punti conta), moltiplichiamo per 2. Segmenti orientati per riga = [math]\binom{5}{2} \times 2 = 10 \times 2 = 20[/math]. Poiché ci sono 5 righe, il totale di segmenti orizzontali orientati è [math]5 \times 20 = 100[/math].
  • Segmenti Verticali: In modo del tutto analogo ai segmenti orizzontali, ci sono 5 colonne, ciascuna con 5 punti. Il numero totale di segmenti verticali orientati è anche [math]5 \times 20 = 100[/math].
  • Segmenti Diagonali (pendenza [math]\pm 1[/math]): Dobbiamo contare i segmenti orientati che si trovano su linee con pendenza +1 o -1.
    • Diagonali con pendenza +1: Queste sono le linee del tipo y = x + c sulla griglia. Le lunghezze (numero di punti) di queste diagonali variano: ci sono 1 diagonale con 5 punti, 2 con 4 punti, 2 con 3 punti, e 2 con 2 punti. Per una diagonale con [math]k[/math] punti, il numero di segmenti orientati su di essa è [math]\binom{k}{2} \times 2[/math] (o equivalentemente, [math]P(k, 2) = k(k-1)[/math]).
      • Lunghezza 5: [math]\binom{5}{2} \times 2 = 10 \times 2 = 20[/math] segmenti.
      • Lunghezza 4: [math]2 \times (\binom{4}{2} \times 2) = 2 \times (6 \times 2) = 24[/math] segmenti.
      • Lunghezza 3: [math]2 \times (\binom{3}{2} \times 2) = 2 \times (3 \times 2) = 12[/math] segmenti.
      • Lunghezza 2: [math]2 \times (\binom{2}{2} \times 2) = 2 \times (1 \times 2) = 4[/math] segmenti.

      Il totale di segmenti orientati con pendenza +1 è [math]20 + 24 + 12 + 4 = 60[/math].

    • Diagonali con pendenza -1: Per simmetria, il numero di segmenti orientati con pendenza -1 è lo stesso, ovvero [math]60[/math].

    Il totale di segmenti diagonali orientati è [math]60 + 60 = 120[/math].

Il numero totale di segmenti orientati è la somma dei segmenti orizzontali, verticali e diagonali:

[math]100 + 100 + 120 = 320[/math]

Risposta:

Si possono tracciare [math]320[/math] segmenti diversi orientati sulla griglia 5×5 con i vincoli dati.

Approfondimento teorico:

  • Disposizioni semplici: Il numero di modi per scegliere e ordinare [math]k[/math] elementi distinti da un insieme di [math]n[/math] elementi ([math]k \le n[/math]) è dato da [math]P(n,k) = \frac{n!}{(n-k)!}[/math]. Nel contesto dei segmenti orientati su una linea con [math]k[/math] punti, scegliere due punti distinti in ordine ([math]P(k,2)[/math]) conta i segmenti orientati. [math]P(k,2) = k(k-1)[/math]. Questo è equivalente a [math]\binom{k}{2} \times 2[/math] perché scegliamo prima i 2 punti e poi decidiamo l’ordine (2 modi).

Sezione Teorica Approfondita

1. Principio di Moltiplicazione

Se un processo può essere scomposto in una sequenza di [math]k[/math] decisioni, e la prima decisione ha [math]n_1[/math] risultati possibili, la seconda decisione ha [math]n_2[/math] risultati possibili (indipendentemente dalla prima), e così via fino alla [math]k[/math]-esima decisione con [math]n_k[/math] risultati possibili, allora il numero totale di risultati possibili per l’intero processo è il prodotto [math]n_1 \times n_2 \times \ldots \times n_k[/math].

Esempio: Lanciare un dado ([math]6[/math] esiti) e poi una moneta ([math]2[/math] esiti) produce un totale di [math]6 \times 2 = 12[/math] esiti combinati.

2. Permutazioni con Ripetizione

Consideriamo un insieme di [math]n[/math] oggetti dove alcuni sono identici. Se ci sono [math]r[/math] tipi distinti di oggetti, e l’i-esimo tipo ([math]i=1, \ldots, r[/math]) appare [math]k_i[/math] volte, con [math]\sum_{i=1}^r k_i = n[/math], allora il numero di permutazioni distinte di questi [math]n[/math] oggetti è dato dalla formula: [math]\frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_r!}[/math].

Esempio: Il numero di anagrammi distinti della parola “MISSISSIPPI” (M:1, I:4, S:4, P:2) è [math]\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!}[/math].

3. Principio di Inclusione-Esclusione

Questo principio è usato per contare gli elementi nell’unione di due o più insiemi. Per due insiemi [math]A[/math] e [math]B[/math], il numero di elementi nella loro unione è la somma delle loro cardinalità meno la cardinalità della loro intersezione, per correggere il doppio conteggio degli elementi comuni: [math]|A \cup B| = |A| + |B| – |A \cap B|[/math]. Questo può essere esteso a più insiemi.

Esempio: Contare i numeri interi da 1 a 100 che sono divisibili per 2 o per 3. Numeri divisibili per 2: 50. Numeri divisibili per 3: 33. Numeri divisibili per 6 (sia 2 che 3): 16. Totale: [math]50 + 33 – 16 = 67[/math].

4. Principio dei Cassetti (Principio di Dirichlet)

Se si dispongono [math]n[/math] oggetti in [math]m[/math] contenitori, e se [math]n > m[/math], allora almeno uno dei contenitori deve contenere più di un oggetto.

Esempio: In un gruppo di 13 persone, almeno due compiono gli anni nello stesso mese, poiché ci sono 13 persone (oggetti) e 12 mesi (contenitori).

(549)

PubblicitàPubblicità