Presentazione
	Raggruppamenti fra gli elementi di due o più insiemi

Presentazione

Il calcolo combinatorio ha come oggetto il calcolo dei modi con i quali possono essere associati, secondo regole stabilite, gli elementi di due o più insiemi o di uno stesso insieme. Nelle applicazioni può sorgere il problema di conoscere in quanti modi si può presentare un fenomeno, ad esempio ci si può chiedere:

quante sono le possibili graduatorie che si possono ottenere da un gruppo di persone partecipanti ad un concorso o candidati ad una competizione elettorale?

come può essere la tabella dell’ordine di arrivo di una gara di atletica o la classifica delle squadre partecipanti ad un torneo?

in quanti modi si può distribuire un dato numero di regali tra certe persone?

in quanti modi si possono scegliere dei campioni da una popolazione per un’indagine statistica?

in quanti modi si possono assegnare dei lavori a un certo numero d'imprese?

in una mensa aziendale si può scegliere fra tre primi piatti, sei secondi e cinque dessert; quanti tipi di pasti, con almeno una portata diversa, può consumare un dipendente?

un’agenzia di viaggi organizza cinque viaggi dello stesso prezzo per cinque località diverse; quante sono le possibili scelte che possono effettuare tre persone, sia nell’ipotesi che la località scelta da ciascuna persona sia diversa, sia nell’ipotesi che la località scelta coincida?

in un confronto all’americana per riconoscere il colpevole fra sei persone, in quanti modi tre testimoni possono effettuare il riconoscimento?

Il problema di conoscere le risposte alle domande del tipo di quelle semplificate può sembrare banale e, in effetti, lo è se il numero degli elementi è piccolo, poiché in questo caso è sufficiente scrivere esplicitamente tutti i possibili raggruppamenti e contarli, ma quando il numero di elementi è elevato la difficoltà consiste proprio nel formare tutti i raggruppamenti senza tralasciarne alcuno e senza cadere in ripetizioni. Il calcolo combinatorio riveste notevole importanza nella matematica del <<discreto>>, dove il termine <<discreto>> contrapposto a <<continuo>> sta a indicare che gli elementi sono separati e i valori appartengono a N. I raggruppamenti possono essere fatti in vari modi, secondo regole precise. Talvolta occorre tenere conto dell’ordine con il quale gli elementi sono scelti, altre volte interessa solo la natura degli elementi. È bene sottolineare che prima di applicare ai casi concreti le formule che otterremo, si dovranno esaminare attentamente i dati e gli scopi che ci si prefiggono. Poiché la matematica offre <<modelli>> che cercano di interpretare i fatti reali, occorre capire a quale modello bisogna riferirsi per le varie applicazioni.

Raggruppamenti fra gli elementi di due o più insiemi

Disposizioni

Consideriamo un solo insieme e formiamo dei raggruppamenti associando fra loro elementi dell'insieme preso in esame. In generale:

Dato un insieme A di n elementi, si definiscono disposizioni di classe k i raggruppamenti di k elementi scelti fra gli n dell’insieme A tali che ogni raggruppamento differisca dagli altri:

o per la natura degli elementi

o per l’ordine degli elementi.

Le disposizioni si dicono:

semplici, se ogni raggruppamento contiene elementi distinti tra loro; il loro numero s'indica con D_n,k

con ripetizione, se nei raggruppamenti gli elementi di A possono comparire più di una volta; il loro numero s'indica con D’_n,k

Calcoliamo ora il numero delle disposizioni di n elementi di classe k. Consideriamo dapprima le disposizioni con ripetizione. Applicando la definizione si ha subito:

D’_n,1 =n

perché i raggruppamenti di un solo elemento sono tanti quanti gli elementi dell’insieme, in pratica n;

D’_n,2 = n * n = n²

In quanto i raggruppamenti di classe due si ottengono associando a ognuno degli n elementi dell’insieme A tutti gli elementi dello stesso insieme A;

D’_n,3 = n² * n = n³

perché i raggruppamenti di tre elementi si ottengono associando a ogni raggruppamento di due elementi un qualsiasi elemento dell’insieme A. Per k qualsiasi si ha quindi:

D’_n,k = n^k

Perciò: il numero delle disposizioni con ripetizione di n elementi di classe k è n^k .Con ragionamento analogo si può ricavare la formula che esprime il numero delle disposizioni semplici di n elementi di classe k (o, come si suole anche dire, <<a k, a k>>). Applicando la definizione si trova successivamente:

D_n,1 = n

poiché sono n i raggruppamenti di un solo elemento;

D_n,2 = n*(n-1)

perché per formare i raggruppamenti di due elementi distinti, a ogni elemento si può associare uno degli n-1 elementi rimanenti dell’insieme, diversi da quello già considerato;

D_n,3 = n * (n-1) * (n-2)

In quanto per formare i raggruppamenti di tre elementi distinti si deve associare a ognuna delle n*(n-1) coppie già ottenute, uno degli (n-2) elementi rimanenti dell’insieme, diversi da quelli già considerati. Per k qualsiasi, purché k £ n, si ha:

D_n,k = n * (n-1) * (n-2)*…*[n – (k-1)]

Perciò: il numero delle disposizioni semplici di n elementi di classe k è uguale al prodotto di k fattori interi consecutivi decrescenti a partire da n. La condizione k £ n per le disposizioni semplici è imposta dal fatto che si possono fare dei raggruppamenti formati con elementi tutti diversi solo se, al massimo, si prendono tutti gli elementi dell’insieme. Tale limitazione non esiste, ovviamente, per le disposizioni con ripetizione perché, in questo caso, gli elementi possono essere ripetuti quante volte si vuole.

Permutazioni

A un concorso sono stati selezionati tre concorrenti A, B, C. Calcolare quanti sono i possibili modi nei quali si può presentare la graduatoria finale. Al primo posto può esservi uno qualunque dei tre concorrenti, al secondo posto uno dei due rimanenti e al terzo posto l'ultimo dei tre concorrenti. Tutte le graduatorie possibili sono le seguenti:

ABC, ACB, BAC, BCA, CAB, CBA

Che sono in numero di 3*2*1=6. In questo caso i raggruppamenti contengono tutti gli elementi dell'insieme e ogni raggruppamento differisce dagli altri solo per l'ordine secondo cui gli elementi sono presi. Raggruppamenti di questo tipo sono detti permutazioni.

Dato un insieme A di n elementi, si definiscono permutazioni di n elementi (diversi fra loro) i raggruppamenti formati dagli n elementi presi in un ordine qualsiasi.

 

Quindi una permutazione differisce da un'altra solo per l'ordine degli elementi. Dalla definizione segue che le permutazioni coincidono con le disposizioni semplici di classe n, quindi il calcolo del numero delle permutazioni è uguale al calcolo del numero delle disposizioni semplici di n elementi di classe n, in pratica:

P_n=D_n,_n=n(n-1)(n-2)…[n-(n-2)][n-(n-1)]=n(n-1)(n-2) …2*1

Il prodotto dei primi n numeri naturali s'indica con il simbolo n! (che si legge n <<fattoriale>>),cioè si pone:

1*2*3*…*(n -1)* n= n!

Il numero delle permutazioni di n elementi è allora:

P_n= n!

Osserviamo che n! è funzione di n e cresce rapidamente al crescere di n. Si possono esprimere per mezzo dei fattoriali anche le disposizioni semplici di n elementi di classe k. Infatti, dalla relazione:

D_n,k=n(n-1)…(n-k+1)

moltiplicando per (n-k)! numeratore e denominatore si ricava:

Un altro semplice esempio di permutazioni sono gli anagrammi, anche senza significato, che si possono ottenere partendo da una parola qualsiasi. Gli anagrammi della parola <<ROMA>> sono le permutazioni di quattro elementi, quindi sono: P₄=4!=24. Però se nella parola una o più lettere sono ripetute, non tutti gli anagrammi sono diversi fra loro. Se è data una parola di n lettere nella quale una lettera è ripetuta µ volte, un’altra b volte ecc., o, in generale, se è dato un insieme di n elementi dei quali µ sono eguali fra loro, b eguali fra loro ecc., il numero delle permutazioni distinte con elementi ripetuti che si possono ottenere risulta:

Combinazioni

In una classe di 25 studenti si vogliono scegliere 2 allievi come rappresentanti di classe. In quanti modi è possibile effettuare la scelta? Il problema chiede di scegliere due allievi fra 25, ma la scelta non implica un ordinamento. Una qualunque coppia è detta una combinazione, e differisce da un’altra coppia per almeno un elemento che la compone. Precisamente si dà la seguente definizione.

Dato un insieme A di n elementi, si definiscono combinazioni semplici degli n elementi di classe k (con k£ n) i raggruppamenti di k elementi, scelti fra gli n dell’insieme A, tali che ogni raggruppamento differisca dagli altri per la natura degli elementi (senza considerare l’ordine degli elementi).

 

Si deve notare la differenza fra disposizioni e combinazioni semplici: mentre nelle disposizioni si tiene conto dell’ordine, nelle combinazioni non se ne tiene conto. Per determinare il numero di combinazioni di n elementi di classe k ricaviamo una formula che esprime il legame fra il numero delle combinazioni e quello delle disposizioni di n elementi a k, a k. Detta formula si ottiene osservando che le disposizioni di n elementi di classe k si ottengono dalle combinazioni di n elementi di classe k, permutando fra loro i k elementi che costituiscono ciascun raggruppamento.

Indicato con C_n,k il numero delle combinazioni semplici di n elementi di classe k ,si ha:

C_{n,k *} P_k=D_n,k

Cioè:

C_n,k=

Solitamente si scrive: C_n,k=

Il simbolo è detto coefficiente binomiale per il suo uso nello sviluppo delle potenze del binomio. Si possono anche considerare le combinazioni con ripetizione, ossia le combinazioni di n elementi di classe k, in cui gli elementi possono anche essere ripetuti. Partendo, ad esempio, dall’insieme:

A={a, b, c}

le combinazioni di classe due con ripetizione sono le seguenti:

aa, ab, ac, bb, bc, cc

le combinazioni di classe tre con ripetizione, sono:

aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc

La formula che dà il numero delle combinazioni con ripetizione di n elementi di classe k è:

C’_n,k=

Tale relazione, letta in senso inverso, si può anche scrivere così:

C’_n,k=C_{n + k – 1, k}=

Proprietà dei coefficienti binomiali

Varie sono le proprietà dei coefficienti binomiali utilizzati nel calcolo delle probabilità e nell’analisi matematica e qui vogliamo indicarne alcune.

La formula dei coefficienti binomiali si può esprimere per mezzo dei fattoriali:

=

Proprietà simmetrica dei coefficienti binomiali. Si può dimostrare la seguente eguaglianza:

=

Infatti, applicando la formula precedente si ha:

=

La formula si giustifica intuitivamente, pensando che a ogni raggruppamento di k elementi scelti fra gli n, si può fare corrispondere il raggruppamento degli n-k elementi residui e viceversa; quindi il numero delle combinazioni di n elementi di classe k è uguale al numero delle combinazioni degli n elementi di classe (n-k). Questa relazione si applica per il calcolo dei coefficienti binomiali quando k è superiore alla metà di n, ad esempio per calcolare:

Nel paragrafo precedente si sono considerate le combinazioni di classe k e si è posto k£ n. Per k=n si ha immediatamente:

poiché, per convenzione, 0! vale 1.

Applicando la proprietà simmetrica dei coefficienti binomiali si può attribuire, per convenzione, un valore al coefficiente binomiale anche per k = 0; si ha infatti:

Formula di ricorrenza

Infatti si ha:

Questa formula permette di ricavare un algoritmo per il calcolo dei coefficienti binomiali facilmente traducibile in un'applicazione per PC.

Proprietà di Stiefel

Infatti:

Poiché (k+1)!=(k+1)k!, segue:

Raccogliendo a fattor comune:

Questa proprietà permette di costruire una tabella di coefficienti binomiali, nota come triangolo di Tartaglia.