Calcolo combinatorio: differenze tra le versioni

Versione delle 22:18, 1 nov 2004

Versione attuale delle 21:28, 18 mag 2025

(347 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

Il '''calcolo combinatorio''' è quella branchia della matematica che studia i modi per raggruppare e ordinare gli elementi di un insieme di oggetti. Un problema di tipo combinatorio è legato al concetto di contare tali modi, detti ''configurazioni'' e viene solitamente posto in termini di domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." ecc... .

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.

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

== Definizione ==

Prima di affrontare un problema combinatorio bisogna capire due fatti importanti:

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:

* Se l''''ordinamento''' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento (Es.: <math>(x,y,z)</math> è uguale a <math>(z,x,y)</math> ? )

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

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

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

=== Permutazioni ===

{{vedi anche|Permutazione|Fattoriale}}

Una permutazione è un riodinamento di un insieme di oggetti ed ogni oggetto può essere considerato al più una volta. Per contare quante siano le permutazioni di un insieme con ''n'' 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 si ottiene che esse sono esattamente <math>n!</math> (<math>n</math> fattoriale):

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

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

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

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

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

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

==== Configurazioni ordinate di dimensione k senza ripetizioni ====

Una '''disposizione semplice''' è un ordinamento degli elementi nella quale non si possono avere ripetizioni di uno stesso oggetto.

In questo caso si è interessati al numero di configurazioni che si possono creare prendendo <math>k</math> oggetti distinti da un insieme di <math>n</math> oggetti. Il primo può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math> e così via sino al <math>k-esimo</math> che può essere scelto in <math>(n-k+1)</math> modi diversi. Pertanto il numero di disposizioni semplici <math>D^{k}_{n}</math> di <math>k</math> oggetti su un insieme di <math>n</math> oggetti è dato dal numero di permutazioni totali da cui si devono togliere gli oggetti non presi in considerazione, ovvero:

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

D^{k}_{n} = P^{k}_{n} = n \times (n-1) \times \dots \times (n-k+1)

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

= \frac{n!}{(n-k)!}

</math>

ASi titolotratta, infatti, di ossservazionedividere siil notinumero comedelle distinte permutazioni di <math>n</math> oggetti per il numero didelle permutazioni di un<math>k_1!</math> insiemepresenze di oggettiuno siastesso effettivamenteelemento, iltutte numerouguali ditra disposizioniloro, semplicipoi cheper siil possononumero operaredelle suglipermutazioni stessi prendendolidi <math>nk_2!</math> perpresenze di uno stesso elemento, volta:ecc.

La formula vale in realtà per qualsiasi permutazione, anche senza ripetizioni di elementi. Infatti, se si assume <math>k_1,\,k_2</math> fino a <math>k_r</math> uguali ad <math>1</math> (cioè gli elementi si ripetono una sola volta), si ottiene esattamente la formula delle permutazioni semplici, perché si ha:

<math>P_{n} = D^{n}_{n} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!</math>

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

Esempio:

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

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

==== Configurazioni ordinate di dimensione k con ripetizioni ====

{{vedi anche|Dismutazione (matematica)}}

Se l'ordine è rilevante nella configurazione ed è possibile avere ripetizioni di uno stesso elemento si parla di '''disposizioni con ripetizione'''. Quello che si sta cercando è il numero delle possibili sequenze di <math>k</math> elementi scegliendoli da un insieme di <math>n</math> oggetti e ognuno di essi può essere preso più volte. Si hanno dunque <math>n</math> possibilità per scegliere il primo elemento, <math>n</math> per il secondo ed altrettante per il terzo e così via sino al <math>k-esimo</math> che completa la configurazione. Il numero di disposizioni con ripetizioni è pertanto:

Sono dette 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>

<math>

DR^{k}_{n}

= {\underbrace{n_{1} \times n_{2} \times \dots \times n_{k}} \atop {k-volte}}

= n^{k}

</math>

== Disposizioni (sequenze ordinate) ==

Esempio:

{{vedi anche|Disposizione}}

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

=== Combinazioni ===

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.

==== Configurazioni non ordinate di dimensione k senza ripetizioni ====

Si chiama '''combinazione semplice''' una configurazione in cui non ha importanza l'ordine degli elementi e non si può riperete lo stesso elemento più volte. Potendo scegliere <math>k</math> elementi da <math>n</math> oggetti distintiti si devono calcolare le permutazioni dei <math>k</math> oggetti e togliere tutte le sequenze uguali a meno di un ordinamento. Le prime sono esattamente le disposizioni semplici mentre le ultime sono le permutazioni possibili della sequenza, ovvero <math>k!</math>:

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>C^{k}_{n} = {n \choose k} = \frac{D^{k}_{n}}{k!} = \frac{n!}{k!(n-k)!}</math>

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

Esempio:

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

==== Configurazioni non ordinate di dimensione kDisposizioni 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:

Quando l'ordine non è importante ma è possibile avere ripetizione degli elementi si parla di '''combinazioni con ripetizione'''. In questo caso un elemento <math>n</math> può essere ripetuto fino a <math>k</math> volte ma bisogna sempre eliminare tutte le sequenze simili a meno di un ordinamento:

:<math>

D'_{n,k}

CR^{k}_{n} = \frac{DR^{k}_{n}}{k!}

= \frac{ {\underbrace{n_{1}n \timescdot n \cdot \dots \timescdot n_{k}n} \atop {k-\mbox{ volte}} } {k!}

= n^k

= \frac{ n \times [(n-1)+1] \times [(n-2)+2] \times \dots \times [(n-k)+k]} {k!} =</math>

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

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

====Esempi====

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

<math><math><math><math>

= \frac{(n+k-1)!}{k!(n-1)!} = \frac{(n+k-1)!}{k!(n+k-1-k)!}

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

riscrivibile quindi come

== Combinazioni (sequenze non ordinate) ==

<math>

{{vedi anche|Combinazione}}

CR^{k}_{n} = {n + k -1 \choose k}

</math>

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

Esempio:

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

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

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

== Note ==

<references/>

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

== Voci correlate ==

* [[Combinatoria]]

* [[Permutazione]]

* [[Disposizione]]

* [[Combinazione]]

* [[Dismutazione (matematica)|Dismutazione]]

* [[Teorema binomiale]]

* [[Fattoriale]]

==Altri progetti==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Algebra}}

{{Controllo di autorità}}

{{Portale|matematica}}

[[Categoria:Combinatoria]]