Try   HackMD

Calcolo combinatorio

tags: md

Cardinalità

Definizione

Un insieme

X è finito di cardinalità
nN{0}
quando esiste una funzione bigettiva
g:XNn
, e si scrive
|X|=n

L'insieme vuoto è un insieme finito la cui cardinalità si pone uguale a 0, e si scrive

||=0

Se un insieme non vuoto Y è tale che per nessun

nN{0} esiste una funzione bigettiva da
Y
a
Nn
allora si dice che
Y
è infinito.

Lemma dei cassetti

Lemma

Supponiamo di avere una funzione

h:NnNm con
n>m
. Allora
h
non è iniettiva.

Enunciato generale
Supponiamo di avere una funzione

f:XY , dove
X
è un insieme di cardinalità
n
e
Y
è un insieme di cardinalità
m
, con
n>m
. Allora f non è iniettiva.

Corollario

Se

N oggetti sono sistemati in K scatole, allora c'è (almeno) una scatola che contiene almeno
NK
oggetti (qui
NK
è la ”parte intera superiore” di
NK
, ossia il più piccolo numero intero
NK
).

Applicazioni

Teorema

Supponiamo che

X e
Y
siano insiemi tali che
XY
e
Y
sia finito. Allora anche
X
è finito e
|X||Y|

Supponiamo che

f:XY sia una funzione fra insiemi finiti e non vuoti tali che
|X|<|Y|
. Allora
f
non è surgettiva.

Supponiamo che

X e
Y
siano insiemi finiti non vuoti della stessa cardinalità. Allora una funzione
f:XY
è iniettiva se e solo se è surgettiva.

Osservazione

Dunque, in questo caso dove

|X|=|Y|, per provare che una certa funzione
g:XY
è bigettiva basta provare una sola fra queste due proprietà:
g
è iniettiva o
g
è surgettiva.

Insiemi di funzioni

Notazione

Siano

X e
Y
due insiemi. Chiamiamo$ F(X \to Y )$ l'insieme di tutte le funzioni che hanno
X
come dominio e
Y
come codominio:
F(XY)={f|f:XY è una funzione}

Teorema

Siano

X e
Y
finiti non vuoti con
|X|=n
e
|Y|=m
. Allora
|F(XY)|=mn

Dimostrazione

Sia

X={x1,x2,,xn} e
Y={y1,y2,,ym}
.
Proviamo a costruire una funzione da
X
a
Y
.
Dove mandiamo
x1
? Abbiamo
m
scelte:
y1,y2,,ym
.
Dove mandiamo
x2
? Abbiamo sempre
m
scelte:
y1,y2,,ym
, perché non abbiamo fatto nessuna richiesta sulla funzione (tipo "che sia iniettiva" o "surgettiva" etc). In generale, dove mandiamo
xi
con
i=1,2,,n
? Abbiamo sempre
m
scelte. Dunque alla fine possiamo costruire la nostra funzione in
mmmmn volte=mn
modi diversi.
Siccome ci capiterà di ripetere spesso ragionamenti simili a questo, vale la pena soffermarsi e riscrivere la dimostrazione da un altro punto di vista.

Dimostrazione

In realtà individuare una funzione

f:XY equivale ad individuare un elemento del prodotto cartesiano
Y×Y××Yn volte=Yn
. Infatti un elemento di
Yn
è una lista
(a1,a2,,an)
di elementi di
Y
e per ogni tale lista noi possiamo porre
f(x1)=a1,f(x2)=a2,,f(xn)=an
. Viceversa, data una funzione
f:XY
possiamo costruire l'elemento
(f(x1),f(x2),,f(xn))Yn
. Dunque vale
|F(XY)|=|Yn|
e noi abbiamo già osservato che
|Yn|=mn
.

Notazione

Chiamiamo

Inj(XY) l'insieme di tutte le funzioni iniettive che hanno
X
come dominio e
Y
come codominio:$ Inj (X \to Y) = {f | f : X \to Y \text{è una funzione iniettiva}}$

Teorema

Siano

X e
Y
finiti non vuoti con
|X|=n
e
|Y|=m
. Allora
|Inj(XY)|=m(m1)(m2)(mn+1)

Dimostrazione

Sia

X={x1,x2,,xn} e
Y={y1,y2,,ym}
. Se
n>m
il lemma dei Cassetti ci dice che
|Inj(XY)|=0
. Supponiamo allora
nm
e proviamo a costruire una funzione iniettiva
g
da
X
a
Y
.
Dove mandiamo
x1
? Abbiamo
m
scelte:
y1,y2,,ym
.
Dove mandiamox2? Abbiamo
m1
scelte, ossia gli elementi di
Y{g(x1)}
, visto chela funzione deve essere iniettiva.
In generale, dove mandiamo
xi
con
i=1,2,,n
? Abbiamo
m(i1)
scelte, cioè gli elementi di
Y{g(x1),g(x2),,g(xi1)}
. In particolare per l'ultimo elemento
xn
avremo
m(n1)
scelte. Dunque alla fine possiamo costruire la nostra funzione in
m(m1)(m2)(mn+1)
modi diversi. Come ultima osservazione notiamo che la formula ottenuta vale per ogni
m
e ogni
n
interi positivi, ossia
|Inj(XY)|=m(m1)(m2)(mn+1)
si adatta bene anche al caso in cui
n>m
: in tal caso infatti la nostra formula è un prodotto di fattori fra i quali è presente anche
mm
e dunque ha come risultato
0
che,come abbiamo osservato all'inizio, è proprio il numero di funzioni iniettive da
X
a
Y
.

Notazione

Se

|X|=|Y| allora l'insieme delle funzioni bigettive che hanno
X
come dominio e
Y
come codominio è non vuoto:
Bij(XY):Bij(XY)={f|f:XY è una funzione bigettiva}

Teorema

Siano

X e
Y
finiti non vuoti con
|X|=|Y|=n
. Allora
|Bij(XY)|=n!

Dimostrazione

Visto che

|X|=|Y| allora
Bij(XY)=Inj(XY)
e dunque si tratta solo di porre
n=m
nell'enunciato del teorema precedente.

Cardinalità insieme delle parti

Definizione

L'insieme

P(A) delle parti di
A
è l'insieme i cui elementi sono tutti i sottoinsiemi di A:
P(A)=B|B\subeA

Osserviamo in particolare che

AP(A) e
P(A)
. In questo paragrafo vogliamo contare quanti elementi ha
P(A)
nel caso in cui
A
sia un insieme finito.

Teorema

Se

|A|=n allora
|P(A)|=2n

Dimostrazione

Se

A= allora ho solo un sottoinsieme, e la formula torna. Se
|A|1
, per contare quanti sono i sottoinsiemi di
A
immaginiamo di doverne costruire uno. Osserviamo che per individuare un sottoinsieme basta sapere, per ognuno degli
n
elementi di
A
, se tale elemento appartiene o no al sottoinsieme. Possiamo dunque passare in rassegna gli elementi di
A
e per ognuno di loro abbiamo due scelte: SI (sta nel sottoinsieme) oppure NO.
Dunque ci sono
2n
distinti sottoinsiemi di
A
. Osserviamo che l'insieme vuoto corrisponde al caso in cui abbiamo ricevuto sempre la risposta NO e l'insieme
A
al caso in cui abbiamo ricevuto sempre la risposta SI.

nelle dispense c'è anche una dimostrazione a pagina 69 molto lunga basata sul'induzione

Coefficiente binomiale

Dato un insieme

X finito o infinito, costruiamo dei particolari sottoinsiemi del suo insieme delle parti
P(X)

Definizione

Dato

rN, chiamiamo
Pr(X)
l’insieme i cui elementi sono tutti i sottoinsiemi di
X
che hanno cardinalità
r
:
Pr(X)={A|A\subeX|A|=r}

Indicheremo
|Pr(X)|
con il simbolo
(nr)
(si legge: "coefficiente binomiale
n
su
r
").

Teorema

Dati

n,rN, con
0rn
, vale che

(nr)=n(n1)(n2)···(nr+1)r!=n!r!(nr)!

Dimostrazione

Come prima, fissato un insieme

X con
n
elementi, cerchiamo di contare la cardinalità di
Pr(X)
.
Consideriamo
Nr={1,2,3,,r}
e una funzione iniettiva
f:NrX

Chi è
Imm(f=)
? È un sottoinsieme di
X
di cardinalità
r
, dunque è un elemento di
Pr(X)
, proprio uno di quelli che dobbiamo "contare". Sarà vero che ogni elemento di
Pr(X)
lo posso esprimere come immagine di una funzione iniettiva da
Nr
a
X
? Sì, preso infatti un elemento di
Pr(X)
, cioè un sottoinsieme
{a1,a2,,ar}X
, posso facilmente indicare una funzione iniettiva da
Nr
a
X
la cui immagine sia proprio
{a1,a2,,ar}
: per esempio posso prendere la
g:NrX
definita da
g(1)=a1,g(2)=a2,,g(r)=ar
. Insomma, con le funzioni iniettive da
Nr
a
X
"raggiungiamo" tutti gli elementi di
Pr(X)
. Per trovare
|Pr(X)|
potremmo allora cominciare a contare
|Inj(NrX)|
, ossia quante sono le funzioni iniettive da
Nr
a
X
. Ma questo numero lo abbiamo già calcolato: è
n(n1)(n2)(nr+1)
. È vero allora che
|Pr(X)|=n(n1)(n2)(nr+1)
? NO, perché se scriviamo così commettiamo l'errore di contare ogni elemento di
Pr(X)
più volte. Precisamente, dato un sottoinsieme
{a1,a2,,ar}X
lo stiamo contando
|Inj(Nr{a1,a2,,ar})|
volte, cioè tante volte quante sono le diverse funzioni iniettive possibili da
Nr
a
{a1,a2,,ar}
. Ma sappiamo quanto vale
|Inj(Nr{a1,a2,,ar})|
: applicando la formula per il conto delle funzioni iniettive a questo caso particolare in cui dominio e codominio hanno la stessa cardinalità
r
(dunque stiamo in realtà considerando le funzioni bigettive), troviamo che
|Inj(Nr{a1,a2,,ar})|=|Bij(Nr{a1,a2,,ar})|=r!

Allora, visto che col numero
n(n1)(n2)(nr+1)
abbiamo contato
r!
volte ogni elemento di
Pr(X)
, per avere
|Pr(X)|
basterà dividerlo per
r!
:
(nr)=|Pr(X)|=n(n1)(n2)(nr+1)r!

Triangolo di Pascal-Tartaglia

Teorema

Dati

r,nN+ con$ 1 ≤ r < n$, vale

(nr)=(n1r1)+(n1r)

Dimostrazione

Sia

X un insieme con
n
elementi. Visto che
n1
, possiamo scegliere un elemento
aX
. Per calcolare
(nr)
dobbiamo calcolare la cardinalità di
Pr(X)
. Possiamo adesso dividere
Pr(X)
in due parti, raggruppando in un sottoinsieme (che chiameremo
L1
) tutti i sottoinsiemi di
X
di cardinalità
r
che contengono
a
, e in un altro (che chiameremo
L2
) tutti i sottoinsiemi di
X
di cardinalità
r
che NON contengono
a
:
Pr(X)=L1L2

Trattandosi di una unione di due insiemi disgiunti, vale che
(nr=|Pr(X)|=|L1|+|L2|)

Ora, un sottoinsieme di cardinalità
r
che contiene
a
è univocamente determinato se si dice quali sono gli altri elementi (quelli diversi da
a
) che contiene; tali elementi costituiscono un sottoinsieme di cardinalità
r1
di
X{a}
. Dunque
|L1|=|Pr1(X{a})|=(n1r1)

Analogamente si osserva che scegliere un sottoinsieme di
X
di cardinalità
r
che non contiene
a
equivale a scegliere un sottoinsieme di
X{a}
di cardinalità
r
, dunque
|L2|=|Pr(X{a})|=(n1r)

Allora possiamo concludere che
(nr)=|Pr(X)|=|L1|+|L2|=(n1r1)+(n1r)

Il teorema che abbiamo appena dimostrato è il motivo per cui possiamo disporre i coefficienti binomiali in modo da formare il cosiddetto "Triangolo di Pascal-Tartaglia"

Teorema del binomio di Newton

Teorema

Date due variabili

a e
b
, per ogni
nN
vale:

(a+b)n=i=0n(ni)anibi

cioè

(a+b)n=(n0)an+(n1)an1b1+(n2)an2b2++(nn1)a1bn1+(nn)bn

Dimostrazione

Cominciamo da un esempio, per avere un'idea di cosa succede. Calcoliamo lo sviluppo di

(a+b)3. Se non raggruppiamo i termini troviamo:
(a+b)3=(a+b)(a+b)(a+b)=a(a+b)(a+b)+b(a+b)(a+b)==aa(a+b)+ab(a+b)+ba(a+b)+bb(a+b)==aaa+aab+aba+abb+baa+bab+bba+bbb

Abbiamo espresso
(a+b)3
come somma di
8
monomi, ognuno dei quali è stato ottenuto, tramite le proprietà distributiva e associativa, scegliendo o
a
o
b
da ogni parentesi che compare in
(a+b)(a+b)(a+b)
. Quindi, raggruppando adesso i termini tramite la proprietà commutativa, quale sarà il coefficiente di
a2b
? Sarà uguale al numero dei monomi in cui troviamo due
a
e una
b
. E questi quanti sono? Sono
3=(32)
, ossia sono tanti quanti sono i modi di scegliere due parentesi fra le tre del prodotto
(a+b)(a+b)(a+b)
(queste saranno le parentesi da cui prendo la
a
): la prima e la seconda, la prima e la terza, la seconda e la terza. Dunque nello sviluppo avremo
3a2b
. Ovviamente, saremmo arrivati allo stesso risultato contando i modi di scegliere una parentesi fra le tre del prodotto
(a+b)(a+b)(a+b)
(quella da cui prendo la
b
), perché
(31)=(32)=3
. Passiamo al caso generale. Nello sviluppo di
(a+b)n
troveremo
2n
monomi, ciascuno ottenuto scegliendo o
a
o
b
da ognuna delle
n
parentesi del prodotto
(a+b)n=(a+b)(a+b)(a+b)(a+b)(a+b)

Raggruppando i termini, preso un indice
i
con
0in
, quale sarà allora il coefficiente di
anibi
? Sarà uguale al numero di modi con cui si possono scegliere
i
parentesi fra le
n
del prodotto
(a+b)(a+b)(a+b)(a+b)(a+b)
(quelle da cui prendiamo la
b
); dunque sarà uguale a
(ni)
. Oppure sarà uguale al numero di modi con cui si possono scegliere
ni
parentesi fra le
n
del prodotto
(a+b)(a+b)(a+b)(a+b)(a+b)
(quelle da cui prendiamo la
a
): infatti come sappiamo
(ni)=(nni)
. In conclusione, nello sviluppo di
(a+b)n
troveremo il termine
(ni)anibi
. Siccome questo è vero per ogni
i
, con
0in
, abbiamo dimostrato il teorema.