• Non ci sono risultati.

Elementi di calcolo combinatorio

N/A
N/A
Protected

Academic year: 2021

Condividi "Elementi di calcolo combinatorio"

Copied!
5
0
0

Testo completo

(1)

Elementi di calcolo combinatorio

A.1 Disposizioni, combinazioni, permutazioni

Il calcolo combinatorio si occupa di alcune questioni inerenti allo studio delle modalit`a secondo cui si possono raggruppare degli oggetti dati.

Supponiamo dati n oggetti distinti di natura qualsiasi, che indicheremo semplicemente con i numeri 1, 2, . . . , n. Fissiamo poi un numero positivo k, non superiore a n, e ci proponi- amo di formare con gli n oggetti dati tutti i possibili gruppi di k oggetti. Nella formazione di tali gruppi si possono seguire due diversi criteri e cio`e si pu`o pensare a gruppi ordinati oppure a gruppi non ordinati.

Considerare gruppi ordinati significa che in ogni gruppo si tiene conto dell’ordine con cui compaiono gli oggetti che lo compongono, vale a dire che due gruppi si considerano diversi, non solo se c’`e almeno un oggetto che compare in uno e non nell’altro, ma anche se, essendo i due gruppi costituiti dai medesimi oggetti, `e per`o diverso l’ordine secondo cui questi si susseguono nei due gruppi. Quando con gli n oggetti dati interessa formare tutti i possibili gruppi ordinati di k oggetti, si dice che si considerano le disposizioni degli n oggetti dati di classe k.

Considerare invece gruppi non ordinati vuol dire che in ogni gruppo non si tiene alcun conto dell’ordine secondo il quale si susseguono gli oggetti nel gruppo stesso, cio`e due gruppi si considerano diversi soltanto se differiscono in almeno un oggetto. Quando i gruppi di k oggetti che si possono formare con gli n oggetti dati si considerano non ordinati, si dice che essi formano le combinazioni degli n oggetti di classe k.

Ci chiediamo ora quante siano le disposizioni di classe k di n oggetti. Per formare una di tali disposizioni occorre scegliere l’oggetto che si vuole porre al primo posto (questa scelta si pu`o fare in n modi diversi), poi l’oggetto che deve occupare il secondo posto (scelta che pu`o ora farsi in n − 1 modi diversi), quindi l’oggetto relativo al terzo posto (per il quale sussistono n − 2 possibilit`a di scelta), e cos`ı via fino alla scelta dell’oggetto da porre al k-esimo posto (per il quale ci sono ancora n − (k − 1) possibilit`a). E poich´e ogni scelta del primo oggetto pu`o associarsi con una qualunque del secondo, del terzo, . . . , del k-esimo oggetto, si conclude che visono n(n − 1)(n − 2) . . . (n − k + 1) modi diversi di formare una delle disposizioni cercate e pertanto:

Il numero delle disposizioni di classe k di n oggetti `e espresso da

n(n − 1)(n − 2) . . . (n − k + 1) (A.1)

ossia dal prodotto di k numeri consecutivi, decrescenti a partire da n.

(2)

Appendice A. Elementi di calcolo combinatorio

Come caso particolare si pu`o prendere k = n; ogni gruppo contiene allora tutti gli n oggetti considerati ed un gruppo differisce da un altro soltanto per l’ordine con cui si susseguono gli oggetti. In tal caso, invece di usare il termine disposizione di classe n degli n oggetti, si parla di permutazione di essi.

Come caso particolare della (A.1) si ha che il numero delle permutazioni di n oggetti

`e dato da n(n − 1)(n − 2) . . . 1, cio`e dal prodotto dei primi n numeri interi. Si ha spesso occasione di considerare tale prodotto, che viene chiamato il fattoriale di n e si indica con il simbolo n!. Si pu`o dunque dire che:

Il numero delle permutazioni di n oggetti `e espresso da

n! = 1 · 2 · 3 . . . (n − 1) · n (A.2) ossia dal fattoriale di n.

Osserviamo che risulta evidente la relazione n! = (n − 1)! n

che vale per n > 2; conviene renderla convenzionalmente valida anche per n = 1, ponendo per definizione

0! = 1. (A.3)

Passiamo ora a valutare il numero delle combinazioni di classe k di n oggetti. Supponiamo formate tutte queste combinazioni e, fissatane una qualsiasi, pensiamo di permutare i k oggetti che la costituiscono. Da tale fissata combinazione sorgono allora k! gruppi ordinati, ciascuno di k oggetti scelti tra gli n dati. Immaginando di ripetere questa operazione per tutte le combinazioni, otteniamo evidentemente le disposizioni di classe k degli stessi n oggetti. Tenito conto della (A.1), risulta quindi che il numero delle combinazioni `e dato dall’epressione

n(n − 1)(n − 2) . . . (n − k + 1)

k! che si suole indicare brevemente col simbolo n k



e prende il nome di coefficiente binomiale (per il motivo che vedremo nel seguito). Si pu`o quindi sintetizzare che:

Il numero delle combinazioni di classe k di n oggetti `e espresso da n(n − 1)(n − 2) . . . (n − k + 1)

k! (A.4)

ossia dal coefficiente binomiale

n k



. (A.5)

(3)

A.2 Propriet`a dei coefficienti binomiali

Esaminiamo alcune semplici propriet`a dei coefficienti binomiali (A.5) i quali hanno senso se k 6 n. Se nella frazione (A.4) moltiplichiamo numeratore e denominatore per (n − k)!, otteniamo la formula

n k



= n!

k!(n − k)! (A.6)

la quale vale per k = 1, 2, . . . , n. Il primo membro della (A.6) non ha senso per k = 0;

tuttavia viene dato convenzionalmente un significato anche al coefficiente che si ottiene per k = 0, visto che, tenendo conto della (A.3), si pu`o scrivere

n 0



= n!

0! n! = n!

n! = 1.

Dunque, fissato il numero intero n > 0, restano definiti gli n + 1 coefficienti binomiali

n 0



= 1, n 1

 , n

2

 , . . . ,

 n

n − 1

 , n

n



= 1 (A.7)

dati dalla formula (A.6). Si noti che da questa segue la relazione

n k



=

 n

n − k



(A.8) che esprime una propriet`a di simmetria dei numeri della successione (A.7) (il primo `e uguale all’ultimo, il secondo al penultimo, ecc.).

Dando a n i successivi valori 0, 1, 2, 3, . . . e scrivendo su righe successive i corrispondenti numeri (A.7) si ottiene il cosiddetto triangolo aritmetico di Tartaglia

0 0



1 0

 1 1



2 0

 2 1

 2 2



3 0

 3 1

 3 2

 3 3



4 0

 4 1

 4 2

 4 3

 4 4



5 0

 5 1

 5 2

 5 3

 5 4

 5 5



. . . .

(4)

Appendice A. Elementi di calcolo combinatorio

vale a dire

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

. . . .

(A.9)

Per 1 6 k 6 n − 1 sussiste la relazione

n k



=n − 1 k − 1



+n − 1 k



(A.10) la quale si dimostra osservando che per la (A.6) si ha

n − 1 k − 1



+n − 1 k



= (n − 1)!

(k − 1)! (n − k)! + (n − 1)!

k! (n − k − 1)! = (n − 1)! k + (n − 1)! (n − k)

k! (n − k)! = (n − 1)! (k + n − k)

k! (n − k)! = n!

k! (n − k)! =n k

 .

La (A.10) esprime una propriet`a del triangolo aritmetico di Tartaglia in base alla quale in ogni riga un qualsiasi numero (esclusi il primo e l’ultimo) si ottiene sommandone due della riga precedente, come si vede dalla (A.9).

A.3 Disposizioni e combinazioni con ripetizione

Parlando di disposizioni e di combinazioni di classe k di n oggetti si `e tacitamente supposto che, in ogni gruppo (ordinato o no) di k oggetti, un determinato oggetto non potesse com- parire pi`u di una volta. Rimuovendo questa restrizione, cio`e ammettendo che, in ogni gruppo di k oggetti, un medesimo oggetto possa comparire anche pi`u volte, si parler`a di disposizioni o combinazioni con ripetizione. Naturalmente non sar`a pi`u necessario supporre k 6 n; pu`o essere benissimo k > n.

Per contare quante sono le disposizioni con ripetizione di classe k di n oggetti basta osservare che quando si vuole formare una tale disposizione, ciascuno dei k oggetti che la

(5)

compongono si pu`o scegliere in n modi diversi e perci`o si hanno in tutto n · n . . . · n = nk possibilit`a di scelta. Dunque:

Il numero delle disposizioni con ripetizione di classe k di n oggetti `e dato nk.

Meno semplice `e il computo delle combinazioni con ripetizione; si ha al riguardo il seguente risultato:

Il numero delle combinazioni con ripetizione di classe k di n oggetti `e dato dal coefficiente binomiale:

n + k − 1 k

 .

A.4 Potenza di un binomio

Dato un binomio a+b ci proponiamo di calcolarne la potenza (a+b)n(con n intero positivo).

Sviluppando, con le note regole dell’algebra, il prodotto

(a + b)(a + b) . . . (a + b), (A.11)

ove il numero dei fattori `e n, si ottiene una somma di tanti termini ognuno dei quali `e il prodotto di n fattori, alcuni uguali ad a ed i rimanenti a b. Se, in uno qualunque di tali termini, diciamo k il numero dei fattori b (pu`o essere k = 0, 1, . . . , n), sar`a n − k il numero dei fattori a e quindi il termine considerato avr`a il valore an−kbk. Va tenuto conto per`o che, fissato il valore di k, di termini uguali a an−kbk non ne esiste in generale uno solo, ma ne esistono tanti quanti sono i modi di scegliere fra gli n fattori a + b del prodotto (A.11) quei k dai quali si vogliono prelevare i k fattori b che compaiono in an−kbk; tali modi sono evidentemente tanti quante sono le combinazioni di classe k di n oggetti. Dunque, fissato k, i termini uguali a an−kbk danno, nello sviluppo del prodotto (A.11), un contributo uguale a

n k



an−kbk.

Dando successivamente a k i valori 0, 1, 2 . . . , n e sommando i predetti contributi, dedu- ciamo che lo sviluppo cercato `e

(a + b)n=n 0



an+n 1



an−1b +n 2



an−2b2+ . . . +n n

 bn, o brevemente

(a + b)n=

n

X

k=0

n k



an−kbk. (A.12)

Nella (A.12), detta formula del binomio, i coefficienti dei prodotti an−kbksono numri che si trovano su una stessa riga del triangolo di Tartaglia, donde il nome di coefficienti binomiali dato ai numeri di tale triangolo.

Riferimenti

Documenti correlati

Alcune terne che nell’esempio precedente erano distinte adesso sono equivalenti; più precisamente, a ogni terna di qualificati corrispondono 6 (cioè, 3!) configurazioni del podio:

[r]

Se la gelateria offre un solo gusto di gelato, possiamo scegliere un solo gelato (ad esempio due palline di vaniglia, “vaniglia- vaniglia”).. Se la gelateria offre due varietà

I metalli dei gruppi 13, 14 e 15 sono elementi duttili e malleabili, ma diversi dagli elementi di transizione, a differenza dei quali, infatti, non mostrano stati di

Partiamo da tutte le terne possibili (ossia le disposizioni semplici D 5,3 ) e osserviamo che le permutazioni P 3 di ognuno dei gruppi di tre lettere non

• Tutti gli altri elementi sono stati originariamente prodotti a partire da atomi di idrogeno o da altri elementi che a loro volta si erano originariamente generati a partire da

Calcolare la probabilità che, scelta a caso una coppia di studenti della 5 a A, questa sia formata da alunni di

[r]