Calcolo combinatorio: differenze tra le versioni

Versione delle 19:47, 7 nov 2021

Versione delle 21:43, 9 feb 2022

Riga 1:

{{NN|matematica|febbraio 2022}}

Il '''calcolo combinatorio''' è il termine che denota tradizionalmente la branca della [[matematica]] che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un [[insieme]] finito di oggetti. Il calcolo combinatorio si interessa soprattutto di contare tali modi, ossia le ''configurazioni'' e solitamente risponde a domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." e così via.

Il '''calcolo combinatorio''' è il termine che denota tradizionalmente la branca della [[matematica]] che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un [[insieme]] finito di oggetti. Il calcolo combinatorio si interessa soprattutto di contare tali modi, ossia le ''configurazioni'' e solitamente risponde a domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." e così via.

Più formalmente, dato un insieme <math>S</math> di <math>n</math> oggetti si vogliono contare le configurazioni che possono assumere <math>k</math> oggetti tratti da questo insieme.

Prima di affrontare un problema combinatorio bisogna precisare due punti importanti:

== Definizione ==

* Se l'''ordinamento'' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento (<math>\left\{x,\,y,\,z \right\}</math> è uguale a <math>\left\{z,\,x,\,y\right\}</math>?)

Più formalmente, datoDato un insieme <math>S</math> di <math>n</math> oggetti si vogliono contare le configurazioni che possono assumere <math>k</math> oggetti tratti da questo insieme., e per far ciò bisogna precisare due punti importanti:

* Se si possono avere più ''ripetizioni'' di uno stesso oggetto, ovvero se uno stesso oggetto dell'insieme può o meno essere riusato più volte all'interno di una stessa configurazione.

* Sese l'''ordinamento'' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento;<ref>rispondendo ad esempio alla domanda: (<math>\left\{x,\,y,\,z \right\}</math> è uguale a <math>\left\{z,\,x,\,y\right\}</math>?)</ref>

* Sese si possono avere più ''ripetizioni'' di uno stesso oggetto, ovvero se uno stesso oggetto dell'insieme può o meno essere riusato più volte all'interno di una stessa configurazione.

== Permutazioni ==

Riga 15 ⟶ 17:

Ad esempio le permutazioni degli elementi dell'insieme <math>\left\{a,\,b,\,c \right\}</math> sono <math>3! = 3 \cdot 2 \cdot 1 = 6</math>: <math>abc,\,bac,\,bca,\,cab,\,cba,\,acb</math>.

Un altro esempio può essere il seguente:

In quanti modi possibili si può anagrammare la parola "MONTE"<ref>nella parola MONTE nessuna lettera si ripete</ref>, contando anche le parole prive di significato?

La parola MONTE è composta da <math>5</math> lettere diverse tra loro, quindi <math>n=5</math>;

Le permutazioni possibili sono:

<math>P_5 = 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120</math> modi di anagrammare la parola MONTE.

N.B: nella parola MONTE nessuna lettera si ripete.

Per completare la definizione di fattoriale si fissano i valori seguenti:

Riga 44 ⟶ 48:

<math>\frac{3!}{2! \cdot 1!} = 3</math>, ossia: <math>aab,\,aba,\,baa</math>.

Secondo esempio: In quanti modi è possibile anagrammare la parola "FARFALLA"?

Le lettere contenute nella parola sono <math>n=8</math>; gli elementi che si ripetono sono:

Riga 64 ⟶ 68:

=== Disposizioni semplici (senza ripetizioni) ===

Una '''disposizione semplice''' di lunghezza <math>k</math> di elementi di un insieme <math>S</math> di <math>n</math> oggetti, con <math>k \le n</math>, è una presentazione ordinata di <math>k</math> elementi di <math>S</math> nella quale non si possono avere ripetizioni di uno stesso oggetto.

Per avere il numero di queste configurazioni si considera che il primo componente di una tale sequenza può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math> e così via, sino al <math>k-</math>esimo che può essere scelto in <math>(n-k+1)</math> modi diversi. Pertanto il numero <math>D_{n,\,k}</math> di disposizioni semplici di <math>k</math> oggetti estratti da un insieme di <math>n</math> oggetti è dato da:

:<math>D_{n,k} = n \cdot (n-1) \cdot \dots \cdot (n-k+1)

Riga 80 ⟶ 85:

=== Disposizioni con ripetizioni ===

Una presentazione ordinata di elementi di un insieme nella quale si possono avere ripetizioni di uno stesso elemento si dice '''disposizione con ripetizioni'''. Si cerchi ora il numero delle possibili sequenze di <math>k</math> oggetti estratti dagli elementi di un insieme di <math>n</math> oggetti, ognuno dei quali può essere preso più volte. Si hanno <math>n</math> possibilità per scegliere il primo componente, <math>n</math> per il secondo, altrettante per il terzo e così via, sino al <math>k-</math>esimo che completa la configurazione. Il numero cercato è pertanto:

:<math>

Riga 104 ⟶ 109:

=== Combinazioni semplici (senza ripetizioni) ===

Si chiama '''combinazione semplice''' una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti e non si può ripetere lo stesso elemento più volte. La collezione delle combinazioni di <math>k</math> elementi estratti da un insieme <math>S</math> di <math>n</math> oggetti distinti si può considerare ottenuta dalla collezione delle disposizioni semplici di lunghezza <math>k</math> degli elementi di <math>S</math> ripartendo tali sequenze nelle [[Relazione di equivalenza|classi]] delle sequenze che presentano lo stesso sottoinsieme di <math>S</math> e scegliendo una sola sequenza da ciascuna di queste classi. Ciascuna delle suddette classi di sequenza di lunghezza <math>k</math> contiene <math>k!</math> sequenze, in quanto accanto a una sequenza <math>\sigma</math> si hanno tutte e sole quelle ottenibili permutando i componenti della <math>\sigma</math>. Quindi il numero delle combinazioni semplici di <math>n</math> elementi di lunghezza <math>k</math> si ottiene dividendo per <math>k!</math> il numero delle disposizioni semplici di <math>n</math> elementi di lunghezza <math>k</math>:

:<math>C_{n,k} = \frac{D_{n,k}}{P_k} = \frac{n!}{k!(n-k)!} = {n \choose k}</math>

Riga 117 ⟶ 122:

===Combinazioni con ripetizioni ===

Quando l'ordine non è importante, ma è possibile avere componenti ripetute, si parla di '''combinazioni con ripetizione'''. Il numero di combinazioni con ripetizione di <math>n</math> oggetti di classe <math>k</math> è uguale a quello delle combinazioni senza ripetizione di <math>n+k-1</math> oggetti di classe <math>k</math> ed è quindi uguale a:

:<math>C'_{n,k}=\binom {n+k-1}{k}</math>

Ad esempio, vi sono <math>\binom {2+4-1}{4}=\binom{5}{4}=5</math> modi di distribuire a 2 bambini distinguibili 4 caramelle indistinguibili, contando anche i casi in cui uno dei bambini non riceva alcuna caramella: <math>0-4,\,1-3,\,2-2,\,3-1,\,4-0</math>. Equivalentemente, le combinazioni con ripetizioni informano sul numero di possibili <math>n-</math>uple di addendi non negativi la cui somma sia <math>k</math> (considerando diverse <math>n-</math>uple in cui eguali addendi compaiano in ordine differente); nel suddetto esempio, sono mostrate le cinque diverse coppie di somma <math>4</math>.

Inoltre, le combinazioni con ripetizioni per <math>n</math> oggetti di classe <math>k</math> rappresentano il numero delle derivate parziali di ordine <math>k</math> che al più differiscono fra loro per una funzione a <math>n</math> variabili con derivate continue fino all'ordine <math>k</math> (che rispetta quindi le ipotesi del [[teorema di Schwarz]]).

== Note ==

<references/>

== Bibliografia ==

Riga 131 ⟶ 139:

* [[Disposizione]]

* [[Combinazione]]

* [[Dismutazione (matematica)|Dismutazione]]

* [[Teorema binomiale]]

* [[Fattoriale]]