Διακριτά Μαθηματικά

1 Εισαγωγικό κεφάλαιο 3
1.1 Φυσικοί αριθμοί 4
1.1.1 Μαθηματική επαγωγή 4
1.1.2 Διαιρετότητα 13
1.2 Σχέσεις και απεικονίσεις 15
1.2.1 Διμελείς σχέσεις 15
1.2.2 Απεικονίσεις 16
1.3 Ασκήσεις 19

2 Στοιχειώδης συνδυαστική απαρίθμησης 37
2.1 Πεπερασμένα σύνολα 37
2.2 Βασικές αρχές απαρίθμησης 38
2.3 Εφαρμογές 45
2.3.1 Απεικονίσεις 45
2.3.2 Αναδιατάξεις 46
2.3.3 Κυκλικές αναδιατάξεις 47
2.3.4 Υποσύνολα, συνδυασμοί, διωνυμικοί συντελεστές 48
2.3.5 Αναδιατάξεις συλλογών, πολυωνυμικοί συντελεστές 54
2.3.6 Συνθέσεις ακεραίων 56
2.3.7 Συνδυασμοί με επανάληψη 57
2.3.8 Μονοπάτια και αριθμοί Catalan 58
2.4 Συνδυαστικές ταυτότητες 61
2.5 Ασκήσεις 65

3 Εγκλεισμός-­αποκλεισμός 89
3.1 Αρχή εγκλεισμού ­ αποκλεισμού 89
3.2 Εφαρμογές 94
3.2.1 Επί απεικονίσεις 94
3.2.2 Συνάρτηση του Euler 94
3.2.3 Αναδιατάξεις χωρίς σταθερά σημεία 96
3.2.4 Πιόνια στη σκακιέρα 97
3.3 Ασκήσεις 100

4 Διαμερίσεις, σχέσεις ισοδυναμίας, μερικές διατάξεις 113
4.1 Αρχή του περιστερώνα 113
4.2 Διαμερίσεις συνόλων 116
4.3 Αριθμοί Stirling και Bell 118
4.4 Μερικές διατάξεις 124
4.4.1 Αλυσίδες και αντιαλυσίδες 126
4.4.2 Το Θεώρημα του Sperner 129
4.5 Ασκήσεις 131

5 Γραφήματα 153
5.1 Η έννοια του γραφήματος 153
5.2 Περίπατοι και συνεκτικότητα 157
5.3 Δένδρα 160
5.3.1 Ορισμοί και ιδιότητες 161
5.3.2 Το Θεώρημα Cayley–Sylvester 164
5.3.3 Βέλτιστα δένδρα και ο αλγόριθμος του Kruskal 168
5.3.4 Δένδρα με ρίζα 170
5.4 Χρωματισμοί και ταιριάσματα 173
5.4.1 Ο χρωματικός αριθμός 173
5.4.2 Διμερή γραφήματα 176
5.4.3 Το Θεώρημα του Γάμου 178
5.5 Το χρωματικό πολυώνυμο 183
5.6 Επίπεδα γραφήματα 192
5.7 Ασκήσεις 195

6 Γεννήτριες συναρτήσεις 223
6.1 Ορισμοί και παραδείγματα 223
6.1.1 Αριθμοί Fibonacci 223
6.1.2 Τυπικές δυναμοσειρές 225
6.1.3 Γραμμικές αναδρομικές σχέσεις 230
6.2 Συνθέσεις ακεραίων 233
6.3 Διαμερίσεις ακεραίων 236
6.4 Διωνυμικές σειρές, αριθμοί Catalan 239
6.5 Εκθετικές γεννήτριες συναρτήσεις 241
6.6 Ασκήσεις 245

7 Διακριτή πιθανότητα 271
7.1 Χώροι πιθανότητας 271
7.1.1 Απαρίθμηση και πιθανότητα 271
7.1.2 Πεπερασμένοι χώροι πιθανότητας 276
7.1.3 Διακριτοί χώροι πιθανότητας 282
7.2 Δεσμευμένη πιθανότητα και ανεξαρτησία 284
7.3 Τυχαίες μεταβλητές 289
7.3.1 Ορισμοί και παραδείγματα 290
7.3.2 Μέση τιμή και διασπορά 293
7.4 Ασκήσεις 306