Differenze tra le versioni di "Disposizione"

nessun oggetto della modifica
{{Nota disambigua|la disposizione in senso filosofico|Abito (filosofia)}}
 
Nel [[calcolo combinatorio]], se ''n'' e ''k'' sono due numeri [[numero intero|interi]] positivinon negativi, si definisce '''disposizione''' di ''n'' elementi a ''k'' a ''k'' (oppure di ''n'' elementi di classe ''k'', oppure di ''n'' elementi presi ''k'' alla volta) ogni sottoinsieme ''ordinato'' di ''k'' elementi estratti da un insieme di ''n'' elementi tale che i sottoinsiemi differiscono se presentano qualche elemento diverso oppure se presentano gli stessi elementi ma ordinati diversamente. Talvolta ''k'' viene chiamato ''numero di posti'' e la disposizione di ''n'' elementi in ''k'' posti viene chiamata ''k''-disposizione.
 
Se nei sottoinsiemi ''non sono ammessi'' elementi ripetuti si parla di '''disposizioni semplici''' altrimenti di [[disposizioni con ripetizione]]: nel primo caso deve essere <math>k \le n.</math>
 
Il numero di disposizioni semplici (denotate con il simbolo <math>D_{n, k}</math>) di n elementi a k a k è pari a:
:<math>
D_{n, k} = n(n-1)(n-2) \cdot \cdot \cdot (n-k+1) = \frac{n!}{(n-k)!}
</math>
 
Il numero di disposizioni con ripetizione (denotate con il simbolo <math>D^'_{n, k}</math>) di n elementi a k a k è pari a:
:<math>
D^'_{n, k} = n^k
</math>
== Disposizioni semplici ==
Siano ''A'' un [[insieme]] finito di [[cardinalità]] ''k'' e ''B'' un insieme finito di cardinalità ''n'', con 0 ≤ ''k'' ≤ ''n''. Sia inoltre ''F''<sub>k</sub> l'insieme delle [[funzione iniettiva|funzioni iniettive]] ''f'': ''A'' → ''B''.
 
Il numero di disposizioni semplici, (denotate con il simbolo <math>D_{n, k},</math>) di <math>n</math> elementi a <math>k</math> a <math>k</math> è pari a:
Sia ''F''<sub>k-1</sub> l'insieme delle funzioni iniettive da un sottoinsieme di ''A'' di cardinalità ''k''–1 in ''B''. Ciascuna di tali funzioni è un insieme di ''k''-1 [[Coppia (matematica)|coppie]] (''a'',''b''), con ''a'' appartenente al sottoinsieme di ''A'' e ''b'' appartenente a ''B'', tali che ciascun ''a'' e ciascun ''b'' compaiano in una sola di esse.
 
:<math>D_{n, k} = n(n-1)(n-2) \cdot \cdot \cdot (n-k+1) = \frac{n!}{(n-k)!}.</math>
Sia |''F''<sub>k-1</sub>| il numero di tali funzioni. Il numero delle funzioni iniettive da ''A'' in ''B'' si ottiene aggiungendo, per ciascuna funzione, il numero delle coppie (''a'',''b'') in cui ''a'' e ''b'' non siano già presenti in alcuna coppia. Vi è un solo ''a'', ma vi sono ''n'' – (''k''-1) elementi ''b'', ovvero ''n'' – (''k''-1) nuove coppie. Si ha quindi la [[relazione di ricorrenza|ricorrenza]]:
:<math>\begin{align}|F_k|&=(n-k+1)|F_{n-1}|\\&=(n-k+1)(n-k+2)\cdots(n-1)|F_1|\\&=(n-k+1)(n-k+2)\cdots(n-1)(n)=\frac{n!}{(n-k)!}\end{align}</math>
essendo |''F''<sub>1</sub>| = ''n'', in quanto vi sono ''n'' coppie (''a'',''b'') in cui ''a'' sia fissato e ''b'' sia scelto tra gli ''n'' elementi di ''B''.
 
La formula si può ottenere usando la seguente formalizzazione. Siano ''A'' un [[insieme]] finito di [[cardinalità]] ''k'' e ''B'' un insieme finito di cardinalità ''n'', con 0 ≤ ''k'' ≤ ''n''. Sia inoltre ''F''<sub>k</sub> l'insieme delle [[funzione iniettiva|funzioni iniettive]] ''f'': ''A'' → ''B''. Sia ''F''<sub>k-1</sub> l'insieme delle funzioni iniettive da un sottoinsieme di ''A'' di cardinalità ''k''–1 in ''B''. Ciascuna di tali funzioni è un insieme di ''k''-1 [[Coppia (matematica)|coppie]] (''a'',''b''), con ''a'' appartenente al sottoinsieme di ''A'' e ''b'' appartenente a ''B'', tali che ciascun ''a'' e ciascun ''b'' compaiano in una sola di esse. Sia |''F''<sub>k-1</sub>| il numero di tali funzioni. Il numero delle funzioni iniettive da ''A'' in ''B'' si ottiene aggiungendo, per ciascuna funzione, il numero delle coppie (''a'',''b'') in cui ''a'' e ''b'' non siano già presenti in alcuna coppia. Vi è un solo ''a'', ma vi sono ''n'' – (''k''-1) elementi ''b'', ovvero ''n'' – (''k''-1) nuove coppie. Si ha quindi la [[relazione di ricorrenza|ricorrenza]]:
Il numero delle funzioni iniettive da un insieme di cardinalità ''k'' in uno di cardinalità ''n'' si indica anche col simbolo:
 
:<math>\begin{align}|F_k|&=(n-k+1)|F_{n-1}|\\&=(n-k+1)(n-k+2)\cdots(n-1)|F_1|\\&=(n-k+1)(n-k+2)\cdots(n-1)(n)=\frac{n!}{(n-k)!},\end{align}</math>
 
essendo |''F''<sub>1</sub>| = ''n'', in quanto vi sono ''n'' coppie (''a'',''b'') in cui ''a'' sia fissato e ''b'' sia scelto tra gli ''n'' elementi di ''B''. Il numero delle funzioni iniettive da un insieme di cardinalità ''k'' in uno di cardinalità ''n'' si indica anche col simbolo:
:<math>(n)_k=\frac{n!}{(n-k)!}</math>
 
Nella terminologia combinatoria classica, il numero delle applicazioni iniettive da un insieme di cardinalità ''k'' in un insieme di cardinalità ''n'' viene detto numero delle ''disposizioni semplici'' di ''n'' oggetti presi ''k'' alla volta, o di classe ''k'', e si indica con ''D''<sub>n,k</sub>.
 
Infine si può notare che c'è una relazione tra le disposizioni e le permutazioni; infatti nel caso in cui <math>k</math> sia uguale a <math>n</math> si avrebbe:
Ad esempio, se ''n=5'' e ''k=3'' e come oggetti consideriamo le lettere A, B, C, D ed E, allora le disposizioni possibili sono le seguenti 5!/(5-3)! = 120/2 = 60:
 
:<math>D_{n,n} = \frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!</math>
 
cioè le [[Permutazione|permutazioni]] di <math>n</math> elementi.
 
=== Esempio ===
 
Ad esempio, seSe ''n=5'' e ''k=3'' e come oggetti consideriamo le lettere A, B, C, D ed E, allora le disposizioni possibili sono le seguenti 5!/(5-3)! = 120/2 = 60:
 
:ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED
Generalizzando, ogni volta che si estrae una lettera, il numero delle lettere che si possono estrarre diminuisce di uno; se nel sacchetto ci sono ''n'' lettere e vogliamo estrarne ''k'' avremo:
 
:<math>D_{n,k} = n(n-1)(n-2) \cdots (n-k+1),</math>
 
ovverocioè un prodotto di ''k'' fattori pari a ''n'' diminuito di 0, 1, ..., (''k''-1). Moltiplicando e dividendo tale prodotto per (''n''-''k'')!, si ottiene la formula data sopra:
 
:<math>\begin{align}D_{n,k} &= n(n-1)(n-2) \cdots (n-k+1)\\&= \frac{n(n-1)(n-2) \cdots (n-k+1)(n-k)(n-k-1)\cdots 1}{(n-k)(n-k-1)\cdots 1}\\&=\frac{n!}{(n-k)!}.\end{align}</math>
 
== Disposizioni con ripetizione ==
Infine si può notare che c'è una relazione tra le disposizioni e le permutazioni; infatti nel caso in cui k sia uguale a n si avrebbe:
:<math>D_{n,n} = \frac{n!}{(n-n)!}=\frac{n!}{0!}=\frac{n!}{1}=n!</math>
 
cioè le [[Permutazione|permutazioni]] di n elementi.
 
Il numero di disposizioni con ripetizione, (denotate con il simbolo <math>D^'_{n, k},</math>) di <math>n</math> elementi a <math>k</math> a <math>k</math> è pari a:
== Disposizioni con ripetizione ==
:<math>D^'_{n, k} = n^k.</math>
Una [[Funzione (matematica)|funzione]] da un insieme ''A'' in un insieme ''B'' può essere vista come un insieme di coppie (''a'',''b'') tale che vi siano tante coppie quante sono gli elementi ''a'' di ''A'' e che non vi sia alcun ''a'' presente in più di una coppia. Possono invece esservi nessuna o più coppie aventi, come secondo membro, un dato elemento ''b'' di ''B''.
 
DatiLa formula si può ottenere usando la seguente formalizzazione. Una [[Funzione (matematica)|funzione]] da un insieme ''A'' diin cardinalitàun insieme ''kB'' edpuò essere vista come un insieme ''B'' di cardinalitàcoppie (''na'', con ''nb'') etale ''k''che interivi positivi,siano iltante numerocoppie dellequante funzionisono dagli elementi ''Aa'' indi ''BA'' èe datoche danon vi sia alcun ''na''<sup>k</sup>, presente in quantopiù ciascunadi delleuna ''k''coppia. Possono invece esservi nessuna o più coppie può avereaventi, come secondo membro, unoun qualsiasidato deglielemento ''nb'' elementi di ''B''. Ad esempio, il numero delle funzioni daDati un insieme di 2 elementi {''aA'', di cardinalità ''bk''} ined un insieme ''B'' di 10cardinalità elementi {1,...,10} è 10<sup>2</sup>, in quanto si hanno 10 coppie del tipo (''an'', con ''xn''), dovee ''xk'' =interi 1,2,...,10positivi, eil pernumero ciascunadelle difunzioni esseda 10 coppie del tipo (''bA'', in ''xB''). Ciascuna delle funzioni cercate è costituitadato da una delle dieci coppie il cui primo elemento sia ''an''<sup>k</sup>, ein daquanto unaciascuna delle dieci il cui primo elemento sia ''bk''; ilcoppie numeropuò diavere talicome funzionisecondo èmembro quindiuno datoqualsiasi dalladegli cardinalità''n'' del [[prodotto cartesiano]] dei due insiemielementi di dieci''B''. coppie: 10&times;10=10<sup>2</sup>.
 
Nella terminologia combinatoria classica, il numero delle funzioni da un insieme di cardinalità ''k'' in uno di cardinalità ''n'' viene detto numero delle ''disposizioni con ripetizione'' di ''n'' oggetti ''k'' a ''k'', o di classe ''k''; a differenza delle disposizioni semplici, ''k'' può essere maggiore di ''n''.
 
=== Esempi ===
 
Il numero delle funzioni da un insieme di 2 elementi {''a'', ''b''} in un insieme di 10 elementi {1,...,10} è 10<sup>2</sup>, in quanto si hanno 10 coppie del tipo (''a'', ''x''), dove ''x'' = 1,2,...,10, e per ciascuna di esse 10 coppie del tipo (''b'', ''x''). Ciascuna delle funzioni cercate è costituita da una delle dieci coppie il cui primo elemento sia ''a'' e da una delle dieci il cui primo elemento sia ''b''; il numero di tali funzioni è quindi dato dalla cardinalità del [[prodotto cartesiano]] dei due insiemi di dieci coppie: 10&times;10=10<sup>2</sup>.
 
L'esempio sopra proposto può essere reinterpretato come segue. Dati 10 oggetti distinti, il numero delle presentazioni di 2 di tali elementi, anche non diversi tra loro, è 10<sup>2</sup>; in particolare, con le 10 cifre da 0 a 9 si possono comporre 100 numeri di due cifre: 00, 01, ..., 09, 10, 11, ..., 19, 20, 21, 22, ...., 99.