Analisi 1 Teoria "Principio di Induzione e Calcolo Combinatorio" [cap. II]

Capitolo 2

Principio di induzione e calcolo combinatorio

Il principio di induzione serve a dimostrare che una certa formula è valida per un qualsiasi numero naturale "n".

Es: Vogliamo provare che la somma dei primi "n": S_n = 1 + 2 + 3 + ... + n vale ⁿ⁽ⁿ⁺¹⁾/₂ perché:

∀n ∈ Ν P(n) è vera

P(u): S_n

Il principio di induzione afferma che se valgono le seguenti condizioni:

1. P(i) è vera
2. ∀n ∈ N P(n) ⇒ P(n+1)

Allora ∀n ∈ Ν P(n) è vera

Esempio

Nel primo esempio dato:

1. P(i) è vera? n=1 S_n = 1 = (n+1)₂ = 1 VERO 
2. P(n) → P(n+1) ∀n ∈ N S_n = n(n+1)₂. In effetti: S_n = n(n+1)₂ → S_n + (n+1) = (n+2)₂  VERO 

Questa formula vale per ogni n ∈ N

Calcolo della formula in modo diretto

Come arrivare alla formula?

In modo diretto:

S_n = 1 + 2 + 3 + 4 + ... + N

S_n = N + (n-1) + (n-2) + (n-3) + ... + 1

2S_n = (n+1) + (n+1) + (n+1) + ... + (n+1)

S_n = n(n+1)₂

Disequazione di Bernoulli

Es.2 Disequazione di Bernoulli

Sia >1 vogliamo provare:

(1+d)ⁿ ≥ (1+nd) P(n)

1. P(i) vera? (1+d)¹ ≥ 1+d VERO 
2. P(n) → P(n+1) ∀n ∈ N (1+d)ⁿ ≥ 1+nd ⇒ (1+d)ⁿ(1+d) ≥ (1+nd)(1+d)

Calcolo combinatorio

n persone fanno un brindisi, quante note si ottano - brindisi?

Affermo che B_n = ^n(n-1)/₂ P(n)

1. P(1) vero? P₁: = ^1(1-1)/₂ = 0
2. P(n)² ⇒ P(n+1) ∀n ∈ ℕ Se B_n = ^n(n-1)/₂ ⇒ B_n+1 = B_n = ^n(n-1)/₂ + n = ⁽ⁿ⁺¹⁾ⁿ/₂

Equivalenza tra insiemi

Siano dati due insiemi D e A, un'applicazione (o funzione) da D in A è una legge F: D → A ∀x∈D associo un solo elemento y∈A, che, denominiamo F(x), e chiamiamo immagine di x tramite f.

F si dice suriettiva se ∀y∈A ∃x∈D: F(x)=y

F si dice iniettiva se ∀x₁, x₂∈D x₁≠x₂ ⇒ F(x₁)≠F(x₂)

F si dice biettiva o biunivoca se valgono entrambe le proprietà sopra citate

Diciamo che due insiemi D e A sono equipotenti se esiste una corrispondenza biunivoca tra due, scriviamo: D ≈ A

Diciamo che un insieme A è finito se ∃n∈ℕ: A ≈ {1,...,n} il numero n se esiste è necessariamente unico si definisce cardinalità o potenza A

Diciamo che un insieme A è infinito se non è finito A è numerabile se A ≈ ℕ quindi: ∃F: ℕ → A biunivoca

Esempio di insieme numerabile

Esempio A=P {2, 4, 6, 8, 10,...} ≈ {2k | k∈ℕ}

P è numerabile in quanto l’applicazione f: N → P è biunivoca k → f(k) = 2k infatti:

∀ n ∈ P ∃! k ∈ N : f(k) = n 2k = n ↔ k = n/2

Z = {0, 1, -1, -2, 2, ...} 0 1 -1 -2 2 3 -3 1 2 3 4 5 6 7 k → f(k) {k/2 se k è pari k-1/2 se k è dispari Anche Z è numerabile in quanto: (applicazione) f: N → Z

Per quanto visto negli esempi precedenti A è numerabile se riesco a "mettere in fila" i suoi elementi in modo tale da non saltare e non ripetere nessuno di essi

Q ∩ ]0, 1[ 1/2 2/3 X 3/2 3/4 4/3 5/3 5/4... 1 2 3 4 5 6 7 8 9 10 11 In modo analogo si potrebbe provare che tutta Q è numerabile R invece così come un qualunque suo sottoarco non è numerabile in questo caso parleremo di potenza del continuo

Definizione di disposizioni semplici

(Coni di Panetta) (Contraabsorber) Coppie ordinate (Disposizione Senafraiva) Prodotti quoti sono i numeri formati da 3 cifre dispose peraturate tra loro 3 S^f 5 3 S₁ ecc

Def: n E' con k ≤ n il simbolo D⁽ⁿ⁾(k) indicates 's numbers je Ci sono disposti.

Proprietà delle disposizioni semplici

Parliamo di: Disposizioni Semplici n = 5 k = 3 D(5,3) = 60 dati n ∈ N osserviamo che:

• D(n,1) = n banalmente
• D(n,k) = D(n-1,k-1) ⋅ nn - k + 1 oggetti rimasti
• D(n,3) = n (n-1) (n-2)

Proprietà:

• D(n,1) = n
• D(n,2) = n (n-1)
• D(n,k) = n (n-1) ... (n-k+1) = ∏_k=1^k=1 (n-i)

Nel nostro caso D(5,3) = 5 ⋅ 4 ⋅ 3 = 60

Definizione di disposizioni semplici

La disposizione semplice è un'applicazione iniettiva da un insieme di k elementi ad un insieme di n elementi.

Es: 27 persone si devono disporre in una fila da 4 poltrone in quanti modi possono farlo:

D(7,4) = 7 ⋅ 6 ⋅ 5 ⋅ 4 = 840!

Caso particolare: k=n D(n,n) = n (n-1) (n-2) ... 3·2·1 = n! fattoriale di n D(n,n) = P(n) nel caso precedente con 7 persone P(7) = 7! = 1·2·3·4·5·6·7 = 5040

Combinazioni senza ripetizione

Combinazioni Semplici Dati n,k ∈ ℕ con k≤n per formare un’ordinazione semplice di n oggetti di classe k posso pensare il procedimento in due tempi:

1. I scelgo gli oggetti
2. II decido come disporli Una volta effettuata la scelta quanti modi ho di disporre gli oggetti? Tanti quante le permutazioni di classe k e k!

Partendo ognuna delle scelte di k oggetti di cui al punto I ho eseguito k! disposizioni distinte Quindi se denotiamo:

(i (n,k)): il numero delle scelte di cui al punto I che classicamente combiniamo sempre I n oggetti di classe k ordine vale bene uguale D(n,k) = k! · C_n(n,k) (i (n,k)) = D(n,k) / k! (È il numero di tutti i sottoinsiemi di un sistema di n elementi formati da k elementi)

Esempio: Dato un esempio quanti triangoli posso formare con i suoi vertici? La risposta è D(6,3) / 3! = 20

Es. 2: Date 15 persone quante squadre da 11 posso formare con esse? C_{(15, 11)} = D_(15,11) = ^{C_{(15, 4)}}/_11! 15 persone 4 persone che togliamo dalla squadra non conta l'ordine conviene usare C= persone giallatine della squadra C_{(15, 4)} = 15 · 7 · 13 = 1365

Problema dei bimbalzi

Es. 3: Il problema dei Bimbalzi n persone Le coppie non sono ordinate anche se Carlo balla con Maria anche Maria balla con Carlo C_(n,2) = ^D_(n,2)/_2!

Per utilizzare C_(n,k) usiamo  Osserviamo che ⁿ/_ksi può esprimere nella seguente forma: ⁿ/_k = ^n!/_k!(n-k)! molto altro sopra e sotto poi:

ⁿ/_k → Formulazione pratica

Da questo deduco che: ⁿ/_n-k = ⁿ/_k Infatti: ⁿ/_n-k = ^n!/_(n-k)!·k! Convenzione: ⁿ/₀ = 1→ inserto sottosottratto formato da 0 elementi In questo modo dimostro anche che le cose estreme: ⁿ/_n = 1→ è l'inserto sottosottratto formato da ogni elemento con sé stesso

Il binomio di Newton

a,b ∈ R

(a+b)ⁿ = ∑_k=0ⁿ (n k) a^n-k b^k (ab)ⁿ = aⁿ bⁿ (a+b)² = a² + 2ab + b² (a+b)³ = a³ + 3a²b + 3ab² + b³

Qual è il coefficiente del monomio generale a^n-k b^k? per n=5

(a+b)⁵ = a⁵ + 5a⁴b + (10) a³b² + ...anche il 10, Perché 10 è il numero di ogni sequenza di tipo aaabbaaabb aabbb aaaba ecc... Infatti 10 = (5 2)

Scrivete 2 tipi (a b) Più in generale, il coefficiente del monomio a^n-k b^k nello sviluppo di (a+b)ⁿ è dato da (n k) Pertanto:

(a+b)ⁿ = (n 0) aⁿ + (n 1) a^n-1t₁ + (n 2) a^n-2b² + ... + (n n) bⁿ

(a+b)ⁿ = ∑_k=0ⁿ (n k) a^n-k b^k

Triangolo di Tartaglia

(0)(1) (1 1)(2) (2 1) (2 2)(3) (3 1) (3 2) (3 3)...

n=0 n=1 n=2 n=3 quindi

ninit11 11 2 11 3 3 11 4 6 4 11 ... ... n=0 n=1 n=2 n=3 n=4

Ci aspettiamo che valga la regola (n+1 k) = (n k-1) + (n k)

Dimostriamola!

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

Qual è il MCD?