Politecnico di Milano. Scuola di Ingegneria Industriale e dell’Informazione Analisi e Geometria 1
Federico Lastaria
Primi elementi di combinatoria 11 Ottobre 2016
Indice
1 Elementi di combinatoria 2
1.1 Contare tutte le funzioni da un insieme a un altro . . . 2
1.2 Contare le funzioni iniettive . . . 2
1.3 Contare i sottoinsiemi. Il coefficiente binomiale . . . 3
1.4 Il binomio di Newton. . . 4
1
Elementi di combinatoria
1.1 Contare tutte le funzioni da un insieme a un altro
Se A e B sono due insiemi, denoteremo con AB l’insieme costituito da tutte le funzioni da A a B.
Proposizione 1.1. Se M e N sono insiemi finiti con m e n elementi rispettivamente, allora la cardinalit`a dell’insieme MN di tutte le funzioni da N a M `e
|MN| = |M ||N |= mn
Dimostrazione. Supponiamo dapprima che dominio N e codominio M siano entrambi non vuoti. Poniamo: N = {x1, ...., xn}, M = {y1, ...., ym}. Assegnare una funzione f : N −→ M
significa assegnare f (x1), ...., f (xn). Per f (x1) sono possibili m scelte (uno qualunque degli
elementi y1, ...., ym). Ognuna di queste m possibili scelte pu`o essere associata a m possibili
scelte per f (x2), dando cos`ı origine a m2possibilit`a. A sua volta, ciascuna di queste possibilit`a
pu`o essere associata a m possibili scelte per f (x3), e cos`ı via, fino a un totale di mnpossibilit`a.
In definitiva abbiamo provato che se |N | = n e |M | = m (n, m > 0), allora |MN| = mn.
Per completare l’analisi, osserviamo che dall’insieme vuoto a un qualunque altro insieme (vuoto o no) c’`e un’unica funzione e da un insieme non vuoto all’insieme vuoto non esiste alcuna funzione. Quindi l’uguaglianza |MN| = mn vale anche quando N o M `e vuoto, pur
di assumere 00 = 1.
Nella terminologia classica dell’analisi combinatoria, le funzioni arbitrarie da un insieme con n oggetti a un insieme con m oggetti sono chiamate disposizioni con ripetizione di n oggetti, presi m alla volta.
1.2 Contare le funzioni iniettive
Proposizione 1.2. Il numero delle funzioni iniettive da un k-insieme a un n-insieme `e nk= n(n − 1)(n − 2) · · · (n − k + 1).
Il numero
nk = n(n − 1)(n − 2) · · · (n − k + 1)
Dimostrazione. Denotiamo con
[k] = {1, ...., k} [n] = {1, ...., n}
gli insiemi finiti standard con k e n elementi e sia f : [k] −→ [n] una funzione iniettiva. Il valore f (1) pu`o essere uno qualunque degli n elementi di [n]; il valore f (2) pu`o essere uno qualunque degli n−1 elementi di [n] diversi da f (1), perch´e, per l’iniettivit`a di f , il valore f (1) non pu`o essere pi`u assunto. Le possibili scelte per i valori f (1) e f (2) sono dunque n(n − 1). Continuando nello stesso modo, troviamo infine che il numero delle funzioni iniettive da [k] a [n] `e
n(n − 1)(n − 2) · · · (n − k + 1) (k fattori)
Si vede facilmente che se un insieme A `e finito, allora una funzione da A a A `e iniettiva se e solo se `e biunivoca. (Vedere gli esercizi.) Quindi le permutazioni di A, vale a dire le funzioni biunivoche f : A −→ A, sono in numero di
n! = nn= n(n − 1)(n − 2) · · · 2 · 1.
1.3 Contare i sottoinsiemi. Il coefficiente binomiale
Definizione 1.3 (Coefficienti binomiali). Per definizione, se n e k sono interi non negativi, denotiamo con il simbolo
n k
(1.1) il numero dei k-sottoinsiemi di un n-insieme (cio`e, il numero dei sottoinsiemi con k elementi di un insieme con n elementi).
Questi numeri si chiamano coefficienti binomiali (perch´e vedremo che figurano nello sviluppo del binomio (a + b)n)
Cerchiamo ora una formula esplicita per il coefficiente binomiale n k
. Proposizione 1.4. Il numero dei k-sottoinsiemi di un n-insieme `e:
n k = n k k! = n(n − 1) · · · (n − k + 1) k! (1.2)
Moltiplicando numeratore e denominatore per (n−k)! il coefficiente binomiale si pu`o scrivere: n
k
= n!
Dimostrazione. Sia S un insieme con n elementi. Per trovare il numero n k
dei k-sottoinsiemi di S, procediamo nel modo seguente. Consideriamo l’insieme M ono([k], S) di tutte le funzioni iniettive dall’insieme [k] = {1, 2, ..., k} a S. Si osservi che:
a) Poich´e le funzioni in M ono([k], S) sono iniettive, le loro immagini sono k-sottoinsiemi di S;
b) Per ogni k-sottoinsieme Y di S, esistono esattamente k! funzioni iniettive da [k] a S la cui immagine `e Y .
Ripartiamo ora l’insieme M ono([k], S) in classi, mettendo due funzioni iniettive [k] −→ f S e [k] −→ gS nella stessa classe se Im (f ) = Im (g). Il numero di tali classi `e uguale al numero dei k-sottoinsiemi di S, vale a dire, per definizione, `e uguale a n
k
; e in ciascuna di queste classi, ci sono k! funzioni (per l’osservazione b) di sopra). Dunque la cardinalit`a di M ono([k], S) `e: nk = k!n k (1.4) da cui ricaviamo: n k = n k k! = n(n − 1) · · · (n − k + 1) k! 1.4 Il binomio di Newton
Proposizione 1.5 (Binomio di Newton). Se a, b sono numeri e n `e un intero ≥ 0, allora:
(a + b)n= n X k=0 n k an−kbk (1.5)
Dimostrazione. Per sviluppare
(a + b)n= (a + b) · · · (a + b) (n fattori)
si usa la propriet`a distributiva e poi la propriet`a commutativa. Lo sviluppo consister`a alla fine nella somma di termini del tipo an−kbk. Per ogni fissato k = 0, 1, 2, ..., n, i termini an−kbk sono tanti quanti i modi di scegliere k volte il termine b (e quindi n − k volte il termine a) negli n fattori (a + b), cio`e tanti quanti i k-sottoinsiemi di un insieme con n elementi. Il numero di tali sottoinsiemi `e, per definizione, n
k
1.5 Contare tutti i sottoinsiemi di un insieme finito
Proposizione 1.6. Se A `e un insieme finito con n elementi, allora l’insieme P(A) dei sottoinsiemi di A ha 2n elementi.
Di questo teorema, diamo tre dimostrazioni.
Prima dimostrazione.
Denotiamo con Ω = {0, 1} l’ insieme (con due elementi) dei valori di verit`a: 0 `e il Falso e 1 il Vero. Proviamo che
I sottoinsiemi X ⊆ A sono tanti quante le funzioni A−→ Ω.ϕ
Dimostriamo questa affermazione definendo una funzione invertibile dall’insieme P(A) (di tutti i sottoinsiemi di A) all’insieme ΩA(di tutte le funzioni da A all’insieme con due elementi Ω dei valori di verit`a), nel modo seguente.
• Al sottoinsieme X ⊆ A associamo la funzione A ϕX
−→ Ω definita da:
ϕX(x) =
0 se x /∈ X 1 se x ∈ X
Questa funzione ϕX si chiama la funzione caratteristica del sottoinsieme X ⊆ A.
• 2) Viceversa, a una funzione A−→ Ω associamo il sottoinsiemeϕ X = {x ∈ A | ϕ(x) = 1}.
In questo modo si viene a definire una corrispondenza biunivoca tra l’insieme P(A) delle parti di A e l’insieme ΩAdi tutte le funzioni da A a Ω. Dunque, questi due insiemi hanno la stessa cardinalit`a:
|P(A)| = ΩA
Poich´e sappiamo che l’insieme ΩA delle funzioni da A a Ω ha cardinalit`a 2n, dove n = |A| `e il numero di elementi di A, possiamo concludere che
|P(A)| = 2n
Si noti che questa formula vale anche quando n = 0 (cio`e quando A `e l’insieme vuoto). Infatti, l’insieme vuoto ha un unico sottoinsieme (che `e l’insieme vuoto), e 20 vale proprio 1.
Un altro modo di ottenere il numero Fndei sottoinsiemi di un n-insieme si ottiene notando
che possiamo trovare tutti i sottoinsiemi di {1, ...., n + 1} prendendo tutti i sottoinsiemi di {1, ...., n} ed estendendo ciascuno di essi nei due modi possibili: non aggiungere nulla, oppure aggiungere l’elemento n + 1. Cos`ı
Fn+1 = 2Fn (1.6)
Questa `e una relazione ricorsiva che, unita alla condizione iniziale F0 = 1, permette di trovare
Fn per ogni n. Per l’equazione 1.6si trova subito la soluzione in forma chiusa:
Fn= 2nF0 = 2n.
Terza dimostrazione. Ricordiamo che il coefficiente binomiale nk `e il numero dei sottoin-siemi con k elementi di un insieme con n elementi. Dunque il numero complessivo di tutti i sottoinsiemi di un insieme con n elementi `e dato da
n 0 +n 1 +n 2 + · · · + n n − 1 +n n
(perch´e questo `e il numero dei sottoinsiemi con 0 elementi, pi`u il numero dei sottoinsiemi con 1 elemento, pi`u il numero dei sottoinsiemi con 2 elementi, eccetera, fino al numero dei sottoinsiemi con n elementi). Ma, per la formula della potenza del binomio, abbiamo
2n= (1 + 1)n=n 0 +n 1 +n 2 + · · · + n n − 1 +n n
