SUPERCAT.DEV

Nel precedente articolo abbiamo contato le possibili sequenze di tre carte estratte senza reinserimento da un mazzo standard:

52 · 51 · 50
=
132.600

Quel conteggio era corretto perché distinguevamo l'ordine.

Quindi:

A♠ K♠ Q♠

e:

Q♠ A♠ K♠

erano due risultati diversi.

Ma se stiamo parlando di una mano di tre carte, cambia tutto.

Le carte presenti sono le stesse. L'ordine nel quale sono state distribuite non modifica la mano.

In quel momento le disposizioni iniziano a contare troppe volte lo stesso risultato.

Ed è proprio da questo problema che nascono le combinazioni.

Le stesse tre carte vengono contate sei volte

Prendiamo tre carte specifiche:

A♠
K♠
Q♠

Se consideriamo l'ordine, possono comparire così:

A♠ K♠ Q♠
A♠ Q♠ K♠
K♠ A♠ Q♠
K♠ Q♠ A♠
Q♠ A♠ K♠
Q♠ K♠ A♠

Sono:

$$ 3! = 6 $$

sequenze diverse.

Ma come mano rappresentano un solo risultato:

{A♠, K♠, Q♠}

Quindi il conteggio delle disposizioni:

132.600

conta ogni insieme di tre carte esattamente:

$$ 3! = 6 $$

volte.

Per ottenere il numero delle mani distinte dobbiamo eliminare questi duplicati:

132.600 / 6
=
22.100

Quindi esistono:

22.100

diverse selezioni di tre carte da un mazzo di 52 quando l'ordine non conta.

Dalle disposizioni alle combinazioni

Nel caso generale, le disposizioni semplici di k elementi scelti tra n sono:

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

Ma ogni gruppo di k elementi viene contato in tutti i suoi possibili ordinamenti interni.

Questi ordinamenti sono:

$$ k! $$

Perciò dividiamo per k!:

$$ \binom{n}{k} = D(n,k) / k! $$

Sostituendo la formula delle disposizioni:

$$ \binom{n}{k} = n! / (k!(n-k)!) $$

Questa è la formula delle combinazioni semplici.

Il punto importante non è ricordare il denominatore. È capire perché compare.

(n-k)! elimina la parte degli elementi che non abbiamo scelto.

k! elimina invece i diversi ordinamenti della stessa selezione, perché in questo problema non rappresentano risultati differenti.

La domanda che decide tutto

Prima di scegliere una formula conviene chiedersi:

Se prendo gli stessi elementi ma cambio il loro ordine, ho ottenuto un risultato diverso?

Se la risposta è sì, siamo nel territorio delle disposizioni.

Se la risposta è no, siamo nel territorio delle combinazioni.

Per esempio:

non è uguale a:

1° Carla, 2° Bruno, 3° Alice

quindi l'ordine conta.

Una mano di carte:

A♠ K♠ Q♠

rimane invece la stessa mano indipendentemente dall'ordine con cui le carte sono arrivate.

La combinatoria diventa molto più semplice quando partiamo dalla struttura del risultato invece di cercare di riconoscere una formula dalla forma dell'esercizio.

Tre carte da un mazzo

Applichiamo la formula:

$$ \binom{52}{3} = 52! / (3!49!) $$

Semplificando:

C(52,3)
=
52 · 51 · 50
---------------
3 · 2 · 1

otteniamo:

C(52,3)
=
22.100

Possiamo leggere il calcolo in modo molto concreto.

Il numeratore:

$$ 52 \cdot 51 \cdot 50 $$

conta tutte le sequenze ordinate di tre carte.

Il denominatore:

$$ 3! $$

raggruppa le sei sequenze che rappresentano ogni singola mano.

La probabilità delle tre carte specifiche

Nel precedente articolo avevamo calcolato la probabilità di ottenere esattamente:

A♠ poi K♠ poi Q♠

in quell'ordine:

$$ 1 / 132.600 $$

Ora chiediamo:

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

Se usiamo le disposizioni, abbiamo:

6

sequenze favorevoli su:

132.600

sequenze possibili:

$$ 6 / 132.600 = 1 / 22.100 $$

Se invece costruiamo direttamente lo spazio campionario delle mani non ordinate, abbiamo una sola combinazione favorevole su:

$$ \binom{52}{3} = 22.100 $$

quindi:

$$ 1 / 22.100 $$

Il risultato è identico.

Questo è un controllo importante: possiamo modellare lo stesso problema in modi diversi, purché numeratore e denominatore contino oggetti dello stesso tipo.

Una mano di poker a cinque carte

Ora possiamo costruire uno dei denominatori più importanti che useremo più avanti.

Una mano di poker tradizionale contiene cinque carte e l'ordine nel quale sono state distribuite non cambia la mano.

Quindi il numero di mani possibili è:

$$ \binom{52}{5} $$

ossia:

$$ 52! / (5!47!) $$

Semplificando:

52 · 51 · 50 · 49 · 48
------------------------
5 · 4 · 3 · 2 · 1

otteniamo:

2.598.960

mani differenti.

Questo numero tornerà quando calcoleremo le probabilità di coppia, doppia coppia, tris, scala, colore, full e poker.

Non dovremo memorizzare quelle probabilità: costruiremo ogni volta il numeratore contando le mani favorevoli e useremo:

2.598.960

come numero totale delle mani possibili.

Una mano specifica

Supponiamo di decidere prima della distribuzione una mano esatta:

A♠ K♠ Q♠ J♠ 10♠

Se tutte le mani di cinque carte sono equiprobabili, la probabilità di ricevere proprio quelle cinque carte, senza considerare l'ordine, è:

$$ 1 / \binom{52}{5} $$

cioè:

$$ 1 / 2.598.960 $$

circa:

0,00003848%

Attenzione: qui stiamo parlando di una specifica mano, non della probabilità di una scala reale in generale.

Esistono più mani che appartengono alla categoria "scala reale"; quel conteggio verrà affrontato quando studieremo le mani di poker.

Ancora una volta, l'evento deve essere definito con precisione prima di contare.

Lo stesso principio nelle estrazioni numeriche

Le combinazioni non appartengono soltanto alle carte.

Immaginiamo un gioco nel quale vengono estratti sei numeri distinti da 1 a 90 e il giocatore deve indovinare quali sei usciranno, senza che l'ordine di estrazione abbia importanza.

Il numero delle sestine possibili è:

$$ \binom{90}{6} $$

cioè:

622.614.630

Se una sola sestina specifica è vincente, la probabilità di indovinarla è:

$$ 1 / 622.614.630 $$

circa:

0,0000001606%

Il meccanismo è identico a quello della mano di carte.

Se l'estrazione fisica produce comunque una sequenza ordinata di sei numeri, ogni sestina non ordinata corrisponde a:

$$ 6! = 720 $$

sequenze possibili.

Poiché il gioco ignora quell'ordine, tutte le 720 sequenze vengono considerate lo stesso risultato.

Perché C(n,k) = C(n,n-k)?

Le combinazioni hanno una simmetria interessante:

$$ \binom{n}{k} = \binom{n}{n-k} $$

Per esempio:

C(5,2)
=
C(5,3)
=
10

Il motivo è più intuitivo della formula.

Scegliere:

2 elementi da tenere

determina automaticamente:

3 elementi da lasciare fuori

e viceversa.

Ogni scelta di due elementi corrisponde quindi a una sola scelta complementare dei tre esclusi.

Con le carte:

$$ \binom{52}{5} = \binom{52}{47} $$

Naturalmente è molto più comodo pensare alle cinque carte che riceviamo che alle 47 che non riceviamo, ma matematicamente i due conteggi sono lo stesso problema visto da lati opposti.

Questa simmetria sarà utile anche per scrivere un algoritmo efficiente.

Una corrispondenza uno-a-uno: la biiezione

Il ragionamento appena fatto ha anche un nome importante.

Una biiezione è una corrispondenza uno-a-uno fra due insiemi: ogni oggetto del primo insieme corrisponde a un solo oggetto del secondo e viceversa.

Qui la biiezione è:

scelta di k elementi da tenere
<->
scelta degli n-k elementi da lasciare fuori

Per esempio, con cinque elementi:

{A, B} scelti
<->
{C, D, E} esclusi

Non abbiamo bisogno di calcolare due formule e osservare che danno lo stesso numero. Abbiamo mostrato direttamente che le due collezioni di scelte possono essere accoppiate senza perdere e senza duplicare nessun caso.

Questo tipo di argomento viene chiamato dimostrazione combinatoria: invece di trasformare simboli algebrici, spiega perché due quantità sono uguali mostrando che contano gli stessi oggetti, oppure oggetti messi in corrispondenza uno-a-uno.

È una prospettiva che useremo spesso: davanti a un'identità combinatoria, prima di manipolare fattoriali conviene chiedersi che cosa stanno contando i due lati?

Fonte didattica di approfondimento: Brian Hopkins, Hands-On Combinatorics, capp. 1–2, dove biiezioni e manipolazioni di oggetti vengono usate per rendere visibili identità su composizioni e coefficienti binomiali.

I casi limite

Se scegliamo zero elementi tra n:

$$ \binom{n}{0} = 1 $$

perché esiste un solo insieme vuoto.

Se scegliamo tutti gli elementi:

$$ \binom{n}{n} = 1 $$

perché esiste una sola selezione che contiene tutto.

La formula conferma entrambi i casi:

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

e:

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

Il fatto che:

$$ 0! = 1 $$

continua quindi a rendere naturali i bordi delle formule combinatorie.

Calcolare le combinazioni in C#

Lo standalone C# associato a questo articolo è:

CombinazioniCarte.cs

Potremmo usare direttamente tre fattoriali:

Fattoriale(n)
/
(Fattoriale(k) * Fattoriale(n - k))

ma possiamo fare di meglio.

Grazie alla simmetria:

$$ \binom{n}{k} = \binom{n}{n-k} $$

possiamo usare il più piccolo tra:

$$ k $$

e:

$$ n-k $$

e costruire il risultato progressivamente.

using System.Numerics;

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

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

    k = Math.Min(k, n - k);

    BigInteger risultato = BigInteger.One;

    for (int i = 1; i <= k; i++)
    {
        risultato *= n - k + i;
        risultato /= i;
    }

    return risultato;
}

Console.WriteLine(Combinazioni(52, 3));
Console.WriteLine(Combinazioni(52, 5));
Console.WriteLine(Combinazioni(90, 6));

Otteniamo:

22100
2598960
622614630

Il calcolo rimane interamente esatto grazie a BigInteger.

Perché la divisione dentro il ciclo è esatta?

Nel codice facciamo:

risultato *= n - k + i;
risultato /= i;

A ogni iterazione il valore ottenuto corrisponde a un coefficiente binomiale intero.

Per esempio, calcolando:

$$ \binom{5}{3} $$

usiamo per simmetria:

$$ \binom{5}{2} $$

e otteniamo progressivamente:

$$ \begin{gathered} i = 1: \ 4 / 1 = 4 \ i = 2: \ 4 \cdot 5 / 2 = 10 \end{gathered} $$

Non stiamo approssimando una divisione floating-point.

BigInteger esegue divisioni intere e, con questa costruzione, il risultato intermedio è esatto a ogni passo.

Enumeriamo un caso piccolo

Prendiamo cinque carte simboliche:

A K Q J 10

e scegliamone tre senza considerare l'ordine.

Le combinazioni possibili sono:

A K Q
A K J
A K 10
A Q J
A Q 10
A J 10
K Q J
K Q 10
K J 10
Q J 10

Sono:

10

e infatti:

C(5,3)
=
5! / (3!2!)
=
10

Possiamo verificarlo anche con un piccolo enumeratore:

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

    for (int i = inizio;
         i <= elementi.Length - (corrente.Length - posizione);
         i++)
    {
        corrente[posizione] = elementi[i];

        EnumeraCombinazioni(
            elementi,
            corrente,
            i + 1,
            posizione + 1,
            ref conteggio);
    }
}

A differenza dell'enumeratore delle disposizioni, dopo aver scelto un elemento proseguiamo soltanto con quelli che vengono dopo.

In questo modo:

A K Q

viene generata una sola volta e non ricompare come:

Q A K

perché per una combinazione sarebbero lo stesso risultato.

La formula giusta dipende dalla domanda, non dagli oggetti

È importante evitare un'associazione troppo rigida come:

carte = combinazioni

Le carte possono produrre problemi di permutazioni, disposizioni oppure combinazioni.

Se mescoliamo tutto il mazzo e ci interessa l'ordine completo:

permutazioni

Se osserviamo le prime tre carte e conta l'ordine:

disposizioni

Se ci interessa soltanto quali tre carte sono presenti:

combinazioni

Gli oggetti sono gli stessi.

È cambiato il significato del risultato che vogliamo distinguere.

Questo è il vero criterio da imparare.

Il punto pratico

Le combinazioni nascono quando scegliamo soltanto k elementi tra n e l'ordine non modifica il risultato.

Partiamo dalle disposizioni:

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

e osserviamo che ogni stessa selezione viene contata:

$$ k! $$

volte, una per ciascun suo ordinamento.

Perciò:

$$ \binom{n}{k} = D(n,k) / k! = n! / (k!(n-k)!) $$

Con tre carte:

C(52,3)
=
22.100

Con una mano di poker:

C(52,5)
=
2.598.960

La domanda da portarsi dietro non è quindi "quale formula devo usare?", ma:

Cambiare l'ordine crea davvero un nuovo risultato nel problema che sto studiando?

Con permutazioni, disposizioni e combinazioni abbiamo ormai quasi tutti gli strumenti fondamentali del conteggio senza ripetizioni.

Nel prossimo articolo cambieremo un'altra condizione: alcuni risultati saranno uguali tra loro.

Cinque dadi possono mostrare, per esempio:

2 2 5 5 5

e scambiare tra loro i tre 5 non produce una nuova configurazione distinguibile.

È il problema delle permutazioni con ripetizioni, e ci permetterà di calcolare la probabilità di ottenere un full con cinque dadi.