Statistica - calcolo combinatorio e probabilità - Appunti

Calcolo combinatorio

Necessità del calcolo combinatorio

Accade spesso di dover risolvere problemi dall'apparenza molto semplice, ma che richiedono calcoli lunghi e noiosi per riuscire a trovare delle conclusioni valide. Supponiamo, ad esempio, di voler risolvere il seguente problema: in quanti modi quattro persone possono sedersi l’una accanto all’altra?

Risolvere il problema, nel migliore dei casi, richiede disciplina e la scelta di una strategia per arrivare a contare effettivamente tutti i modi possibili. Decidiamo, allora, di procedere sistematicamente per esaurire tutte le possibilità esistenti: fissiamo la prima persona, senza cambiare di posto, e contiamo in quanti modi le tre rimanenti possono sedersi accanto. Poi fissiamo la seconda e così via fino alla quarta. Se chiamiamo A, B, C e D le quattro persone, avremo:

ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA

Dallo schema precedente, si vede subito che ci sono 24 modi diversi per far sedere quattro persone l'una accanto all'altra, in fila. Il nostro problema è risolto, diremmo. Ma quanta fatica per arrivarci! In effetti, a noi interessa solo contare il numero dei diversi modi e non elencarli esplicitamente l'uno dopo l'altro.

Supponiamo ora di voler complicare il problema. Possiamo ritenere che le lettere, che rappresentano le quattro persone, elencate l'una dopo l'altra, siano le lettere dell’alfabeto di una certa lingua. Allora, se non ci sono ripetizioni di lettere, ci sono 24 parole diverse che si possono formare con le quattro lettere dell'alfabeto. Ma quante parole si possono formare se vogliamo considerare anche le ripetizioni di ciascuna lettera? Per rispondere potremmo pensare di seguire la strategia precedente. Ma ci vorrebbe molto tempo e rinunciamo a farlo, dando soltanto il risultato: 256.

Il risultato di sopra l'abbiamo dato non perché, in separata sede ci siamo messi a fare il lavoro per elencare prima e contare poi le parole che si possono formare. Abbiamo soltanto contato il numero del modi possibili in cui le quattro lettere si possono scrivere l'una accanto all'altra con tutte le ripetizioni possibili. Vediamo come.

In quanti modi possiamo scegliere la prima lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la seconda lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la terza lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la quarta lettera? In 4 modi diversi.
Allora il numero delle parole possibili (contando le ripetizioni) è: 4x4x4x4=256.

Per il primo problema la situazione è differente in quanto non possiamo avere ripetizioni; e dunque:

In quanti modi possiamo scegliere la prima lettera? In 4 modi diversi.
In quanti modi possiamo scegliere la seconda lettera? In 3 modi diversi.
In quanti modi possiamo scegliere la terza lettera? In 2 modi diversi.
In quanti modi possiamo scegliere la quarta lettera? In 1 modo.
Allora il numero dei modi in cui possiamo scrivere, senza ripetizioni, parole con le quattro lettere A, B, C e D è: 4x3x2x1=24.

A quali conclusioni ci portano le considerazioni precedenti? Innanzitutto possiamo fare astrazione dalla natura degli oggetti considerati (persone o lettere dell'alfabeto). In secondo luogo, la scelta di una buona strategia di calcolo può farci evitare elenchi lunghi e noiosi che, in casi più complessi, sarebbero addirittura impensabili. Scopo del calcolo combinatorio è evitare, appunto, elenchi inutili e noiosi ed arrivare al risultato richiesto con l'ausilio di calcoli molto semplici (le classiche 4 operazioni!) e di fornire anche, se necessario, gli elenchi di tutti i casi possibili.

Nel resto del capitolo vedremo, in modo sistematico, le tecniche del calcolo combinatorio da applicare, nei capitoli seguenti, al calcolo delle probabilità.

Disposizioni semplici e con ripetizione

Un problema molto ricorrente, in diverse situazioni (non necessariamente di tipo matematico), è quello del calcolo del numero dei modi in cui un certo numero di elementi, presi da un determinato insieme finito, possono essere disposti, ritenendo che due configurazioni sono diverse o per la natura degli elementi o per l'ordine in cui gli elementi sono sistemati.

Per rendere le idee più chiare, supponiamo di avere un insieme di cinque lettere: A, B, C, D ed E. Vogliamo sapere quante parole diverse, ciascuna formata da tre lettere, si possono formare a partire dalle cinque lettere date. Ogni parola prende il nome di disposizione dei cinque elementi presi tre alla volta. È chiaro che la prima lettera può essere scelta, tra le cinque, in cinque modi diversi; la seconda lettera, tra le quattro rimanenti, in quattro modi diversi; infine, la terza lettera, tra le tre rimanenti, in tre modi diversi. Quindi otteniamo 5x4x3=60 modi diversi di disporre tre lettere da scegliere in un insieme di cinque lettere.

La cosa può essere generalizzata, considerando un insieme di n elementi e volendo calcolare il numero di modi in cui possiamo scegliere una configurazione di k elementi, tra gli n disponibili, considerando diverse due configurazioni che hanno elementi diversi o che, pur avendo gli stessi elementi, questi sono disposti in ordine diverso. Si parla in questo caso di disposizioni semplici di n elementi presi k alla volta, il cui numero viene indicato simbolicamente con D(n,k).

Per calcolare questo numero possiamo procedere come nell'esempio precedente:

• In quanti modi possiamo scegliere il 1° elemento? In n modi diversi.
• In quanti modi possiamo scegliere il 2° elemento? In n - 1 modi diversi.
• In quanti modi possiamo scegliere il 3° elemento? In n - 2 modi diversi.
• In quanti modi possiamo scegliere il k-esimo elemento? In n - k + 1 modi diversi.

Allora avremo: D(n,k) = n(n - 1)(n - 2)...(n - k + 1)

La formula, che ci dà il numero di disposizioni semplici di n elementi presi k alla volta, può essere letta come il prodotto di k fattori naturali decrescenti a partire da n. Mediante questa formula, non abbiamo più bisogno di elencare tutte le configurazioni possibili e poi contarle. Tutto si riduce ad un calcolo meccanico per il problema specifico.

Esempi di calcolo delle disposizioni

Esempio 1: Calcolare in quanti modi 10 palline numerate da 1 a 10 possono essere estratte da un'urna prendendone 4 alla volta.

Il calcolo è semplice ed abbiamo: D(10,4) = 10·9·8·7 = 5040. Notare che abbiamo il prodotto di 4 fattori decrescenti a partire da 10.

Esempio 2: Calcolare il numero dei modi in cui uno studente può scegliere, nell'ordine, 5 domande tra un questionario di 8 domande.

Abbiamo facilmente: D(8,5) = 8·7·6·5·4 = 6720. Notare che abbiamo il prodotto di 5 fattori decrescenti a partire da 8.

Ma cosa succede se i k elementi che dobbiamo scegliere tra gli n disponibili possono essere ripetuti? In questo caso si parla di disposizioni con ripetizione di n elementi presi k alla volta, il cui numero viene indicato con D'(n,k).

Il calcolo del numero di queste disposizioni è ancora più semplice che nel caso delle disposizioni semplici, in quanto, ogni volta, possiamo scegliere tutti gli n elementi dell'insieme dato. Avremo allora:

• In quanti modi possiamo scegliere il 1° elemento? In n modi diversi.
• In quanti modi possiamo scegliere il 2° elemento? In n modi diversi.
• In quanti modi possiamo scegliere il 3° elemento? In n modi diversi.
• In quanti modi possiamo scegliere il k-esimo elemento? In n modi diversi.

Dunque: D'(n,k) = n^k

Esempi di disposizioni con ripetizione

Esempio 3: Omettendo il loro discutibile significato, quante parole di 3 lettere si possono formare con 5 lettere?

Abbiamo immediatamente: D'(5,3) = 5³ = 125.

Esempio 4: Disponendo di bandiere di 7 colori diversi, quanti messaggi differenti si possono formare usando 4 bandiere alla volta?

Si tratta evidentemente di disposizioni con ripetizione di 7 elementi presi 4 alla volta. Quindi avremo: D'(7,4) = 7⁴ = 2401.

Esempio 5: Calcoliamo il numero delle colonne che è necessario giocare, nel gioco del Totocalcio, per fare con certezza un tredici. In questo gioco, molto probabilmente...