ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ
- +
Τελική τιμή: 18,00€
Αρχική τιμή: 20,00€ Έκπτωση -10% (2,00€)
Κερδίσατε Δωρεάν μεταφορικά για αγορές 30€ και άνω! Δείτε το καλάθι σας εδώ
Βάρος 0,850 kg
Είδος

Έκδοση

Έτος έκδοσης

ISBN

Μήνας έκδοσης

Σελίδες

Σχήμα

Εκδότης

Το βιβλίο αυτό απευθύνεται κυρίως σε φοιτητές και φοιτήτριες τμημάτων μαθηματικών, πληροφορικής αλλά και άλλων συγγενικών θετικών επιστημών, που δεν έχουν εξειδικευμένες γνώσεις στα διακριτά μαθηματικά. Στόχος του βιβλίου είναι να εξοικειώσει τους αναγνώστες με δομές των διακριτών και συνδυαστικών μαθηματικών που θα φανούν χρήσιμες
στην περαιτέρω μελέτη των μαθηματικών και των εφαρμογών τους, και να τους βοηθήσει τόσο να εκτιμήσουν και να αφομοιώσουν τις ανάλογες μεθόδους και ιδέες όσο και να αναπτύξουν τη συνδυαστική τους σκέψη. Τα προαπαιτούμενα είναι ελάχιστα, γεγονός που καθιστά το βιβλίο κατάλληλο για ένα ευρύτερο φάσμα αναγνωστών (το οποίο περιλαμβάνει και κάποιους μαθητές και μαθήτριες Λυκείου) με ενδιαφέρον στα μαθηματικά

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
viii Διακριτά μαθηματικά
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
Περιεχόμενα ix
7.2 Δεσμευμένη πιθανότητα και ανεξαρτησία . . . . . . . . . . . . . . . 284
7.3 Τυχαίες μεταβλητές . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
7.3.1 Ορισμοί και παραδείγματα . . . . . . . . . . . . . . . . . . . 290
7.3.2 Μέση τιμή και διασπορά . . . . . . . . . . . . . . . . . . . . 293
7.4 Ασκήσεις . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306