Calcolo combinatorio

Disposizioni con ripetizioni

Supponiamo di lanciare una moneta quattro volte e di annotare ad agni lancio se si presenta la faccia testa T o la faccia croce C.

Ora, chiediamoci:

alla fine dei quattro lanci, in quanti modi ordinati si possono presentare le quattro facce Testa o Croce?

Attenzione! In questo caso gli oggetti distinti sono le due facce della moneta (testa e croce) e ogni gruppo è costituito da quattro oggetti che differiscono per l'ordine ma uno stesso oggetto può comparire 1, 2, 3, 4 volte e quindi non siamo nella situazione precedente delle disposizioni semplici. Nel calcolo combinatorio, il numero dei gruppi ordinati di k oggetti anche ripetuti scelti fra n oggetti (con k maggiore o uguale o minore di n) che differiscono per almeno un oggetto o per il loro ordine prendono il nome di disposizioni con ripetizione di n oggetti di classe k e si indica con il simbolo D^'_n,k.

Come si vede dal grafo ad albero

nel primo lancio possiamo avere:

T (testa ) o C (croce)

nei primi due lanci possiamo avere:

TT    TC    CT    CC

nei primi tre lanci possiamo avere:

TTT    TCT    CTT    CCT

TTC    TCC    CTC    CCC

e nei quattro lanci possiamo avere:

TTT    TCTT    CTTT    CCTT

TTTC    TCTC    CTTC    CCTC

TTCT    TCCT    CTCT    CCCT

TTCC    TCCC    CTCC    CCC

Per il primo lancio abbiamo 2 possibilità, che restano 2 anche per il secondo lancio che formano con le possibilità precedenti 4 coppie ordinate, con il terzo lancio abbiamo ancora 2 possibilità che formano con le possibilit precedenti 8 coppie ordinate, con il quarto lancio abbiamo ancora 2 possibilità che formano con le possibilità precedenti 16 coppie ordinate. Pertanto le disposizioni con ripetizione di 2 oggetti distinti di classe 4 sono:

D^'_2,4=2⋅2⋅2⋅2=2⁴=16

In generale, le disposizioni con ripetizione di n oggetti distinti di classe k sono:

D^'_n,k = n^k