Alcuni problemi di calcolo combinatorio (draft)

Consideriamo un insieme A finito di n elementi:

$\huge A = \{ a_1, a_2, ..., a_n \}$

Gli elementi dell'insieme A potrebbero ad es. essere le 52 carte di un mazzo da gioco (13 per ogni seme ad esclusione dei jolly) oppure ancora le 26 lettere dell'alfabeto.

Questi elementi possono essere combinati: ad esempio dall'insieme delle lettere possiamo formare parole oppure possiamo estrarre in vari modi 5 carte dal mazzo da gioco.

I modi per combinare gli elementi sono 2:

• non ammettendo duplicati: ad es. $a_1, a_1, a_5$ non è ammesso perchè $a_1$ è presente 2 volte, mentre $a_3, a_5, a_9$ è ammessa perchè ogni elemento è preso 1 volta sola. Non ammettendo duplicati possiamo combinare fino a un massimo di n elementi (dove n è il numero di elementi dell'insieme)
• ammettendo duplicati: possiamo avere ad. es $a_1, a_1, a_2$ (in cui $a_1$ è presente 2 volte). Ammettendo duplicati possiamo avere combinazioni con un numero qualsiasi di elementi (anche maggiore di n).

Le combinazioni possono essere di 2 tipi:

• ordinate: e' importante l'ordine degli elementi. La combinazione $a_1, a_3, a_5$ è differente da $a_5, a_3, a_1$ anche se ha gli stessi elementi.
• non ordinate: l'ordine non e' importante. La combinazione $a_1, a_3, a_5$ è uguale a $a_5, a_3, a_1$ perchè ha gli stessi elementi.

Le ordinate sono dette permutazioni, le non ordinate combinazioni .

Ora chiediamoci:

Non ammettendo duplicati quante combinazioni ordinate posso avere?

Estraiamo una carta dal mazzo senza rimetterla nel mazzo. La 1° estrazione avrà quindi 52 combinazioni possibili (52 - 1 + 1). La 2° avrà 51 estrazioni possibili (52 - 2 + 1). La terza 50, e così via fino all' r° estrazione che avrà 52 - r + 1 possibili estrazioni.

Il numero di combinazioni possibili per r estrazioni da un insieme di n elementi sarà quindi:

E = n * (n-1) * ... * (n-r+1)

Ricordando che il fattoriale di un numero n è:

n! = n * (n-1) * (n-2) * ... * 2 * 1

Possiamo riscrivere E in questo modo:

$\huge{E=\frac{n*(n-1)*...*(n-r+1)*(n-r)*(n-r-1)*...*2*1}{(n-r)*(n-r-1)*...*2*1}}$

che può essere riscritta come:

$\huge{E=\frac{n!}{(n-r)!}}$

Non ammettendo duplicati quante combinazioni non ordinate posso avere?

Nella sezione precedente abbiamo calcolato il numero di estrazioni ordinate e distinte. Queste estrazioni distinte possono essere raggruppate in estrazioni con gli stessi elementi. Ad esempio:

Con r=3 possiamo avere a_2, a_5, a_7 oppure a_5, a_2, a_7, oppure a_7, a_5, a_2 etc. che nel passo precedente sono conteggiate esattamente 6 volte.

Gli elementi a_2, a_5, a_7 possono essere considerati come un insieme di cui vogliamo calcolare il numero di combinazioni possibili. In questo caso n=3 e r=3.

Le combinazioni conteggiate nella sezione precedente possono quindi essere raggruppate per stessi elementi che andranno quindi conteggiati 1 sola volta.

In sostanza, in questo caso avremo:

$\huge{EN=\frac{E}{r!}=\frac{n!}{(n-r)!*r!}}$

Ammettendo duplicati quante combinazioni ordinate posso avere?

Estraiamo una carta dal mazzo, prendiamo nota e la rimettiamo nel mazzo. Poi passiamo all'estrazione successiva comportandoci allo stesso modo fino a r estrazioni.

Se r = 1 abbiamo 52 possibili combinazioni. Se r = 2 ogni singola carta del mazzo della prima estrazione può essere combinata con 52 possibili carte della seconda estrazione. Avremo quindi 52^2 combinazioni. Più in generale, considerando con n come il numero di elementi dell'insieme di partenza e con r il numero di estrazioni avremo:

E = n^r

Ammettendo duplicati quante combinazioni non ordinate posso avere?

Per dimostrare questo caso ci si riconduce a quello delle "combinazioni ordinate che non ammettono duplicati"

Supponiamo voler contare in quanti modi possiamo formare 3 sottoinsiemi a partire dagli elementi dell'insieme A= {a, b, c, d, e}. Ad es. {a, b}, {c, d}, {e} oppure {a}, {b,c}, {d, e}

Possiamo rappresentare gli elementi dell'insieme e i gruppi utilizzando | (barre). Ad es.:

a b | c d | e ({a,b}, {c,d}, {e}) oppure | | a b c d e (vuoto, vuoto, {a,b,c,d,e})

per creare i 3 gruppi ci servono 3 - 1 = 2 barre.

Considerando le barre come elementi distinti possiamo ricondurci alla situazione delle combinazioni ordinate che non ammettono duplicati. Supponiamo che l'insieme di partenza abbia n elementi, e il numero di gruppi sia r allora: ( (n+r-1)! | r! ) <- binomiale