In questo primo mese di universita’, dopo aver introdotto gli insiemi e le loro principali proprieta’ e operazioni, siamo passati alle applicazioni/funzioni, per poi parlare delle relazioni, delle classi di equivalenza e di combinatoria. Tra meno di un mese avro’ il mio primo esonero di geometria e algebra lineare ed usero’ questo post per riprendere e ripassare i concetti di combinatoria.

La combinatoria cerca di rispondere a domande del tipo: “In quanti modi diversi posso disporre n oggetti?”. Si basa su due regole fondamentali che sono: La regola della somma e del prodotto.

La regola della somma:

Siano A1 e A2 due insiemi disgiunti ( A1 ∩ A2 = Ø, la loro intersenzione e’ uguale ad un insieme vuoto), con |A1|=n1 |A2|=n2 (le loro rispettive cardinalita’ sono n1 e n2) allora | A1 U A2 | (la cardinalita’ dell’unione dei due insiemi) sara’ uguale alla somma delle loro cardinalita’ ossia n1 + n2.

La regola del prodotto:

Siano A1 e A2 due insiemi con la cardinalita’ rispettivamente uguale a n1 e n2 allora la cardinalita’ di A1 x A2 sara’ uguale a n1 x n2.

Fatta questa premessa sulle regole principali della combinatoria passiamo alle “disposizioni” e alle “combinazioni”. La disposizione e’ una scelta di k oggetti da un insieme di n oggetti dove l’ordine e’ importante. La combinazione invece e’ una scelta di k oggetti da un insieme di n oggetti dove l’ordine non e’ importante.

Vediamo le combinazioni e disposizioni semplici (senza ripetizione).

D (n,k) = n! / (n-k)!

C ( n ) = n! / (k! (n-k)! ) —> detto anche coefficiente binomiale

  ( k )

Disposizioni e combinazioni con ripetizione.

D (n,k) = n^k

C ( n + k -1 ) = (k + n - 1)! / ((n - 1)! k!)

  ( n - 1  )

Infine abbiamo il principio di inclusione esclusione.

Dati due insiemi A1 e A2 e la loro intersezione e’ diversa da un insieme vuoto (hanno degli elementi in comune) allora la cardinalita’ degli insiemi sara’ uguale alla somma delle cardinalita’ di A1 e A2 meno la cardinalita’ dell’intersezione tra A1 e A2.

Se A1 ∩ A2 ≠ Ø —> | A1 U A2 | = | A1 | + | A2 | - | A1 ∩ A2 |.

Con tre insiemi la formula si complica.

Se A1 ∩ A2 ∩ A3 ≠ Ø —> | A1 U A2 U A3| = | A1 | + | A2 | + | A3 | - | A1 ∩ A2 | - | A1 ∩ A3 | - | A2 ∩ A3 | + | A1 ∩ A2 ∩ A3 |.

0xandrea, see you in the next post.