Calcolo combinatorio: differenze tra le versioni

Versione delle 21:43, 9 feb 2022

Versione attuale delle 22:28, 18 mag 2025

(18 versioni intermedie di 10 utenti non mostrate)

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.

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.

== Definizione ==

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, e per far ciò bisogna precisare due punti importanti:

Riga 12 ⟶ 10:

=== Permutazioni semplici (senza ripetizioni) ===

Una [[permutazione]] di un insieme di oggetti è una presentazione ordinata, cioè una sequenza, dei suoi elementi nella quale ogni oggetto viene presentato una ed una sola volta. Per contare quante siano le permutazioni di un insieme con <math>n</math> oggetti, si osservi che il primo elemento della configurazione può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math>, il terzo in <math>(n-2)</math> e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con <math>P_n</math> il numero delle possibili permutazioni di un insieme di <math>n</math> elementi, si ottiene che esse sono esattamente <math>n!</math> (<math>n</math> [[fattoriale]]):

:<math>P_{n} = n \cdot (n - 1) \cdot (n-2) \cdot \dots \cdot 1 = n!</math>

Da cui si deduce come caso particolare <math>P_1=1! = 1</math>. Per completare la definizione di fattoriale mantenendone le proprietà si pone: <math>P_0=0! = 1 </math><ref name=unibo>{{cita web|lingua=|capitolo=|titolo=Cenni di calcolo combinatorio|autore=|url=http://progettomatematica.dm.unibo.it/Prob2/2calcolocombinatorio.html|sito=Università di Bologna}}</ref>

====Esempi====

Ad esempio le*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>.

*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?

Un altro esempio può essere il seguente:

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

:Le permutazioni possibili sono:

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?

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

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.

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

*<math>1! = 1</math>

*<math>0! = 1</math>.

=== Permutazioni con ripetizioni ===

In alcuni casi un insieme può contenere elementi che si ripetono. In questo caso alcune permutazioni di tali elementi saranno uguali tra loro. Indicando con <math>k_1</math>, <math>k_2</math> fino a <math>k_r</math> il numero di volte che si ripetono rispettivamente gli elementi <math>1,\,2,</math> fino a <math>r</math>, dove <math>r \le n</math>, le permutazioni uniche (non ripetute) divengono:

:<math>P^{k_1,k_2,\dots,k_r}_n=\frac {n!}{k_1!k_2!\cdots k_r!} </math><ref>{{cita web|lingua=|capitolo=|titolo=Permutazioni con ripetizione|autore=|url=https://www.sosmatematica.it/le-permutazioni-con-ripetizione/|sito=SOS matematica}}</ref><ref>{{cita web|lingua=|capitolo=|titolo=Permutazioni con ripetizione|autore=|url=https://www.formuliamo.it/probabilita/permutazioni-con-ripetizione/|sito=Formuliamo}}</ref>

:<math>P^{k_1,k_2,\dots,k_r}_n=\frac {n!}{k_1!k_2!\cdots k_r!} </math>

Si tratta, infatti, di dividere il numero delle distinte permutazioni di <math>n</math> oggetti per il numero delle permutazioni di <math>k_1!</math> presenze di uno stesso elemento, tutte uguali tra loro, poi per il numero delle permutazioni di <math>k_2!</math> presenze di uno stesso elemento, ecc.

Riga 43 ⟶ 31:

:<math>P^{k_1,k_2,\dots,k_r}_n=\frac {n!}{k_1!\cdots k_r!}=\frac {n!}{1!\cdots 1!}=n! </math>

====Esempi====

Ad* esempio: leLe permutazioni di <math>\left\{a,\,a,\,b \right\}</math> sono: <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:

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

*:la lettera F <math>1! (k_1= 12)</math>

*:la lettera A <math>(k_2=3)</math>

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

*:la lettera L <math>(k_3=2)</math>

:Utilizzando la formula, avremo:

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

*la lettera F <math>(k_1=2)</math>

*la lettera A <math>(k_2=3)</math>

*la lettera L <math>(k_3=2)</math>

Utilizzando la formula, avremo:

:<math>P^{k_1,k_2,k_3}_8=\frac {8!}{2! 3! 2!}=\frac {40320}{24}= 1680 </math>

=== Dismutazioni ===

{{vedi anche|Dismutazione (matematica)}}

Sono dette [[dismutazione (matematica)|dismutazioni]] le permutazioni prive di punti fissi, conil cui valore approssimato è dato formulada:

:<math>\sum_{i=0}^n \left (-1 \right)^ i \frac{n!}{i!} \sim \frac{n!}{e}</math>

Riga 73 ⟶ 56:

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

= \frac{n \cdot (n-1) \cdot \dots \cdot 1}{(n-k) \cdot (n-k-1) \cdot \dots \cdot 1}

= \frac{n!}{(n-k)!}</math>

</math>

Ad esempio, le disposizioni semplici di lunghezza 2 degli elementi dell'insieme <math>\left\{1,\,2,\,3,\,4,\,5 \right\}</math> sono <math>\frac{5!}{(5-2)!} = \frac{5!}{3!} = \frac{120}{6} = 20</math>,

ossia sono i numeri: <math>12,\,13,\,14,\,15,\,21,\,23,\,24,\,25,\,31,\,32,\,34,\,35,\,41,\,42,\,43,\,45,\,51,\,52,\,53,\,54</math>.

Si osserva che le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di <math>n</math> oggetti sono le disposizioni semplici di tali oggetti di lunghezza <math>n</math>. In effetti per il loro numero:

:<math>P_{n} = D_{n,n} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!</math><ref name=unibo />

====Esempi====

Ad esempio, le*Le disposizioni semplici di lunghezza 2 degli elementi dell'insieme <math>\left\{1,\,2,\,3,\,4,\,5 \right\}</math> sono <math>\frac{5!}{(5-2)!} = \frac{5!}{3!} = \frac{120}{6} = 20</math>, ossia sono i numeri: <math>12,\,13,\,14,\,15,\,21,\,23,\,24,\,25,\,31,\,32,\,34,\,35,\,41,\,42,\,43,\,45,\,51,\,52,\,53,\,54</math>.

=== Disposizioni con ripetizioni ===

Riga 91 ⟶ 70:

= {\underbrace{n \cdot n \cdot \dots \cdot n} \atop {k\mbox{ volte}}}

= n^k

</math><ref>{{cita web|lingua=|capitolo=|titolo=Disposizione con ripetizione|autore=|url=https://www.formuliamo.it/probabilita/disposizioni-con-ripetizione/|sito=Formuliamo}}</ref>

</math>

Ad esempio, le disposizioni con ripetizione di lunghezza <math>2</math> degli elementi di <math>\left\{1,\,2,\,3,\,4,\,5 \right\}</math> sono:

<math>5^2 = 25</math>,

ossia: <math>11,\,12,\,13,\,14,\,15,\,21,\,22,\,23,\,24,\,25,\,31,\,32,\,33,\,34,\,35,\,41,\,42,\,43,\,44,\,45,\,51,\,52,\,53,\,54,\,55</math>.

Si fa notare che può anche essere <math>k>n</math>.

====Esempi====

Ad* esempio, leLe disposizioni con ripetizione di lunghezza <math>2</math> degli elementi di <math>\left\{1,\,2,\,3,\,4,\,5 \right\}</math> sono: <math>5^2 = 25</math>,

:ossia sono i numeri: <math>11,\,12,\,13,\,14,\,15,\,21,\,22,\,23,\,24,\,25,\,31,\,32,\,33,\,34,\,35,\,41,\,42,\,43,\,44,\,45,\,51,\,52,\,53,\,54,\,55</math>.

Secondo esempio: i [[byte]] usati in informatica sono disposizioni di <math>8</math> oggetti sugli elementi <math>\left\{0,\,1 \right\}</math> che possono quindi assumere <math>2^8 = 256</math> valori distinti: <math>00000000,\,00000001,\,00000010,\,\ldots\,,11111111</math>.

Secondo* esempio: iI [[byte]] usati in informatica sono disposizioni di <math>8</math> oggetti sugli elementi <math>\left\{0,\,1 \right\}</math> che possono quindi assumere <math>2^8 = 256</math> valori distinti: <math>00000000,\,00000001,\,00000010,\,\ldots\,,11111111</math>.

Nella [[teoria dei linguaggi formali]] le disposizioni rappresentano le [[Stringa (linguaggi formali)|stringhe]] su un alfabeto dato.

== Combinazioni (sequenze non ordinate) ==

Riga 109 ⟶ 83:

=== 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>

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

Di solito tra le diverse disposizioni semplici di una classe si sceglie come combinazione rappresentativa la sequenza nella quale i componenti compaiono in ordine crescente (tutti gli insiemi finiti possono avere gli elementi ordinati totalmente, ovvero associati biunivocamente ai primi interi positivi).

====Esempio====

Ad esempio, le*Le combinazioni semplici di lunghezza <math>4</math> degli elementi di <math>\left\{1,\,2,\,3,\,4,\,5,\,6 \right\}</math> sono:

:<math>\frac{6!}{4!(6-4)!}=\frac{6!}{4!\cdot 2!} = 15</math>,

:cioè: <math>1234,\,1235,\,1236,\,1245,\,1246,\,1256,\,1345,\,1346,\,1356,\,1456,\,2345,\,2346,\,2356,\,2456,\,3456.</math>

===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><ref name=unibo />

====Esempio====

Ad* esempio, viVi 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 ==

Riga 131 ⟶ 105:

== Bibliografia ==

* {{cita libro|autore=[[Mauro Cerasoli]]|coautori=[[Franco Eugeni]]; [[Marco Protasi]]|titolo=Elementi di matematica discreta|anno=1988|editore=Zanichelli|città=Bologna|ISBN=978-88-08-03858-6}}

* {{cita libro|autore=Sheldon M. Ross|titolo=Calcolo delle probabilità|anno=2013|editore=Apogeo|città=Milano|ISBN=978-88-38-78860-4}}

Riga 144 ⟶ 118:

==Altri progetti==

{{Interprogetto|commons=Category:Combinatorics|preposizione=sul}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Algebra}}