bjugiubponi

Apunts de Matem`tica Discreta
a
Grau en Matem`tiques
a
Facultat de Matem`tiques i Estad´
a
ıstica. UPC.

Merc` Mora Gin´
e
e
Departament de Matem`tica Aplicada II
a
Universitat Polit`cnica de Catalunya
e
Barcelona, 4 de febrer de 2012

2

´
Index
1 Combinat`ria enumerativa
o
1.1 Principis b`sics d’enumeraci´ . . . . . . . . . . . . . . . . . . . . . . .
a
o
1.1.1Principi de les caselles . . . . . . . . . . . . . . . . . . . . . . .
1.1.2 Principi de doble recompte . . . . . . . . . . . . . . . . . . . .
1.2 Seleccions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Seleccions ordenades amb repetici´ . . . . . . . . . . . . . . . .
o
1.2.2 Seleccions ordenades sense repetici´ . . . . . . . . . . . . . . .
o
1.2.3 Seleccions noordenades sense repetici´ . . . . . . . . . . . . . .
o
1.2.4 Nombres binomials . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5 Seleccions no ordenades amb repetici´ . . . . . . . . . . . . . .
o
1.2.6 Nombres multinomials . . . . . . . . . . . . . . . . . . . . . . .
1.3 Principi d’inclusi´-exclusi´. Aplicacions . . . . . . . . . . . . . . . . .
o
o
1.3.1 Principid’inclusi´-exclusi´ . . . . . . . . . . . . . . . . . . . .
o
o
1.3.2 Desarranjaments . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.3 Nombre d’aplicacions exhaustives . . . . . . . . . . . . . . . . .
1.3.4 Funci´ Φ d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . .
o
1.4 Particions d’un conjunt . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Particions d’un enter . . . . . . . . .. . . . . . . . . . . . . . . . . . .
1.6 Nombres de Catalan . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7 Resum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.7.1 Nombre de k-seleccions d’un n-conjunt . . . . . . . . . . . . . .
1.7.2 Nombre d’aplicacions f : A −→ B, si |A| = k ≥ 1 i |B| = n ≥ 1
1.7.3 Nombre de distribucions de n boles en k capses(Twelve-fold) .
2 Estimaci´ asimpt`tica
o
o
2.1 Nombres harm`nics . . . . . . . . . . . . .
o
2.2 Comparaci´ asimpt`tica de funcions . . .
o
o
2.2.1 Definicions . . . . . . . . . . . . .
2.2.2 Manipulaci´ del s´
o
ımbol O . . . . .
2.2.3 Comparaci´ de funcions elementals
o
2.3 Factorial . . . . . . . . . . . . . . . . . . .
2.4 Nombres binomials . . . . . . . . . . . . .

.
.
.
..
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

7
7
7
8
9
9
9
10
11
14
16
17
17
18
19
20
21
22
24
26
26
26
26

.
.
.
.
.
.
.

27
27
28
28
29
30
30
33

´
INDEX

4
3 Successions recurrents i funcions generadores
3.1 Successions recurrents . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Alguns m`todes de resoluci´ de successions recurrents . . . . . .
e
o
3.3 L’anellde les s`ries formals de pot`ncies C[[x]] . . . . . . . . . .
e
e
3.4 Funcions generadores . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Funci´ generadora ordin`ria d’una successi´ . . . . . . . .
o
a
o
3.4.2 Manipulaci´ de funcions generadores . . . . . . . . . . . .
o
3.4.3 Nombres binomials generalitzats . . . . . . . . . . . . . .
3.5 Successions recurrents lineals ambcoeficients constants . . . . . .
3.5.1 Resoluci´ de successions recurrents lineals homog`nies . .
o
e
3.5.2 Resoluci´ de successions recurrents lineals no homog`nies
o
e
3.6 Funci´ generadora del nombre de particions d’un enter . . . . . .
o

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

37...