SUPERCAT.DEV

Nel precedente articolo abbiamo contato tutti i possibili ordinamenti di un mazzo completo:

$$ 52! $$

Ma spesso non ci interessa sapere come sono ordinate tutte le 52 carte.

Supponiamo invece di mescolare un mazzo standard e osservare soltanto le prime tre.

Quante sequenze diverse possiamo ottenere?

La risposta non è:

$$ 52! $$

perché le altre 49 carte non fanno parte del risultato che stiamo distinguendo.

Non è nemmeno:

$$ 52^{3} $$

perché, dopo aver estratto una carta, non possiamo estrarla di nuovo se non la rimettiamo nel mazzo.

Il conteggio corretto nasce ancora una volta dal principio del prodotto.

Prima carta, seconda carta, terza carta

Per la prima posizione possiamo scegliere una qualsiasi delle:

52

carte.

Dopo la prima estrazione ne rimangono:

51

per la seconda posizione.

Dopo la seconda ne rimangono:

50

per la terza.

Il numero di sequenze ordinate possibili è quindi:

52 · 51 · 50
=
132.600

Abbiamo scelto soltanto tre carte, ma l'ordine in cui compaiono fa parte del risultato.

Per esempio:

A♠ K♥ 7♣

e:

7♣ K♥ A♠

contengono le stesse tre carte, ma sono due sequenze diverse.

Questo è il problema delle disposizioni semplici.

Che cosa cambia rispetto alle permutazioni?

Nella terminologia che useremo in tutta la serie, una permutazione ordina tutti gli n elementi disponibili.

Una disposizione sceglie invece soltanto k elementi tra n e tiene conto dell'ordine.

Con un mazzo completo:

permutazione:
ordino tutte le 52 carte

Con le prime tre carte:

disposizione:
scelgo 3 carte tra 52
e considero anche il loro ordine

La differenza non è soltanto terminologica. Cambia il numero dei fattori che dobbiamo moltiplicare.

La formula generale

Se abbiamo n elementi distinti e vogliamo sceglierne k senza ripetizione, mantenendo l'ordine, abbiamo:

$$ n $$

possibilità per il primo posto,

$$ n - 1 $$

per il secondo,

$$ n - 2 $$

per il terzo,

e così via fino ad aver scelto k elementi.

Il numero di disposizioni è quindi:

$$ n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) $$

Questa stessa quantità può essere scritta usando il fattoriale.

Partiamo da:

$$ n! = n \cdot (n-1) \cdot ... \cdot (n-k+1) \cdot (n-k)! $$

Dividendo per:

$$ (n-k)! $$

rimangono soltanto i primi k fattori:

$$ D(n,k) = n! / (n-k)! $$

La notazione può variare tra testi diversi; qui useremo D(n,k) come abbreviazione didattica per le disposizioni semplici.

Per il nostro mazzo:

$$ D(52,3) = 52! / 49! $$

e tutti i fattori da 49! in giù si semplificano:

D(52,3)
=
52 · 51 · 50
=
132.600

Perché non serve calcolare davvero 52!

Questa forma:

$$ 52! / 49! $$

è matematicamente corretta, ma non è il modo più intelligente di calcolare il risultato.

Sviluppando i fattoriali:

$$ 52! = 52 \cdot 51 \cdot 50 \cdot 49! $$

quindi:

$$ 52! / 49! = 52 \cdot 51 \cdot 50 $$

Non abbiamo bisogno di costruire due numeri enormi per poi dividerli.

Questo principio sarà utile anche nel codice: quando vogliamo una disposizione possiamo moltiplicare direttamente soltanto i k fattori necessari.

Una probabilità immediata

Ora scegliamo una sequenza precisa prima dell'estrazione:

prima: A♠
seconda: K♠
terza: Q♠

Assumiamo che il mazzo sia ben mescolato e che tutte le sequenze ordinate di tre carte siano equiprobabili.

Abbiamo:

132.600

sequenze possibili e una sola sequenza favorevole.

Quindi:

P(A♠, poi K♠, poi Q♠)
=
1 / 132.600

cioè circa:

0,000754%

La stessa probabilità può essere ottenuta moltiplicando le probabilità condizionate delle tre estrazioni:

$$ 1/52 \cdot 1/51 \cdot 1/50 = 1/132.600 $$

I due ragionamenti coincidono perché stanno descrivendo lo stesso spazio campionario da prospettive diverse.

Qui le estrazioni non sono indipendenti

È importante notare la differenza rispetto ai lanci di dado visti negli articoli precedenti.

Dopo aver estratto:

A♠

quella carta non è più nel mazzo.

La seconda estrazione avviene quindi su:

51

carte, non su 52.

Dopo due estrazioni rimangono:

50

carte.

Questo significa che le estrazioni senza reinserimento non sono indipendenti.

La probabilità del secondo passo dipende da ciò che è successo nel primo, perché lo spazio delle possibilità è cambiato.

Il principio del prodotto continua a funzionare, ma i fattori cambiano:

$$ 52 \cdot 51 \cdot 50 $$

nel conteggio,

oppure:

$$ 1/52 \cdot 1/51 \cdot 1/50 $$

nella probabilità di una particolare sequenza.

E se rimettessimo ogni carta nel mazzo?

Immaginiamo ora un esperimento diverso: peschiamo una carta, la registriamo, la rimettiamo nel mazzo, mescoliamo e ripetiamo.

In quel caso ogni estrazione avrebbe nuovamente:

52

possibilità.

Le sequenze di tre estrazioni diventerebbero:

52 · 52 · 52
=
52³
=
140.608

e la stessa carta potrebbe comparire più volte.

Per esempio sarebbe possibile:

A♠ A♠ A♠

che invece è impossibile in tre estrazioni senza reinserimento da un singolo mazzo.

Questa distinzione fra con reinserimento e senza reinserimento cambia completamente il modello probabilistico.

Nella serie dovremo quindi dichiararla ogni volta che analizziamo un'estrazione.

Un piccolo esempio con cinque carte

Prima di lavorare con 52 elementi, possiamo verificare il ragionamento su un insieme più piccolo.

Prendiamo cinque carte distinte e scegliamone tre in ordine.

La prima posizione offre:

5

scelte.

La seconda:

4

La terza:

3

Quindi:

D(5,3)
=
5 · 4 · 3
=
60

Con la formula fattoriale:

D(5,3)
=
5! / 2!
=
120 / 2
=
60

Il risultato è lo stesso.

Cosa succede se k = n?

Se scegliamo tutti gli elementi:

$$ k = n $$

la formula delle disposizioni diventa:

$$ D(n,n) = n! / (n-n)! = n! / 0! $$

Poiché:

$$ 0! = 1 $$

otteniamo:

$$ D(n,n) = n! $$

Quindi le permutazioni non sono un concetto scollegato: sono il caso particolare delle disposizioni nel quale scegliamo tutti gli elementi.

Questo è uno dei motivi per cui 0! = 1 rende le formule combinatorie così coerenti.

Cosa succede se k = 0?

Se non scegliamo alcun elemento:

D(n,0)
=
n! / n!
=
1

Esiste un solo modo di scegliere una sequenza ordinata di lunghezza zero: la sequenza vuota.

Anche questo caso può sembrare astratto, ma rende la formula valida senza eccezioni artificiali.

Calcoliamo le disposizioni in C#

Lo standalone C# associato a questo articolo è:

DisposizioniCarte.cs

Poiché i conteggi combinatori possono crescere rapidamente, continuiamo a usare BigInteger.

Non serve però calcolare due fattoriali completi.

using System.Numerics;

static BigInteger Disposizioni(int n, int k)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    if (k < 0 || k > n)
        throw new ArgumentOutOfRangeException(nameof(k));

    BigInteger risultato = BigInteger.One;

    for (int i = 0; i < k; i++)
        risultato *= n - i;

    return risultato;
}

BigInteger sequenze = Disposizioni(52, 3);

Console.WriteLine(sequenze);

Il risultato è:

132600

Il ciclo esegue esattamente il prodotto:

$$ 52 \cdot 51 \cdot 50 $$

La struttura del codice coincide quindi con il ragionamento combinatorio.

Verifichiamo la formula fattoriale

Per controllo possiamo anche implementare il fattoriale e confrontare le due forme.

static BigInteger Fattoriale(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    BigInteger risultato = BigInteger.One;

    for (int i = 2; i <= n; i++)
        risultato *= i;

    return risultato;
}

BigInteger diretta = Disposizioni(52, 3);

BigInteger conFattoriali =
    Fattoriale(52) / Fattoriale(49);

Console.WriteLine(diretta == conFattoriali);

Il programma stampa:

True

Matematicamente le due forme sono equivalenti.

Computazionalmente, però, il prodotto diretto di k fattori è più semplice e non costruisce valori intermedi inutilmente grandi.

Enumeriamo un caso piccolo

Con cinque elementi possiamo anche generare tutte le sequenze ordinate di lunghezza tre per verificare che siano davvero 60.

static void Enumera(
    string[] elementi,
    bool[] usato,
    string[] corrente,
    int posizione,
    ref int conteggio)
{
    if (posizione == corrente.Length)
    {
        Console.WriteLine(string.Join(" ", corrente));
        conteggio++;
        return;
    }

    for (int i = 0; i < elementi.Length; i++)
    {
        if (usato[i])
            continue;

        usato[i] = true;
        corrente[posizione] = elementi[i];

        Enumera(
            elementi,
            usato,
            corrente,
            posizione + 1,
            ref conteggio);

        usato[i] = false;
    }
}

string[] carte =
{
    "A",
    "K",
    "Q",
    "J",
    "10"
};

int conteggio = 0;

Enumera(
    carte,
    new bool[carte.Length],
    new string[3],
    0,
    ref conteggio);

Console.WriteLine($"Totale: {conteggio}");

Il risultato finale è:

Totale: 60

Ancora una volta l'enumerazione è utile per verificare un caso piccolo, mentre la formula è ciò che ci permette di affrontare spazi molto più grandi.

Le stesse tre carte, ma in qualunque ordine

Torniamo alla sequenza:

A♠ K♠ Q♠

Finora abbiamo richiesto esattamente questo ordine.

Ma supponiamo che la domanda diventi:

Qual è la probabilità che le prime tre carte siano proprio A♠, K♠ e Q♠, in qualunque ordine?

Ora gli esiti favorevoli non sono più uno solo.

Le tre carte possono comparire in:

$$ 3! = 6 $$

ordini diversi.

Quindi:

P(le tre carte specifiche, qualunque ordine)
=
6 / 132.600
=
1 / 22.100

La probabilità è sei volte maggiore rispetto a richiedere un ordine preciso.

Questo esempio mette in evidenza la domanda che guiderà il prossimo articolo:

Se l'ordine non cambia ciò che considero un successo, perché dovrei continuare a contare separatamente tutti i suoi possibili ordinamenti?

La risposta ci porterà alle combinazioni.

Il punto pratico

Le permutazioni rispondono alla domanda:

In quanti modi posso ordinare tutti gli elementi?

Le disposizioni rispondono invece a:

In quanti modi posso scegliere k elementi tra n, se anche l'ordine è importante?

Per tre carte estratte senza reinserimento da un mazzo di 52:

D(52,3)
=
52 · 51 · 50
=
132.600

e in generale:

$$ D(n,k) = n! / (n-k)! $$

Il fattoriale che abbiamo introdotto nell'articolo precedente non viene quindi sostituito: viene usato per descrivere un problema più generale.

Ma il passaggio successivo cambierà una sola condizione e produrrà una formula diversa.

Se ci interessa una mano di carte, l'ordine nel quale le carte sono arrivate non conta. Le sei sequenze delle stesse tre carte devono allora essere considerate un unico risultato.

È da questa eliminazione degli ordinamenti duplicati che nasceranno le combinazioni.