Calcolo combinatorio: differenze tra le versioni

Versione delle 19:50, 21 gen 2023

Versione delle 15:24, 20 mag 2023

Riga 1:

{{NN|matematica|febbraio 2022}}

[[File:AnnaCerasoli8SimposioAPAV-MatNat2022.jpg|thumb|upright=2|[[Anna Maria Cerasoli|Anna Cerasoli]] relazione "Calcolo combinatorio, un gioco da ragazzi"<ref>{{cita web|autore=[[Anna Maria Cerasoli|Anna Cerasoli]]|titolo=MadddMaths Matematica Divulgazione Didattica|capitolo=Calcolo combinatorio, un gioco da ragazzi |url=https://maddmaths.simai.eu/calcolo-combinatorio/}}</ref>, presentata all' 8° Simposio APAV Mat^Nat, "Fascino e bellezza della matematica", Roccaraso, 8 aprile 2022]]

Il '''calcolo combinatorio''' è 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.

Riga 13:

=== 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ò [[anagramma|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 ⟶ 33:

:<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 [[anagramma|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 formulacui valore approssimato è dato da:

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

Riga 73 ⟶ 58:

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

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>

Ad:<math>P_{n} esempio= D_{n,n} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!</math><ref name=unibo le/>
====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>.

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

=== Disposizioni con ripetizioni ===

Riga 91 ⟶ 76:

= {\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>.

====Esempio====

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: <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 111 ⟶ 91:

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