Algebra e geometria lineare - disposizioni semplici e ripetute permutazioni

Disposizioni semplici di h oggetti presi da n n!/(n-h)!

Disposizioni con ripetizione n^h

n!

n : = Numero di sottoinsiemi di h elementi presi da

( ) h !∗(n−h)!

h un'insieme di n elementi

Es. A = {a,b,c,d,e} Quanti sottoinsiemi da 3 elementi ha?

5! 5∗4

5 = = =10

( ) 3!∗2 ! 2

3

Es. una gelateria ha 12 gusti di gelato, quanti coni gelato con 3 gusti diversi posso fare?

12 !

12 = = 12 * 11 * 10 / 3 * 2 = 2 * 11 * 10 = 220

( ) 3!∗9!

3

Numero di Combinazioni di h oggetti presi da un insieme di n semplici

Combinazioni con RIPETIZIONI

Es. ci sono 10 tipi di frutta e ne voglio scegliere 4 anche uguali tra loro

13! 13∗12∗11∗10

10+ 4−1 13

= = =

( ) ( ) 4 !∗9 ! 4∗3∗2

4 4

Una permutazione di n oggetti è una disposizione semplici di n su n

Es. A = {a,b,c,d}

abcd è una permutazione degli elementi di A

bacd

cbda n! !

ci sono possibili permutazioni di n elementi

=n

!

(n−n)

→ ci sono 4! permutazioni di a b c d

A e B insiemi finiti

voglio contare le funzioni tra A e B

funz. Iniettive

Biettive

Es. A = {1,2,3,4} B = {a,b,c} a 3 * 3 * 3 * 3 = 3^4 funzioni tra A e B

f f(1) b

1 a c

2 b In genere ci sono |B|^|A| funzioni tra A

3 c a e B

4 f(2) b

c

Le funzioni iniettive

Es. A {1,2,3,4} B= {a,b,c,d,e}

a f(2) a 5 * 4 * 3 * 2 = 5! / (5-4)!

f (1) b b

c c

d d

|B|! Cioè il numero di disposizioni semplici di |A| oggetti presi da |B|

(|B| - |A|)!

Es.

A = {1,2,3,4} B = {a,b,c,d}

f(1) ci sono 4 possibilità

f(2) ci sono 3 possibilità ( diverso da f(1)) Ci sono 4! possibili funzioni biettive

f(3) ci sono 2 possibilità Permutazioni di n elementi

f(4) c'è 1 possibilità

funzioni biettive ( deve essere |A| = |B|) ci sono |A|! f.biettive

Problema

Un quiz ha 10 domande con 4 possibili risposte

la probabilità è data da casi favorevoli / casi possibilità

ho ¼ di probabilità di indovinare una risposta

ho ¼ * ¼ di probabilità di indovinare sia la prima per la seconda

per trovare la probabilità di indovinare le 10 risposte è di 1/4^10 = 9 * 10^-7

Quali sono le possibilità di indovinare 7 risposte su 10

10 * 1/4^7 = 7/1000 = 7 * 10^-3

( )

7

Principio di induzione

voglio sommare i numeri da 1 a 100

1 + 2 = 3

1 + 2 + 3 = 6

1 + 2 + 3 + 4 = 10

1 + 2 + 3 + 4 + 5 = 10 + 5 = 15

.[][][][][]

. .[][][][]

5 . . .[][][] 5 * 6 / 2

. . . . [][]

. . . . . []

6

.[][][][][][]

. .[][][][][]

6 . . .[][][][] 6 * 7 / 2 = 21

. . . . [][][]

. . . . . [][]

. . . . . . []

7

1 + …... + n = n (n+1) / 2

Principio di induzine

Se P è una proprietà definita sui numeri naturali

se valgono le seguenti cose:

P(0) cioè la proprietà P vale per 0

– P(m) → p (m+1)

– allora P vale per ogni n ∈ℕ

Sia P (n) la proprietà 1 + ….. + n = n (n + 1) / 2

Mi chiedo : è vero che vale P(n) per ogni n?

P(1) = ? 1 = 1 * 2 / 2 la proprietà è vera per 1

P(2) = ? 1+2 = 2 * 3 / 2 è vera per 2

Supponiamo che valga P(m)

1 + ….. + m = m * (m+1) / 2

Dimostriamo che vale P(m+1) 1 + ….. + m + (m+1) = m * (m+1) / 2 + (m+1) = (m (m+1) + 2

(m+1))/2 = (m+1)(m+2)/2

P(m+1) è la proprietà

1 + …... + m + (m+1) = (m+1) (m+2) / 2

Quindi vale P(1)

Se vale P (m) allora vale P(m+1)

per il principio di induz. Allora P vale per ogni n

n∈ℕ

Princip. Di induz. Se

Se

P (n0)

P (m ) → P (m+1)

allora P (n) vale per ogni n >= n0

NOTAZIONE

n

∑ K 2+...+n

=1+

k = 1