07 - Dadi da poker: permutazioni con ripetizioni e probabilità di un full

Nei primi articoli di combinatoria abbiamo sempre lavorato con elementi distinti.

Tre carte differenti possono essere ordinate in:

$$ 3! = 6 $$

modi, e cinque carte differenti in:

$$ 5! = 120 $$

modi.

Ma con i dadi può comparire una situazione diversa.

Supponiamo di lanciare cinque dadi e ottenere:

2 2 5 5 5

È un full: due dadi mostrano un valore e gli altri tre ne mostrano un altro.

Se provassimo a dire che questi cinque risultati possono essere ordinati in:

$$ 5! = 120 $$

modi, conteremmo moltissime volte la stessa sequenza.

Scambiare tra loro i due 2 non cambia nulla, così come scambiare tra loro i tre 5.

È il momento di introdurre le permutazioni con ripetizioni.

Perché 5! conta troppo

Immaginiamo, per un momento, di rendere artificialmente distinguibili i cinque risultati:

2a 2b 5a 5b 5c

Ora sono cinque oggetti differenti e possiamo ordinarli in:

$$ 5! = 120 $$

modi.

Ma appena togliamo le etichette a, b, c, molti di quegli ordinamenti diventano identici.

Per esempio:

2a 2b 5a 5b 5c

2b 2a 5a 5b 5c

producono entrambi:

2 2 5 5 5

I due 2 possono essere scambiati tra loro in:

$$ 2! = 2 $$

modi senza creare una nuova sequenza osservabile.

I tre 5 possono invece essere permutati internamente in:

$$ 3! = 6 $$

modi senza cambiare il risultato.

Quindi ogni sequenza realmente distinta è stata contata:

2! · 3!
=
12

volte dentro 5!.

Per correggere il conteggio dividiamo:

5! / (2!3!)
=
120 / 12
=
10

Quindi la configurazione:

2 2 5 5 5

può comparire in 10 ordini distinti.

Vediamoli

Possiamo scriverli tutti:

Sono esattamente:

Non importa quale dei dadi fisici abbia prodotto ciascun 2 o ciascun 5: quando guardiamo soltanto la sequenza dei valori, i risultati uguali sono indistinguibili.

La formula generale

Se abbiamo n posizioni occupate da elementi di più tipi e alcuni elementi sono ripetuti, il numero di ordinamenti distinti è:

n!
----------------
n1! n2! ... nr!

dove:

n1 + n2 + ... + nr = n

e n1, n2, ..., nr indicano quante volte compare ciascun tipo.

Nel nostro full:

$$ n = 5 $$

con:

3 valori uguali
2 valori uguali

quindi:

$$ 5! / (3!2!) = 10 $$

La formula nasce dallo stesso principio incontrato nelle combinazioni: quando un conteggio considera come diversi ordinamenti che per il nostro problema sono indistinguibili, dobbiamo eliminare le duplicazioni.

Un altro esempio: quattro uguali e uno diverso

Supponiamo di ottenere:

4 4 4 4 6

Le cinque posizioni potrebbero essere permutate in 5! modi se tutti gli elementi fossero distinti.

Ma i quattro 4 possono essere scambiati tra loro in:

$$ 4! $$

modi senza cambiare nulla.

Quindi:

5! / 4!
=
5

ordinamenti distinti.

Ed è intuitivo: il 6 può stare in una qualsiasi delle cinque posizioni.

E cinque dadi tutti uguali?

Se otteniamo:

3 3 3 3 3

abbiamo:

$$ 5! / 5! = 1 $$

solo ordinamento distinto.

Anche questo è coerente con l'intuizione: spostare dadi che mostrano tutti lo stesso valore non produce alcuna sequenza nuova.

Ora calcoliamo la probabilità di un full

Passiamo dal conteggio alla probabilità.

Lanciamo cinque dadi equilibrati a sei facce e chiediamoci:

Qual è la probabilità di ottenere un full, cioè tre dadi con un valore e due dadi con un altro valore diverso?

Per risolvere il problema dobbiamo contare sia tutti gli esiti possibili sia quelli favorevoli.

Quanti esiti possibili producono cinque dadi?

Ogni dado può mostrare:

valori.

Poiché i cinque lanci sono indipendenti:

6 · 6 · 6 · 6 · 6
=
6⁵
=
7.776

sequenze ordinate equiprobabili.

Questo è il nostro denominatore.

Scegliamo il valore del tris

Il valore che compare tre volte può essere uno qualsiasi tra:

1 2 3 4 5 6

quindi abbiamo:

possibilità.

Supponiamo di scegliere:

come valore del tris.

Scegliamo il valore della coppia

La coppia deve avere un valore diverso da quello del tris.

Se abbiamo già scelto 5, restano:

possibilità:

1 2 3 4 6

Quindi la scelta dei due valori può essere fatta in:

$$ 6 \cdot 5 = 30 $$

modi.

È importante non dividere per 2.

Il ruolo dei due valori è diverso:

5 come tris e 2 come coppia

non è lo stesso caso di:

2 come tris e 5 come coppia

Nel primo risultato compaiono tre 5; nel secondo compaiono tre 2.

Disponiamo tris e coppia nei cinque dadi

Una volta scelti i valori, per esempio:

tris = 5
coppia = 2

dobbiamo stabilire in quali posizioni compaiono.

Abbiamo appena calcolato che gli ordinamenti distinti di:

5 5 5 2 2

sono:

5! / (3!2!)
=
10

Per ogni coppia di valori esistono quindi 10 sequenze favorevoli.

Casi favorevoli totali

Moltiplichiamo le tre scelte:

modi per scegliere il valore del tris,

modi per scegliere il valore della coppia,

modi per distribuire i valori nei cinque dadi.

Otteniamo:

6 · 5 · 10
=
300

esiti favorevoli.

Quindi:

P(full)
=
300 / 7.776

La frazione si semplifica a:

$$ 25 / 648 $$

e in percentuale vale circa:

3,858%

Lo stesso conteggio usando una combinazione

Il fattore:

$$ 5! / (3!2!) = 10 $$

può essere letto anche in un altro modo.

Una volta scelti i valori del tris e della coppia, basta scegliere quali tre dei cinque dadi mostrano il valore del tris:

$$ \binom{5}{3} = 10 $$

Le due posizioni rimaste sono automaticamente occupate dalla coppia.

Potremmo anche scegliere le due posizioni della coppia:

$$ \binom{5}{2} = 10 $$

e ottenere lo stesso risultato.

Non è una coincidenza:

$$ \binom{5}{3} = \binom{5}{2} = 5! / (3!2!) $$

Questo collega direttamente le combinazioni dell'articolo precedente alle permutazioni con ripetizioni.

Stiamo osservando lo stesso conteggio da due prospettive diverse.

Perché non usiamo C(6,2) per scegliere i valori?

Potremmo pensare:

Devo scegliere due valori distinti tra sei, quindi uso C(6,2).

Ma così otterremmo soltanto:

coppie non ordinate di valori.

Per un full, però, i due valori hanno ruoli differenti: uno è il tris e uno è la coppia.

Per ogni coppia non ordinata, per esempio:

{2,5}

esistono due full diversi come struttura dei valori:

2 2 2 5 5

2 2 5 5 5

Perciò potremmo anche scrivere:

C(6,2) · 2 · 10
=
15 · 2 · 10
=
300

Il risultato è lo stesso di:

6 · 5 · 10
=
300

ma il secondo ragionamento è più diretto perché assegna immediatamente i ruoli di tris e coppia.

Un controllo per enumerazione completa

Lo spazio campionario contiene soltanto:

7.776

sequenze.

È abbastanza piccolo da poter essere enumerato completamente in C#.

Possiamo quindi verificare il risultato matematico senza ricorrere a Monte Carlo.

static bool IsFull(
    int a,
    int b,
    int c,
    int d,
    int e)
{
    int[] conteggi = new int[7];

    conteggi[a]++;
    conteggi[b]++;
    conteggi[c]++;
    conteggi[d]++;
    conteggi[e]++;

    bool haTre = false;
    bool haDue = false;

    for (int valore = 1; valore <= 6; valore++)
    {
        if (conteggi[valore] == 3)
            haTre = true;

        if (conteggi[valore] == 2)
            haDue = true;
    }

    return haTre && haDue;
}

int favorevoli = 0;
int totali = 0;

for (int a = 1; a <= 6; a++)
for (int b = 1; b <= 6; b++)
for (int c = 1; c <= 6; c++)
for (int d = 1; d <= 6; d++)
for (int e = 1; e <= 6; e++)
{
    totali++;

    if (IsFull(a, b, c, d, e))
        favorevoli++;
}

Console.WriteLine($"Favorevoli: {favorevoli}");
Console.WriteLine($"Totali:     {totali}");

Il programma produce:

Favorevoli: 300
Totali:     7776

che coincide esattamente con il conteggio combinatorio.

Il calcolo combinatorio in C#

Lo standalone C# associato a questo articolo è:

FullCinqueDadi.cs

Possiamo anche implementare direttamente le permutazioni con ripetizioni.

using System.Numerics;

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;
}

static BigInteger PermutazioniConRipetizioni(
    params int[] molteplicità)
{
    if (molteplicità is null)
        throw new ArgumentNullException(nameof(molteplicità));

    int totale = 0;

    foreach (int valore in molteplicità)
    {
        if (valore < 0)
            throw new ArgumentOutOfRangeException(nameof(molteplicità));

        totale += valore;
    }

    BigInteger risultato = Fattoriale(totale);

    foreach (int valore in molteplicità)
        risultato /= Fattoriale(valore);

    return risultato;
}

BigInteger ordinamenti =
    PermutazioniConRipetizioni(3, 2);

Console.WriteLine(ordinamenti);

Il risultato è:

Per un poker di dadi, cioè quattro risultati uguali e uno diverso:

Console.WriteLine(
    PermutazioniConRipetizioni(4, 1));

otteniamo:

Per cinque valori tutti uguali:

Console.WriteLine(
    PermutazioniConRipetizioni(5));

otteniamo:

Calcoliamo il full senza enumerare 7.776 casi

Ora possiamo tradurre direttamente il ragionamento matematico:

BigInteger modiValori = 6 * 5;

BigInteger modiPosizioni =
    PermutazioniConRipetizioni(3, 2);

BigInteger favorevoli =
    modiValori * modiPosizioni;

BigInteger totali =
    BigInteger.Pow(6, 5);

double probabilita =
    (double)favorevoli / (double)totali;

Console.WriteLine($"Favorevoli: {favorevoli}");
Console.WriteLine($"Totali:     {totali}");
Console.WriteLine($"P(full):    {probabilita:P4}");

Otteniamo:

Favorevoli: 300
Totali:     7776
P(full):    3,8580%

Il vantaggio del calcolo combinatorio è evidente.

In questo caso enumerare 7.776 risultati è ancora facile, ma la formula ci dice perché i casi favorevoli sono 300 e continua a funzionare anche quando lo spazio diventa molto più grande.

Formula esatta e verifica completa

In questo articolo possiamo permetterci una verifica migliore di Monte Carlo.

Il calcolo teorico produce:

$$ 300 / 7776 $$

e l'enumerazione di tutte le sequenze produce esattamente:

full su:

esiti.

Non c'è errore statistico.

Quindi abbiamo due metodi esatti:

conteggio combinatorio

enumerazione completa

Monte Carlo sarebbe possibile, ma qui aggiungerebbe soltanto un'approssimazione a un problema che possiamo verificare integralmente.

Questa distinzione sarà importante più avanti: non dobbiamo simulare per abitudine quando lo spazio campionario è abbastanza piccolo da essere enumerato esattamente.

Il punto pratico

Con le permutazioni semplici tutti gli elementi erano distinti:

$$ n! $$

Con le permutazioni con ripetizioni alcuni elementi sono indistinguibili, quindi dobbiamo eliminare gli scambi interni che non producono un nuovo risultato:

n!
----------------
n1! n2! ... nr!

Per un full specifico come:

2 2 5 5 5

abbiamo:

5! / (2!3!)
=
10

ordinamenti distinti.

Per un full qualunque con cinque dadi:

6 · 5 · 10
=
300

esiti favorevoli su:

$$ 6^{5} = 7.776 $$

esiti equiprobabili.

Quindi:

P(full)
=
300/7776
=
25/648
≈
3,858%

Con questo articolo si completa il blocco dedicato a permutazioni, disposizioni, combinazioni e ripetizioni.

Siamo partiti dal fattoriale e abbiamo imparato a distinguere quattro situazioni diverse: ordinare tutti gli elementi, sceglierne soltanto alcuni mantenendo l'ordine, sceglierli ignorando l'ordine e ordinare elementi tra i quali esistono ripetizioni indistinguibili.

Il prossimo passo sarà tornare pienamente alla probabilità.

Con le carte inizieremo a studiare cosa succede quando ogni estrazione modifica le probabilità successive: due assi consecutivi senza reinserimento.