Algebra e geometria - calcolo combinatorio

Calcolo combinatorio

Prodotto cartesiano

Il prodotto cartesiano di due insiemi A e B è definito come l'insieme di tutte le coppie ordinate (a, b) tali che a ∈ A e b ∈ B. Se gli insiemi A e B sono finiti, allora il numero delle coppie è dato dal prodotto del numero di elementi di A e di B: |A × B| = |A| * |B|.

Esempio:

A = {a, b, c} e B = {1, 2}

Elenchiamo le coppie di A × B: (a,1), (a,2), (b,1), (b,2), (c,1), (c,2). Ci sono 6 coppie = 3 * 2

Estensione ai prodotti cartesiani multipli

Se abbiamo tre insiemi A, B, e C, il prodotto cartesiano A × B × C è l'insieme di tutte le terne ordinate (a, b, c) tali che a ∈ A, b ∈ B, c ∈ C. Il numero totale di terne è dato da |A| * |B| * |C|.

Esempio: Un ristorante offre un menù a prezzo fisso composto da un primo, un secondo e un dolce. Se ci sono tre diversi primi, quattro secondi e tre dolci, quanti menù diversi si possono fare?

• |Primi| = 3
• |Secondi| = 4
• |Dolci| = 3

Ci sono 3 * 4 * 3 = 36 menù diversi.

Esempio di identikit

Supponiamo di avere caratteri distintivi come segue:

• 4 tipi di capelli
• 3 tipi di occhi
• 8 tipi di naso
• 6 tipi di bocca
• 4 tipi di viso

Quanti volti diversi si possono ottenere? 4 * 3 * 8 * 6 * 4 = 2304 volti diversi.

Targhe automobilistiche

Quante targhe si possono avere se una targa è composta da due lettere, tre cifre e altre due lettere?

26 * 26 * 10 * 10 * 10 * 26 * 26 = 456976000 targhe possibili.

Principio moltiplicativo

Il principio moltiplicativo afferma che se si vogliono combinare n insiemi A₁, A₂, ..., A_n, ciascuno con un numero finito di elementi, il numero totale di combinazioni è dato da |A₁| * |A₂| * ... * |A_n|.

Se A = B, allora A × A = A². In generale, Aⁿ rappresenta l'insieme delle n-uple di elementi di A.

Esempio: Se A = {1, 2, 3}, allora A² = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}, quindi ci sono 9 coppie.

Sequenze senza ripetizione

Vogliamo contare le sequenze di elementi di A che si ottengono non ripetendo uno stesso simbolo.

Esempio: Se A = {1, 2, 3}, le sequenze di lunghezza 3 senza ripetizioni sono: 123, 132, 213, 231, 312, 321. Ci sono solo 6 sequenze ottenute non ripetendo un simbolo.

Disposizioni

Le disposizioni semplici di h su A sono le sequenze di lunghezza h formate con gli elementi di A senza ripetizioni.