Il trucco dei delimitatori nel calcolo combinatorio

Immaginiamo la seguente situazione. Quattro persone si recano al voto; entrano in cabina, compilano la scheda elettorale e poi la depositano all’interno di una delle quattro urne disponibili. Le urne sono identiche e indistinguibili; ciascun elettore entra a turno, quindi non vedo ciò che ha fatto chi lo ha preceduto. Al termine delle votazioni qual è la distribuzione delle schede nelle urne? Può capitare che finisca una scheda in ciascuna urna, che tutte le schede finiscano nella stessa urna e tutte le configurazioni intermedie tra queste due. Quante sono le configurazioni possibili?

Tutti i problemi di questo tipo possono essere risolti applicando un piccolo trucco, detto dei delimitatori. La situazione in cui troviamo una scheda in ciascuna urna può essere rappresentata come segue (gli asterischi schematizzano le schede, le barre verticali sono i delimitatori tra le urne):

* | * | * | *

La situazione in cui, ad esempio, ci sono tre schede nella seconda urna e una nella quarta è invece rappresentabile come indicato sotto:

| *** || *

Enumerare tutte le possibili configurazioni significa determinare tutti i modi in cui possiamo disporre i tre delimitatori tra i sette oggetti costituiti da asterischi e barre verticali o – equivalentemente – determinare tutti i modi in cui possiamo disporre quattro asterischi tra i sette oggetti costituiti da asterischi e barre verticali.

In termini matematici possiamo scrivere:

C(7,3) = C(7,4) = 7!/(3!4!) = 7!/(4!3!) = 35

dove C(n,k) indica le combinazioni di n oggetti presi a gruppi di k.

Passiamo ora al caso generale. Date n urne avremo d = n – 1 delimitatori. Quindi le configurazioni possibili sono:

C(n+d,d) = C(2n-1,n-1) = (2n – 1)!/((n – 1)!n!)

Nel caso sopra siamo partiti da una situazione di quattro schede con quattro urne e abbiamo derivato una formula generale nel caso di n schede e n urne; il metodo permette tuttavia un’ulteriore generalizzazione: quella di n schede e m urne. In tal caso la formula da applicare è la seguente:

C(n+m-1,m-1) = (n + m – 1)!/((m – 1)!n!)

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...