Calcolo combinatorio: differenze tra le versioni

Versione delle 13:55, 4 giu 2023

Versione attuale delle 22:28, 18 mag 2025

(11 versioni intermedie di 8 utenti non mostrate)

Riga 1:

[[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.

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

Riga 18 ⟶ 16:

====Esempi====

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

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

:Le permutazioni possibili sono:

Riga 35 ⟶ 33:

====Esempi====

* Le permutazioni di <math>\left\{a,\,a,\,b \right\}</math> sono: <math>\frac{3!}{2! \cdot 1!} = 3</math>, ossia: <math>aab,\,aba,\,baa</math>.

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

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

Riga 45 ⟶ 43:

=== Dismutazioni ===

{{vedi anche|Dismutazione (matematica)}}

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

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

Riga 63 ⟶ 61:

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

====Esempi====

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

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

Riga 83 ⟶ 77:

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

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

== Combinazioni (sequenze non ordinate) ==

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

Riga 111 ⟶ 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 124 ⟶ 118:

==Altri progetti==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Algebra}}