Disposizioni

Si vuol conteggiare il numero di applicazioni o applicazioni iniettive che si possono costruire, quando dominio e codominio sono insiemi finiti.



Disposizioni con ripetizione

Ci proponiamo di calcolare il numero delle applicazioni che si possono creare fra due insiemi finiti. Per esempio supponiamo che A sia un insieme di tre oggetti: a, b, c. Ci domandiamo in quanti modi diversi essi possano essere posti in cinque cassetti tenendo presente che possono anche essere contenuti tutti in un unico cassetto. Indichiamo con B = {1,2,3,4,5} l'insieme dei cassetti. Consideriamo l'oggetto a; esso può essere mandato in uno dei cinque cassetti, dunque per quello che riguarda a, ci sono cinque possibilità diverse. Consideriamo ora l'oggetto b: esso può essere mandato in uno qualsiasi dei cinque cassetti, indipendentemente dal modo con cui è stato collocato a. Analogamente si procede per c. Dunque ci sono in tutto 5*5*5 = 125 distinte applicazioni dell'insieme A nell'insieme B. A questo punto si può passare a considerare una situazione generale: A sia un insieme di k oggetti, e B un insieme di n oggetti. Il numero di tutte le applicazioni di A in B è dato da: n*n*n*...*n = n k



Disposizioni semplici

Un'altro problema è quello di contare le applicazioni iniettive di A in B. Partendo da un esempio, si tratta di riporre tre oggetti in cinque cassetti, in modo che non ne vada più di uno in ciascun cassetto. Cominciamo con l'oggetto a: esso può essere collocato in uno dei cinque cassetti; quindi ci sono cinque possibilità. L'oggetto b può essere collocato solo in uno dei quattro cassetti rimasti liberi. Quando si tratta di collocare l'oggetto c, sono già stati impegnati due cassetti, quindi ci sono solo tre possibilità. Potrebbe essere lo stesso nel conteggiare il numero dei dei modi in cui si possono disporre studenti in banchi, col numero di banchi superiore al numero degli studenti. Dunque, il numero delle applicazioni iniettive di un insieme di tre elementi in un insieme di cinque elementi è: 5*4*3 = 60 (Naturalmente, il numero è inferiore a quello dell'insieme delle applicazioni arbitrarie). Consideriamo ora il caso generale: A è un insieme di k elementi, B un insieme di n elementi. Se si vuole che siano possibili applicazioni iniettive, deve essere k minore di n, nell'esempio il numero dei cassetti non deve essere inferiore a quello degli oggetti. Possiamo ripetere, in termini generali, il ragionamento fatto: per collocare il primo oggetto di A ci sono n possibilità, per collocare il secondo oggetto di A ci sono n-1 possibilità, per collocare il terzo oggetto di A ci sono n-2 possibilità. Dunque il numero delle applicazioni iniettive, che indicheremo con D(n,k) è dato dalla formula: D(n,k) = n(n-1)(n-2)...(n-k+1).