Calcolo combinatorio: differenze tra le versioni

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
m Annullate le modifiche di 188.209.81.66 (discussione), riportata alla versione precedente di 87.9.66.98
Etichetta: Rollback
Riga 1: Riga 1:
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 ''S'' di ''n'' oggetti si vogliono contare le configurazioni che possono assumere ''k'' oggetti tratti da questo insieme.
Più formalmente, dato un insieme ''S'' di ''n'' oggetti si vogliono contare le configurazioni che possono assumere ''k'' oggetti tratti da questo insieme.
Prima di affrontare un problema combinatorio bisogna precisare due punti importanti:
Prima di affrontare un problema combinatorio bisogna precisare due punti importanti:
* Se l'''ordinamento'' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento ({''x,y,z''} è uguale a {''z,x,y''}?)
* Se l'''ordinamento'' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento ({''x,y,z''} è uguale a {''z,x,y''}?)

Versione delle 12:47, 1 ott 2019

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 S di n oggetti si vogliono contare le configurazioni che possono assumere k oggetti tratti da questo insieme. Prima di affrontare un problema combinatorio bisogna precisare due punti importanti:

  • Se l'ordinamento è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento ({x,y,z} è uguale a {z,x,y}?)
  • 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

Lo stesso argomento in dettaglio: Permutazione e Fattoriale.

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 n oggetti, si osservi che il primo elemento della configurazione può essere scelto in n modi diversi, il secondo in (n-1), il terzo in (n-2) e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con Pn il numero delle possibili permutazioni di un insieme di n elementi, si ottiene che esse sono esattamente n! (n fattoriale):

Ad esempio le permutazioni degli elementi dell'insieme {a, b, c} sono 3! = 3 × 2 × 1 = 6: abc, bac, bca, cab, cba, acb. Un altro esempio può essere il seguente: In quanti modi possibili possiamo anagrammare la parola "MONTE", contando anche le parole prive di significato: MONTE n=5; P5 = 5! = 5 × 4 × 3 × 2 × 1 = 120 modi di anagrammare la parola MONTE. N.B: nella parola MONTE nessuna lettera si ripete.

Per completare meglio la definizione di fattoriale fissiamo anche i valori seguenti:

1! = 1 e 0! = 1.

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 k1, k2 fino a kr il numero di volte che si ripetono rispettivamente gli elementi 1, 2 fino a r, dove rn, le permutazioni uniche (non ripetute) divengono:

Si tratta, infatti, di dividere il numero delle distinte permutazioni di n oggetti per il numero delle permutazioni di k1! presenze di uno stesso elemento, tutte uguali tra loro, poi per il numero delle permutazioni di k2! presenze di uno stesso elemento, ecc.

La formula vale in realtà per qualsiasi permutazione, anche senza ripetizioni di elementi. Infatti, se assumiamo k1, k2 fino a kr uguali ad 1 (cioè gli elementi si ripetono una sola volta), otteniamo esattamente la formula delle permutazioni semplici, perché si ha:

Ad esempio: le permutazioni di {a, a, b} sono 3!/(2! 1!) = 3 e sono: aab, aba, baa.

Secondo esempio: In quanti modi possiamo anagrammare la parola FARFALLA.

Le lettere contenute nella parola sono n=8; gli elementi che si ripetono sono “F” (k1=2) ; “A” (k2=3); “L” (k3=2)

Utilizzando la formula, avremo:

Dismutazioni

Sono dette dismutazioni le permutazioni prive di punti fissi, con formula:

Disposizioni (sequenze ordinate)

Lo stesso argomento in dettaglio: Disposizione.

Disposizioni semplici (senza ripetizioni)

Una disposizione semplice di lunghezza k di elementi di un insieme S di n oggetti, con kn, è una presentazione ordinata di k elementi di S 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 n modi diversi, il secondo in (n-1) e così via, sino al k-esimo che può essere scelto in (n-k+1) modi diversi. Pertanto il numero Dn,k di disposizioni semplici di k oggetti estratti da un insieme di n oggetti è dato da:

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

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

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. Cerchiamo il numero delle possibili sequenze di k oggetti estratti dagli elementi di un insieme di n oggetti, ognuno dei quali può essere preso più volte. Si hanno n possibilità per scegliere il primo componente, n per il secondo, altrettante per il terzo e così via, sino al k-esimo che completa la configurazione. Il numero cercato è pertanto:

Ad esempio, le disposizioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono 52 = 25 e sono: 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. Si fa notare che può anche essere k > n.

Secondo esempio: i byte usati in informatica sono disposizioni di 8 oggetti sugli elementi {0,1} che possono quindi assumere 28 = 256 valori distinti: 00000000, 00000001, 00000010, ... , 11111111.

Nella teoria dei linguaggi formali le disposizioni rappresentano le stringhe su un alfabeto dato.

Combinazioni (sequenze non ordinate)

Lo stesso argomento in dettaglio: Combinazione.

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 k elementi estratti da un insieme S di n oggetti distinti si può considerare ottenuta dalla collezione delle disposizioni semplici di lunghezza k degli elementi di S ripartendo tali sequenze nelle classi delle sequenze che presentano lo stesso sottoinsieme di S e scegliendo una sola sequenza da ciascuna di queste classi. Ciascuna delle suddette classi di sequenza di lunghezza k contiene k! sequenze, in quanto accanto a una sequenza σ si hanno tutte e sole quelle ottenibili permutando i componenti della σ. Quindi il numero delle combinazioni semplici di n elementi di lunghezza k si ottiene dividendo per k! il numero delle disposizioni semplici di n elementi di lunghezza k:

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

Ad esempio le combinazioni semplici di lunghezza 4 degli elementi di {1,2,3,4,5,6} sono 6!/(4!(6-4)!), cioè 6!/(4!2!) = 15: 1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 2456, 3456.

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 n oggetti di classe k è uguale a quello delle combinazioni senza ripetizione di n+k-1 oggetti di classe k ed è quindi uguale a:

Ad esempio, vi sono modi di distribuire a 2 bambini distinguibili 4 caramelle indistinguibili, contando anche i casi in cui uno dei bambini non riceve nessuna caramella: 0-4, 1-3, 2-2, 3-1, 4-0. Equivalentemente, le combinazioni con ripetizioni informano sul numero di possibili n-ple di addendi non negativi la cui somma sia k (considerando diverse n-ple in cui eguali addendi compaiano in ordine differente); nel suddetto esempio, sono mostrate le cinque diverse coppie di somma 4. Inoltre, le combinazioni con ripetizioni per n oggetti di classe k rappresentano il numero delle derivate parziali di ordine k che al più differiscono fra loro per una funzione a n variabili con derivate continue fino all'ordine k (che rispetta quindi le ipotesi del teorema di Schwarz).

Bibliografia

  • Mauro Cerasoli, Franco Eugeni; Marco Protasi, Elementi di matematica discreta, Bologna, Zanichelli, 1988.
  • Sheldon M. Ross, Calcolo delle probabilità, Milano, Apogeo, 2004.

Voci correlate

Altri progetti

Collegamenti esterni

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica