Calcolo combinatorio: mappa del "tesoro"

In questo prospetto sono presenti i quattro tipi di insieme su cui si basa il calcolo combinatorio: ordinato/non ordinato e con/senza ripetizioni.

Prospetto

[su_accordion]
[su_spoiler title="Convenzioni" style="fancy"]
In questa notazione:

• Y è l'insieme da cui ricaviamo gli elementi da combinare
• |Y| è la cardinalità di Y, cioè il numero di elementi in Y
• n è un altro modo di dire |Y|
• k è il numero di elementi dell'insieme di destinazione
• ℕ_m è l'insieme composto dai primi m numeri naturali
• Per non fare confusione, la notazione X è utilizzata solo per rappresentare l'operazione di prodotto cartesiano
• m! si legge "emme fattoriale" ed è il prodotto di tutti i numeri da 1 a m (es 4! = 1x2x3x4 = 24). Inoltre 0! = 1 per definizione.
• {a, b, c} è un insieme (non ordinato), mentre (a, b, c) è una lista (ordinato)

Esempi:

• se Y è l'insieme dei numeri del lotto, |Y| = 90, perché si estrae da un insieme di 90 numeri
• nello stesso esempio, k = 5, perché per ogni estrazione sono estratti cinque numeri
• ℕ₉₀ è l'insieme di numeri naturali che possono essere messi in corrispondenza con i numeri del lotto
• Se A = {1, 2} e B = {3, 4, 5} allora A X B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)}
• 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720... la funzione fattoriale cresce davvero velocemente! 20! = 2.432.902.008.176.640.000

[/su_spoiler]
[/su_accordion]

	Ordinato	Non ordinato
Con ripetizioni	Disposizioni con ripetizione [su_accordion] [su_spoiler title="Dettagli" style="fancy"] Inglese Ordered selections with repetitions Cardinalità (formula) |Y| = nk Cardinalità (spiegazione) Per ogni elemento k possiamo scegliere qualunque elemento y ∈ Y. Esempio Tombola! Il primo fa ambo, il secondo terno... quante disposizioni ci sono se Y è l'insieme di vincite (ambo, terno, quaterna...) e k il numero di giocatori? [/su_spoiler] [/su_accordion]	Combinazioni con ripetizioni [su_accordion] [su_spoiler title="Dettagli" style="fancy"] Inglese Unordered selections with repetitions Cardinalità (formula) $\left|Y\right|=\frac{\left(n+k-1\right)!}{k!·\left(n-k\right)!}$ Cardinalità (spiegazione) Come le combinazioni senza le ripetizioni, ma con in più k-1 altre possibilità (le ripetizioni) Esempio Ho 12 penne e 5 cassetti. In quanti modi posso distribuire le penne nei cassetti? [/su_spoiler] [/su_accordion]
Senza ripetizioni	Disposizioni semplici [su_accordion] [su_spoiler title="Dettagli" style="fancy"] Inglese Ordered selections without repetitions Cardinalità (formula) $\left|Y\right|=\frac{n!}{\left(n-k\right)!}$ Cardinalità (spiegazione) Per ogni elemento k possiamo scegliere qualunque elemento y ∈ Y, tranne quelli già scelti. Abbiamo n possibilità alla prima scelta, n-1 alla seconda, e così via finché non arriviamo a n-k+1 scelte. n-k+1 e non n-k perché non abbiamo ancora scelto l'elemento. Esempio Tris! Bisogna indovinare il piazzamento dei primi tre (k) cavalli di dieci (n) che partecipano. Quante disposizioni ci sono? [/su_spoiler] [/su_accordion] Permutazioni disposizioni semplici dove k=n [su_accordion] [su_spoiler title="Dettagli" style="fancy"] Inglese Permutation Cardinalità (formula) $\left|Y\right|=\frac{n!}{\left(n-k\right)!}$ma siccome k=n $\left|Y\right|=\frac{n!}{0!}=\frac{n!}{1}=n!$ Cardinalità (spiegazione) Il primo elemento può essere uno qualunque (n); il secondo può essere uno qualunque tranne quello già scelto (n-1), il terzo uno tranne quelli già scelti (n-2) finché resta un elemento solo. Esempio Anagrammi! Quante parole diverse (non di senso compiuto) si possono scrivere con le lettere che compongono la parola RUOTA? [/su_spoiler] [/su_accordion]	Combinazioni senza ripetizioni (Insiemi) [su_accordion] [su_spoiler title="Dettagli" style="fancy"] Inglese Unordered selections without repetitions Cardinalità (formula) $\left|Y\right|=\frac{n!}{k!·\left(n-k\right)!}$ Cardinalità (spiegazione) Partendo dalle disposizioni semplici, si tolgono le permutazioni di insiemi uguali ma con ordini diversi. Per esempio, Y = {a, b, c, d}. P3 = (a,b,c), (a,c,b), (a,c,d), (a,d,c), (a,b,d), (a,d,b), (b,a,c), (b,a,d), (b,c,a), (b,d,a), (b,c,d), (b,d,c), (c,a,b), (c,a,d), (c,b,a), (c,d,a), (c,b,d), (c,d,b), (d,a,b), (d,a,c), (d,b,a), (d,c,a), (d,b,c), (d,c,b). Quelle evidenziate in rosso sono le permutazioni di {a,b,c} Esempio [/su_spoiler] [/su_accordion]