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

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών
Πανεπιστήμιο Κρήτης
Λεωφόρος Κνωσού
714 09 Ηράκλειο

E-mail: mk@fourier.math.uoc.gr

Φθινόπωρο 2002-03

Περιεχόμενα

• 1 Ωράριο
• 2 Περιγραφή του μαθήματος
• 3 Βιβλίο
• 4 Βαθμολογικό Σύστημα - Εξετάσεις
• 5 Ημερολόγιο Μαθήματος
  • 5.1 Τρ, 24/9/02: Εισαγωγικά
  • 5.2 Πα, 27/9/02: Επαγωγή
  • 5.3 Τρ, 1/10/02: Συνέχεια παραδειγμάτων για Μέθοδο Επαγωγής
  • 5.4 Πα, 4/10/02: Εφαρμογή επαγωγής: το θεώρημα του Γάμου
  • 5.5 Τρ, 8/10/02: Μεταθέσεις και συνδυασμοί αντικειμένων ανά
  • 5.6 Πα, 11/10/02: Μεταθέσεων, συνδυασμών συνέχεια
  • 5.7 Τρ, 22/10/02: Απόδειξη ταυτοτήτων με συνδυαστικό επιχείρημα
  • 5.8 Πα, 25/10/02: Γεννήτριες συναρτήσεις ακολουθιών
  • 5.9 Ασκήσεις προετοιμασίας για την πρόοδο
  • 5.10 Τρ, 29/10/02: Εφαρμογές των γεννητριών συναρτήσεων
  • 5.11 Πα, 1/11/02: Εφαρμογές των γεννητριών συναρτήσεων σε αναδρομικά ορισμένες ακολουθίες
  • 5.12 Τρ 5/11/02 και Πα 8/11/02: Εισαγωγή στη θεωρία Γραφημάτων. Δέντρα.
  • 5.13 Τα αποτελέσματα της προόδου
  • 5.14 Ανακοίνωση για την εξεταστέα ύλη
  • 5.15 Ασκήσεις θεωρίας γραφημάτων ως προετοιμασία για τον τελικό
  • 5.16 Οι τελικοί βαθμοί και το τελικό διαγώνισμα Ιουνίου.
  • 5.17 Σεπτέμβριος

1 Ωράριο

Αμφιθέατρο ΒΞ, Τρ 1-3 και Πα 10-11.

Ώρες γραφείου: Τρίτη 3-5 (στο γραφείο μου Γ 111)

2 Περιγραφή του μαθήματος

Από τον οδηγό σπουδών του Τμήματος:

Σκοπός του μαθήματος είναι η εισαγωγή στη συνδυαστική, τη θεωρία γραφημάτων, δένδρων και δικτύων.

Περιεχόμενο:

1. Στοιχεία θεωρίας συνόλων, απεικονίσεις, επαγωγή, αλγόριθμοι, αναδρομικές σχέσεις.
2. Bασικές αρχές συνδυαστικής, διατάξεις, συνδυασμοί, συνδυαστικές ταυτότητες, προβλήματα αντιστοίχισης.
3. Γραφήματα, μονοπάτια, κυκλώματα - ιδιότητες και εφαρμογές.
4. Eίδη δένδρου - ιδιότητες και εφαρμογές, μοντέλα δικτύων.
5. ’λγεβρες Boole, προτασιακός λογισμός.

Μπορείτε επίσης εδώ να δείτε τη σελίδα του μαθήματος όπως διδάχτηκε την άνοιξη 1997-98.

3 Βιβλίο

Θα χρησιμοποιηθεί κυρίως το βιβλίο του C.L. Liu, Στοιχεία Διακριτών Μαθηματικών, που κυκλοφορεί στα Ελληνικά από τις Πανεπιστημιακές Εκδόσεις Κρήτης.

4 Βαθμολογικό Σύστημα - Εξετάσεις

Θα ανακοινωθεί.

5 Ημερολόγιο Μαθήματος

5.1 Τρ, 24/9/02: Εισαγωγικά

Είπαμε πότε δύο σύνολα, πεπερασμένα ή άπειρα, ονομάζονται ισοδύναμα ή ισοπληθικά. Αυτό συμβαίνει όταν υπάρχει μια 1-1 και επί συνάρτηση από το ένα στο άλλο.

Είδαμε ότι η ισοπληθικότητα είναι μια σχέση ισοδυναμίας, δηλ. ανακλαστική ($A \sim A$), συμμετρική ( $A\sim B \Rightarrow B \sim A$) και μεταβατική ($A \sim B$ και $B \sim C$ έπεται $A \sim C$).

Τα σύνολα που είναι ισοπληθικά με τους φυσικούς αριθμούς ${\mathbf N}= {\left\{{1,2,\ldots}\right\}}$ ονομάζονται άπειρα αριθμήσιμα και είδαμε ότι το σύνολο ${\mathbf Z}$ των ακεραίων και το σύνολο ${\mathbf Q}$ των ρητών αριθμών είναι και τα δύο αριθμήσιμα.

Αποδείξαμε με το διαγώνιο επιχείρημα του Cantor ότι το σύνολο ${\mathbf R}$ των πραγματικών αριθμών δεν είναι αριθμήσιμο (είναι, όπως λέμε, υπεραριθμήσιμο).

Αρχίσαμε να μιλάμε για τη μέθοδο της επαγωγής και κάναμε το πρώτο παράδειγμα του βιβλίου.

5.2 Πα, 27/9/02: Επαγωγή

Σήμερα συνεχίσαμε τη μελέτη της Μαθηματικής Επαγωγής κάνοντας μερικά από τα παραδείγματα του βιβλίου, τα 1.2 (σελ. 16), 1.3, 1.4 και 1.5. Δώστε μεγάλη προσοχή στην κατανόηση του 1.4.

Σε αυτό το παράδειγμα η παράμετρος $n$ ως προς την οποία κάνουμε την επαγωγή δεν είναι κατ' αρχήν μέρος του προβλήματος και πρέπει εμείς να την επινοήσουμε, με τέτοιο τρόπο φυσικά ώστε να δουλεύει η επαγωγή. Αν για παράδειγμα δοκιμάσουμε να κάνουμε επαγωγή ως πρός το πλήθος των σφαιρών που βρίσκονται αρχικά στο δοχείο, θα αποτύχουμε.

5.3 Τρ, 1/10/02: Συνέχεια παραδειγμάτων για Μέθοδο Επαγωγής

Δείξαμε με τη μέθοδο επαγωγής τα παρακάτω:

1. Δείξαμε (με λίγες ... περιπέτειες) ότι ένας αριθμός ο οποίος στο δεκαδικό σύστημα αρίθμησης γράφεται ακριβώς με $3^n$ ψηφία, όλα ίδια, διαιρείται από το $3^n$.
2. $2^n > n^3$ για $n \ge 10$.
3. Αν $A$ ένα σύνολο με $n$ στοιχεία, τότε αυτό έχει $2^n$ υποσύνολα.
4. Αν $A$ ένα σύνολο με $n$ στοιχεία, τότε αυτό έχει $n! = 1\cdot2\cdots n$ το πλήθος μεταθέσεις (διαφορετικές δηλ. διατάξεις των στοιχείων του).
5. Έχουμε μια ορθογώνια σοκολάτα που αποτελείται από τετραγωνάκια τοποθετημένα σε $m$ γραμμές και $n$ στήλες. Το τετραγωνάκι όμως της πάνω αριστερά γωνίας (και μόνο αυτό) είναι φτιαγμένο από σαπούνι αντί για σοκολάτα. Δύο παίκτες παίζουν το ακόλουθο παιχνίδι. Όταν έρθει η σειρά κάποιου παίκτη αυτός κόβει ένα κομμάτι σοκολάτα και το τρώει. Η $m\times n$ σοκολάτα μπορεί να κοπεί είτε οριζόντια είτε κάθετα αλλά πλήρως, δηλ. αν η σοκολάτα κοπεί οριζόντια τότε αυτή χωρίζεται σε δύο ορθογώνιες σοκολάτες, μια $k\times n$ και μια $(m-k)\times n$, και ο παίκτης διαλέγει και τρώει ένα από τα δύο ορθογώνια κομμάτια. Ομοίως, αν η σοκολάτα κοπεί κάθετα τότε χωρίζεται σε δυο κομμάτια, ένα $m\times k$ και ένα $m\times (n-k)$. Χάνει ο παίκτης που αναγκάζεται να φάει το τετραγωνάκι με το σαπούνι. B Θα θέλατε να παίζατε πρώτος ή δεύτερος; Η απάντηση εξαρτάται από τα $m$ και $n$ και είναι η εξής: αν $m=n$ τότε ο 2ος παίκτης έχει νικητήρια στρατηγική, ενώ αν $m \neq n$ ο 1ος παίκτης μπορεί πάντα να κερδίσει. Το δείξαμε αυτό κάνοντας επαγωγή ως προς την ποσότητα $k = mn$.
6. Ανισότητα αριθμητικού-γεωμετρικού μέσου: Αν $x_1,\ldots,x_n > 0$ τότε
   
   $${x_1+\cdots+x_n \over n} \ge (x_1\cdots x_n)^{1/n}.$$
   
   
   Δείξαμε αυτή την πρόταση κατ' αρχήν για τιμές του $n = 2^k$, και αυτό το κάναμε με επαγωγή ως προς $k$. Τέλος, περάσαμε από την αλήθεια της πρότασης για δυνάμεις του 2 στην αλήθεια της πρότασης γενικά ως εξής: αν $n$ δεν είναι δύναμη του 2 αλλά $2^k < n < 2^{k+1}$ τότε χρησιμοποιούμε την αλήθεια της πρότασης για $2^{k+1}$ συμπληρώνοντας τα νούμερα $x_1,\ldots,x_n$ με $m$ φορές τον αριθμό
   
   $$\alpha = {x_1+\cdots+x_n \over n},$$
   
   
   όπου $m = 2^{k+1}-n$. Από αυτό προκύπτει με πράξεις το ζητούμενο.

5.4 Πα, 4/10/02: Εφαρμογή επαγωγής: το θεώρημα του Γάμου

Αυτά που ακολουθούν σε αυτή την παράγραφο βρίσκονται εδώ σε μορφή Postscript (αυτό το κείμενο είχε γραφεί την άνοιξη του 1998, όταν δίδαξα για τελευταία φορά Διακριτά Μαθηματικά).

Συμβολισμοί: Με $[n]$ συμβολίζουμε το σύνολο ${\left\{{1,\ldots,n}\right\}}$. Με ${\left\vert{K}\right\vert}$ συμβολίζουμε το πλήθος των στοιχείων του συνόλου $K$.

Εστω $X$ ένα πεπερασμένο ή άπειρο σύνολο και $A_1,\ldots,A_n \subseteq X$ ένα σύστημα υποσυνόλων του $X$. Για απλότητα μπορούμε να θεωρήσουμε ότι το σύνολο $X$ είναι πεπερασμένο, αν και όλες οι αποδείξεις ισχύουν και για άπειρο $X$.

Ορισμός: Τα στοιχεία $x_1 \in A_1, \ldots, x_n \in A_n$ ονομάζονται ένα σύστημα ξένων αντιπροσώπων (ΣΞΑ) για το σύστημα συνόλων $A_1,\ldots,A_n$ αν τα $x_1,\ldots,x_n$ είναι όλα διαφορετικά.

Το πρόβλημα που θα μας απασχολήσει είναι να βρούμε συνθήκες για την ύπαρξη ενός ΣΞΑ για ένα σύστημα συνόλων

$${\cal F} = {\left\{{A_1,\ldots,A_n}\right\}}.$$

Ορισμός: Για κάθε $J \subseteq [n]$ ορίζουμε

$$A(J) = A_{\cal F}(J) = \bigcup_{j\in J} A_j.$$

Ο δείκτης ${\cal F}$ θα παραλείπεται όταν δεν υπάρχει πρόβλημα σύγχισης.

Είναι φανερό πως αν το σύστημα ${\cal F}$ έχει ένα ΣΞΑ ${\left\{{x_1,\ldots,x_n}\right\}}$ τότε έχουμε

$$\forall J \subseteq [n]: {\left\vert{A(J)}\right\vert} \ge {\left\vert{J}\right\vert}.$$ (1)

Αυτό γιατί το σύνολο $A(J)$ περιέχει τουλάχιστον τα $x_j, j\in J$, τα οποία εξ ορισμού είναι όλα διαφορετικά.

Η συνθήκη (1) λέγεται συνθήκη του Hall και το επόμενο θεώρημα μας λέει ότι εκτός από αναγκαία είναι και ικανή για την ύπαρξη ενός ΣΞΑ για το σύστημα συνόλων ${\cal F}$.

Το θεώρημα του Γάμου: Το σύστημα συνόλων ${\cal F}$ έχει ΣΞΑ αν και μόνο αν ισχύει η συνθήκη του Hall (1).

Απόδειξη. Επαγωγή ως πρός $n$. Για $n=1$ το θεώρημα είναι προφανές. Υποθέτουμε πως ισχύει μέχρι και $n-1$. Εστω ${\cal F}={\left\{{A_1,\ldots,A_n}\right\}}$ ένα σύστημα υποσυνόλων του $X$ που ικανοποιεί την (1). Ενα σύνολο $J\subset [n]$, $J\neq \emptyset,[n]$, λέγεται κρίσιμο αν ${\left\vert{A(J)}\right\vert} = {\left\vert{J}\right\vert}$.

Περίπτωση 1η: Δεν υπάρχει κρίσιμο σύνολο $J$.
Από την (1) το $A_1$ έχει τουλάχιστον ένα στοιχείο, έστω $x_1$. Θεωρούμε τώρα το σύστημα υποσυνόλων του $X\setminus{\left\{{x_1}\right\}}$

$${\cal F}' = {\left\{{A_2',\ldots,A_n'}\right\}},$$

με $A_j' = A_j \setminus {\left\{{x_1}\right\}}$, $j=2,\ldots,n$. Εστω $J \subseteq {\left\{{2,\ldots,n}\right\}}$. Αφού το $J$ δεν είναι κρίσιμο για το σύστημα ${\cal F}$ έχουμε

$${\left\vert{A_{\cal F'}(J)}\right\vert} \ge {\left\vert{A_{\... ... {\left\vert{J}\right\vert} -1 \ge {\left\vert{J}\right\vert},$$

άρα η συνθήκη του Hall (1) ισχύει για το σύστημα ${\cal F}'$. Από την επαγωγική υπόθεση υπάρχει ένα ΣΞΑ $x_2,\ldots,x_n$ για το ${\cal F}'$. Είναι εύκολο τότε να δεί κανείς πως τα $x_1,x_2,\ldots,x_n$ είναι ένα ΣΞΑ για το ${\cal F}$.

Περίτωση 2η: Υπάρχει κάποιο κρίσιμο σύνολο.
Εστω $J$ ένα κρίσιμο σύνολο με το ελάχιστο δυνατό μέγεθος. Για απλούστευση μπορούμε να θεωρήσουμε ότι $J={\left\{{1,\ldots,k}\right\}}$. Εχουμε τότε ${\left\vert{A(J)}\right\vert} = {\left\vert{J}\right\vert}$. Αφού η συνθήκη του Hall ισχύει για το σύστημα ${\cal F}$ είναι φανερό ότι θα ισχύει και για το σύστημα $A_1,\ldots,A_k$ υποσυνόλων του $A(J)$. Αφού $k<n$ συμπεραίνουμε από την επαγωγική υπόθεση πως υπάρχει ΣΞΑ $x_1,\ldots,x_k \in A(J)$ για τα $A_1,\ldots,A_k$.

Θα δείξουμε ότι υπάρχει και ένα ΣΞΑ για τα σύνολα $A_{k+1},\ldots,A_n$ με όλους τους αντιπροσώπους $\notin A(J)$, και έτσι θα έχει ολοκληρωθεί η απόδειξη. Γι'αυτό θα δείξουμε ότι ισχύει η συνθήκη του Hall για το σύστημα ${\cal F}' = {\left\{{A_{k+1}',\ldots,A_n'}\right\}}$ υποσυνόλων του $X \setminus A(J)$, με

$$A_j' = A_j \setminus A(J), j=k+1,\ldots,n.$$

Εστω λοιπόν $I \subseteq {\left\{{k+1,\ldots,n}\right\}}$. Πρέπει να δείξουμε ${\left\vert{A_{{\cal F}'}(I)}\right\vert} \ge {\left\vert{I}\right\vert}$.

Από τη συνθήκη του Hall για το αρχικό σύστημα ${\cal F}$ έχουμε

$${\left\vert{A_{\cal F}(I \cup J)}\right\vert} \ge {\left\ver... ...rt} = {\left\vert{I}\right\vert} + {\left\vert{J}\right\vert}.$$

Αλλά είναι φανερό ότι επίσης έχουμε

$$A_{\cal F}(I \cup J) = A_{{\cal F}'}(I) \cup A_{\cal F}(J),$$

όπου η ένωση είναι ξένη.

Επεται ότι

$$\begin{eqnarray*} {\left\vert{A_{{\cal F}'}(I)}\right\vert} & = & {\left\vert{A_... ...- {\left\vert{J}\right\vert} \\ &=& {\left\vert{I}\right\vert}, \end{eqnarray*}$$

που είναι αυτό που θέλαμε να δείξουμε. Αρα το σύστημα ${\cal F}'$ έχει ΣΞΑ του οποίου η ένωση με το ΣΞΑ ${\left\{{x_1,\ldots,x_k}\right\}}$ του συστήματος $A_1,\ldots,A_k$, μας δίνει ένα ΣΞΑ για το αρχικό σύστημα ${\cal F}$.
$\Box$

5.5 Τρ, 8/10/02: Μεταθέσεις και συνδυασμοί $n$ αντικειμένων ανά $r$

Ορισμός: Μια διατεταγμένη $r$-άδα από διαφορετικά στοιχεία του συνόλου $[n] = {\left\{{1,\ldots,n}\right\}}$ ονομάζεται μια μετάθεση $n$ στοιχείων ανά $r$.

Ορισμός: Ένα διατεταγμένο υποσύνολο του $[n]$ μεγέθους $r$ ονομάζεται συνδυασμός $n$ στοιχείων ανά $r$.

Δείξαμε σήμερα ότι το πλήθος των διαφορετικών μεταθέσεων $n$ αντικειμένων ανά $r$ είναι

$$P(n, r) := n \cdot (n-1) \cdots (n-k+1) = { n! \over (n-r)! },$$

και ότι το πλήθος των διαφορετικών συνδυασμών $n$ αντικειμένων ανά $r$ είναι

$${n \choose r} := { n \cdot (n-1) \cdots (n-k+1) \over k!} = {n! \over k!(n-k)!}.$$

Στο βιβλίο σας συμβολίζεται το ${n \choose r}$ με $C(n, r)$.

Διαβάστε τις παραγράφους 3.2 έως 3.4 του βιβλίου σας. Δεν έχουμε καλύψει πλήρως όλα τα παραδείγματα όμως αλλά θα καλύψουμε τα υπόλοιπα μέχρι την επόμενη ίσως φορά.

Είδαμε πώς να δείξουμε χωρίς πράξεις (με συνδυαστικό επιχείρημα, όπως θα λέμε από δω και πέρα) ισότητες όπως η

$${n \choose k} = {n \choose n-k}$$ (2)

και

$${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n.$$ (3)

Για να δείξουμε την (2) παρατηρούμε ότι το αριστερό μέλος μετράει τα υποσύνολα του $[n]$ μεγέθους $k$ και το δεξί μέλος τα υποσύνολα του ίδιου συνόλου μεγέθους $n-k$. Επίσης ότι οι δύο κατηγορίες υποσυνόλων μπορούν να έρθουν σε αμφιμονοσήμαντη αντιστοιχία αν σε κάθε υποσύνολο $A$ μεγέθους $k$ αντιστοιχίσουμε το συμπλήρωμά του

$$A \to A^c$$

που θα είναι βεβαίως μεγέθους $n-k$. Αφού οι δύο κατηγορίες συνόλων είναι σε αμφιμονοσήμαντη αντιστοιχία έπεται ότι είναι και ισοπληθείς και αυτό ακριβώς λέει η (2).

Για την (3) παρατηρείστε ότι ο πρώτος όρος αριστερά μετράει όλα τα υποσύνολα μεγέθους 0 (υπάρχει μόνο ένα, το κενό σύνολο $\emptyset$), ο δεύτερος όρος τα υποσύνολα μεγέθους 1, ο τρίτος τα υποσύνολα μεγέθους 2, κ.λ.π, και ο τελευταίος τα υποσύνολα μεγέθους $n$. Στο αριστερό δηλαδή μέλος μετριούνται όλα τα υποσύνολα του $[n]$. Μα το πλήθος αυτών, γνωρίζουμε ήδη, είναι $2^n$, που είναι ακριβώς η (3).

5.6 Πα, 11/10/02: Μεταθέσεων, συνδυασμών συνέχεια

Είδαμε διάφορα προβλήματα σήμερα που αφορούν μέτρημα.

Μια πολύ σημαντική ταυτότητα, το διωνυμικό θεώρημα είναι

$$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k.$$

Αυτή αποδεικνύεται ως εξής: το αριστερό μέλος είναι ένα γινόμενο με $n$ παράγοντες ίσους με $(1+x)$. Το να ``κάνουμε τις πράξεις'' σε αυτό το γινόμενο σημαίνει να επιλέξουμε με όλους τους δυνατούς τρόπους από ένα προσθετέο σε κάθε παρένθεση, να πολλαπλασιάσουμε μεταξύ τους τους επιλεγέντες προσθετέους, και να προσθέσουμε όλα τα γινόμενο που προκύπτουν έτσι. Είναι φανερό τώρα ότι το $x^k$ προκύπτει από αυτή τη διαδικασία αν και μόνο αν επιλέξουμε το $x$ από κάποιους $k$ από τους $n$ παράγοντες, και τη μονάδα από τους υπόλοιπους, και αυτό που προκύπτει με κάθε τέτοια επιλογή είναι το $x^k$ με συντελεστή μονάδα. Υπάρχουν όμως ${n \choose k}$ τρόποι να γίνει αυτή η επιλογή, άρα ο συντελεστής του $x^k$ είναι ${n \choose k}$.

Ομοίως δείξαμε ότι

$$(x+y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}.$$

Επίσης σχοληθήκαμε σήμερα με το εξής πρόβλημα: έχουμε $r$ ίδιες μπάλες και $n$ αριθμημένα (άρα διαφορετικά μεταξύ τους) κουτιά, και ρωτάμε με πόσους τρόπους μπορούμε να βάλουμε αυτές τις $r$ ίδιες μπάλες στα $n$ κουτιά, οσεσδήποτε ανά κουτί. Η απάντηση είναι

$$n+r-1 \choose r$$

και προκύπτει αν σκεφτούμε ως εξής. Βλέπουμε μια τοποθέτηση των $r$ μπαλών στα $n$ κουτιά ως μια τυχούσα λέξη από $n-1$ άσσους και $r$ μηδενικά. Σε κάθε τέτοια λέξη αντιστοιχούμε την εξής κατάσταση στα κουτιά: από την αριστερή άκρη της λέξης μέχρι το πρώτο 1, έχουμε κάποιο πλήθος από μηδενικά (μπορεί και κανένα). Αυτό το πλήθος από μπάλες θεωρούμε ότι έχουμε στο πρώτο κουτί. Από το πρώτο μέχρι το δεύτερο ένα υπάρχει πάλι ένα πλήθος από μηδενικά και τόσες μπάλες θεωρούμε ότι έχουμε στο δεύτερο κουτί, κ.ο.κ. Τέλος στο τελευταίο κουτί θεωρούμε ότι έχουμε τόσες μπάλες όσα μηδενικά είναι στα αριστερά του δεξιότερους άσσου. Με λίγη σκέψη βλέπουμε ότι υπάρχει αμφιμονοσήμαντη αντιστοιχία ανάμεσα στις λέξεις αυτές και στις δυνατές καταστάσεις στα κουτιά, άρα αρκεί να μετρήσει κανείς πόσες τέτοιες λέξεις υπάρχουν. Αυτό είναι απλό. Για να προσδιοριστεί ακριβώς μια τέτοια λέξη αρκεί να πει κανείς σε ποιες $r$ από $n+r-1$ Θέσεις πάνε μηδενικά, και τότε στις υπόλοιπες πάνε αναγκαστικά άσσοι. Αυτό δίνει το αποτέλεσμα.

5.7 Τρ, 22/10/02: Απόδειξη ταυτοτήτων με συνδυαστικό επιχείρημα

Πέρα από μια σύντομη επανάληψη σε συνδυασμούς και μεταθέσεις είδαμε πώς να αποδεικνύουμε μερικές συνδυαστικές ταυτότητες χωρίς πράξεις, αλλά σκεφτόμενοι συνδυαστικά, με ``συνδυαστικό επιχείρημα'' όπως λέμε.

Παραδείγματα.

1. 
   
   $${n \choose k} = {n \choose n-k}, (0\le k \le n).$$
   
   
   Απόδειξη: Το αριστερό μέλος μετράει τα υποσύνολα του $[n]$ μεγέθους $k$ ενώ το δεξί μετράει τα υποσύνολα μεγέθους $[n-k]$. Αυτές οι δύο κλάσεις υποσυνόλων του $[n]$ μπορούν όμως να τεθούν σε αμφιμονοσήμαντη αντιστοιχία μέσω της απεικόνισης $A \to A^c = [n] \setminus A$, άρα τα δύο πλήθη είναι ίσα.
2. 
   
   $$\sum_{k=0}^n {n \choose k} = 2^n.$$
   
   
   Απόδειξη: Ο πρώτος όρος αριστερά, δηλ. ${n \choose 0}$ μετράει τα υποσύνολα του $[n]$ μεγέθους 0, ο δεύτερος ${n \choose 1}$ τα υποσύνολα μεγέθους 1, κλπ, άρα το αριστερό μέλος μετράει όλα τα υποσύνολα του $[n]$. Εχουμε ήδη δει όμως ότι το πλήθος αυτών είναι $2^n$.
3. 
   
   $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}, (1\le k \le n).$$
   
   
   Απόδειξη: Αριστερά μετράμε τα υποσύνολα του $[n]$ μεγέθους $k$. Αυτά χωρίζονται σε δύο κατηγορίες: (Α) αυτά που περιέχουν το $n$, και (Β) αυτά που δεν το περιέχουν. Τα σύνολα της κατηγορίας (Α) είναι ${n-1 \choose k-1}$ το πλήθος, μια και για να προσδιορίσουμε το τυχόν από αυτά πρέπει να προσδιορίσουμε τα $k-1$ στοιχεία του $[n-1] = {\left\{{1,\ldots,n-1}\right\}}$ που περιέχει, ενώ τα σύνολα της κατηγορίας (Β) είναι το πλήθος ${n-1 \choose k}$, αφού για να προσδιορίσουμε ένα από αυτά πρέπει να προσδιορίσουμε τα $k$ στοιχεία του $[n-1]$ που περιέχει.
4. 
   
   $${2n \choose 2} = 2{n \choose 2} + n^2.$$
   
   
   Απόδειξη: Αριστερά μετράμε διμελή υποσύνολα του $[2n]$. Έστω ότι χρωματίζουμε $n$ από τα $2n$ αντικείμενα σε άσπρα και τα άλλα μαύρα. Τα διμελή υποσύνολα του $[2n]$ είναι τριών τύπων: (Α) δύο στοιχεία άσπρα, (Β) δύο στοιχεία μαύρα, (Γ) ένα άσπρο κι ένα μαύρο. Τα υποσύνολα τύπου (Α) είναι ${n \choose 2}$ το πλήθος αφού διαλέγουμε δύο από τα $n$ άσπρα. Τόσα είναι και τα υποσύνολα τύπου (Β). Τα σύνολα τύπου (Γ) είναι το πλήθος $n\cdot n$, μια και πρέπει να διαλέξουμε ένα από $n$ άσπρα και ένα από $n$ μαύρα. Το σύνολο για τις τρεις κατηγορίες συνόλων εμφανίζεται στο δεξί μέλος.
5. 
   
   $${2n+2 \choose n+1} = {2n \choose n+1} + 2{2n \choose n} + {2n \choose n-1}.$$
   
   
   Απόδειξη: Αριστερά μετράμε υποσύνολα του $[2n+2]$ με $n+1$ στοιχεία. Αυτά χωρίζονται σε τρεις κατηγορίες: (Α) Αυτά που δεν περιέχουν κανένα από τα δύο τελευταία στοιχεία $2n+1$ και $2n+2$, (Β) αυτά που περιέχουν ακριβώς ένα από αυτά και (Γ) αυτά που περιέχουν και τα δύο από αυτά. Τα υποσύνολα τύπου (Α) είναι το πλήθος ${2n \choose n+1}$ αφού τα πάντα τα διαλέγουμε από τα πρώτα $2n$, τα υποσύνολα τύπου (Β) είναι το πλήθος $2{2n\choose n}$ αφού για να φτιάξουμε ένα από αυτά επιλέγουμε ένα από τα δύο τελευταία στοιχεία (2 επιλογές και αυτό είναι το νόημα του παράγοντα 2) και τα υπόλοιπα $n$ επιλέγουμε από τα πρώτα $2n$. Τα υποσύνολα τύπου (Γ) είναι το πλήθος ${2n \choose n-1}$ αφού για να προδιορίσουμε ένα από αυτά αρκεί να επιλέξουμε $n-1$ στοιχεία από τα πρώτα $2n$.
6. 
   
   $$\sum_{k=0}^m {n_1 \choose k} {n_2 \choose m-k} = {n_1+n_2 \choose m}, (m \le \min{\left\{{n_1,n_2}\right\}}).$$
   
   
   Απόδειξη: Δεξιά μετράμε τα υποσύνολα μεγέθους $m$ του $[n_1+n_2]$. Βάφουμε τα $n_1$ αντικείμενα άσπρα και τα άλλα μαύρα. Τα υποσύνολα μεγέθους $m$ που μας ενδιαφέρουν χωρίζονται στις $m+1$ το πλήθος κατηγορίες $C_k$, $k=0,\ldots,m$. Η κατηγορία $C_k$ περιλαμβάνει όλα τα $m$-μελή υποσύνολα του $[n_1+n_2]$ που περιέχουν ακριβώς $k$ άσπρα. Προφανώς έχουμε ${\left\vert{C_k}\right\vert} = {n_1 \choose k}{n_2 \choose m-k}$ αφού για να φτιάξουμε ένα υποσύνολα κατηγορίας $C_k$ πρέπει να επιλέξουμε $k$ άσπρα και τα υπόλοιπα $n-k$ μαύρα. Άρα το αριστερό μέλος της ισότητας είναι ίσο με $\sum_{k=0}^m {\left\vert{C_k}\right\vert}$.
7. 
   
   $$\sum_{k=0,\ldots,n, k \pi\epsilon\rho\iota\tau\tau o} {n \... ... \sum_{k=0,\ldots,n, k \alpha\rho\tau\iota o} {n \choose k}.$$
   
   
   Απόδειξη: Χρησιμοποιούμε για την απόδειξη το διωνυμικό θεώρημα:
   

   $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^n.$$ (4)

   
   
   Θέτουμε στην (4) $x=-1$, και παίρνουμε αμέσως το ζητούμενο.
8. 
   
   $$\sum_{k=1}^n k {n \choose k} = n 2^{n-1}.$$
   
   
   Παραγωγίζουμε την (4) και παίρνουμε
   
   $$\sum_{k=1}^n k {n \choose k}x^{k-1} = n (1+x)^{n-1},$$
   
   
   θέτουμε $x=1$ και παίρνουμε το ζητούμενο.

5.8 Πα, 25/10/02: Γεννήτριες συναρτήσεις ακολουθιών

Σήμερα ορίσαμε τη γεννήτρια συνάρτηση της ακολουθίας $a_n$ ως τη συνάρτηση

$$A(z) = \sum_{n\in{\mathbf Z}} a_n z^n.$$

Αν η ακολουθία $a_n$ δεν ορίζεται σε κάποιους ακεραίους τότε τη θεωρούμε 0 σε αυτούς και οι αντίστοιχοι όροι του άνω άπειρου αθροίσματος λείπουν. Για παράδειγμα, αν η $a_n$ ορίζεται μόνο για $n\ge 0$ τότε στο άνω άθροισμα ο δείκτης άθροισης διατρέχει μόνο τους ακεραίους $0,1,2,\ldots$.

Είδαμε μερικά παραδείγματα ζευγών ακολουθιών και των γεννητριών τους συναρτήσεων καθώς και τεχνικές του πώς βρίσκουμε τη γεννήτρια συνάρτηση από την ακολουθίά και το αντίστροφο.

Ορίσαμε τέλος τη συνέλιξη δύο ακολουθιών $a_n$ και $b_n$ ως την ακολουθία

$$c_n = \sum_{k\in{\mathbf Z}} a_k b_{n-k},$$

και δείξαμε ότι $C(z) = A(z)B(z)$.

Διαβάστε τη παράγραφο 9.4 από το βιβλίο σας.

5.9 Ασκήσεις προετοιμασίας για την πρόοδο

ΑΝΑΚΟΙΝΩΣΗ: Θα γίνει πρόοδος την Παρασκευή 15/11/2002, στο Αμφ. ΒΞ, στις 10-11 το πρωί (να είστε στις θέσεις σας στις 10 ακριβώς). Η πρόοδος είναι προαιρετική και μετρά 30% του βαθμού.

Όλες οι σημειώσεις κλειστές!

Για να προετοιμαστείτε για την πρόοδο λύστε τις ασκήσεις του βιβλίου σας:

Κεφ. 1

33, 34, 36, 39, 40, 43

Κεφ. 3

2, 3, 4, 7, 8, 11, 12, 13, 16.α, 18, 20, 22, 23, 26, 27, 31, 33

Κεφ. 9

25, 26, 27, 28, 31, 32, 38, 40

Διαβάστε επίσης προσεκτικά οτιδήποτε υπάρχει σε αυτή την ιστοσελίδα μέχρι εδώ, και με ιδιαίτερη έμφαση στα συνδυαστικά επιχειρήματα της παραγράφου 5.7.

Στη διάθεσή σας για τυχόν απορίες ή βοήθεια στη λύση των ασκήσεων είμαι φυσικά εγώ στις ώρες γραφείου μου (δείτε την αρχή της σελίδας), αλλά και οποτεδήποτε άλλοτε με πετύχετε και έχω χρόνο, αλλά και ο Μανόλης Κονταδάκης kontad@math.uoc.gr που είναι μεταπτυχιακός φοιτητής του Τμήματος Μαθηματικών και έχει οριστεί βοηθός για το μάθημα. Το γραφείο του είναι το Γ 116.

5.10 Τρ, 29/10/02: Εφαρμογές των γεννητριών συναρτήσεων

Υπολογίσαμε σήμερα το άθροισμα $1^2 + 2^2 + 3^2 + \cdots n^2 = {1\over 6}n(n+1)(2n+1)$, χρησιμοποιώντας γεννήτριες συναρτήσεις (Παράδειγμα 9.13 του βιβλίου σας). Ασχοληθήκαμε ακόμη με τα παραδείγματα 9.16, 9.17 και 9.18.

5.11 Πα, 1/11/02: Εφαρμογές των γεννητριών συναρτήσεων σε αναδρομικά ορισμένες ακολουθίες

Είδαμε πώς χρησιμοποιούμε γεννήτριες συναρτήσεις για να υπολογίσουμε κλειστό τύπο για ακολουθίες που ορίζονται με (γραμμικό) αναδρομικό τρόπο. Είδαμε συγκεκριμένα τις δύο περιπτώσεις

$$a_0 = 1,   a_r = 3 a_{r-1}+2    (r \ge 1)$$ (5)

και

$$a_0 = a_1 = 1,   a_r = a_{r-1}+a_{r-2}    (r \ge 2).$$ (6)

Η μέθοδος συνίσταται στο να χρησιμοποιήσουμε τον αναδρομικό τύπο ((5) ή (6)) για να υπολογίσουμε κατ' αρχήν τη γεννήτρια συνάρτηση $A(z)$ της $a_r$, και από αυτήν να βρούμε ένα τύπο για την ακολουθία της $a_r$.

Διαβάστε την παράγραφο 10.7 του βιβλίου σας.

5.12 Τρ 5/11/02 και Πα 8/11/02: Εισαγωγή στη θεωρία Γραφημάτων. Δέντρα.

Δώσαμε πολλούς ορισμούς για διάφορες κατηγορίες γραφημάτων (κατευθυνόμενα ή μη, απλά, με πολλαπλές ακμές κλπ). Οι περισσότεροι από αυτούς τους ορισμούς είναι αρκετά φυσιολογικοί και, λόγω του πλήθους τους, δεν επιμένουμε να τους μάθουμε. Απλά όταν θα μιλάμε για ένα πρόβλημα ή ένα θεώρημα θα φροντίζουμε να κάνουμε ξεκάθαρο για τι πράγμα μιλάμε.

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

Definition 1   Δέντρο ονομάζεται ένα συνεκτικό απλό γράφημα που δεν έχει κύκλους.

Για τον ορισμό αυτό συνεκτικό ονομάζεται ένα γράφημα που κάθε δύο κορυφές του ενώνονται με ένα μονοπάτι (μια ακολουθία δηλ. κορυφών όπου κάθε μια συνδέεται με την επόμενη) ενώ κύκλος είναι ένα μονοπάτι που αρχίζει και τελειώνει στην ίδια κορυφή και που δεν περνάει δύο φορές από την ίδια ακμή.

Δείξαμε τα εξής:

Θεώρημα 1   Ένα συνεκτικό γράφημα με $n$ κορυφές είναι δέντρο αν και μόνο αν έχει ακριβώς $n-1$ ακμές.

Θεώρημα 2   Ένα γράφημα είναι δέντρο αν και μόνο αν για κάθε δύο διαφορετικές κορυφές του υπάρχει ακριβώς ένα μονοπάτι (χωρίς επανάληψη ακμών) που τις ενώνει.

Ένα γράφημα $H$ που το παίρνουμε από ένα γράφημα $G$ κρατώντας κάποιες κορυφές του $G$ και κάποιες ακμές του ονομάζεται υπογράφημα του $G$. Ένα υπογράφημα $T$ του συνεκτικού απλού γραφήματος $G$ λέγεται δέντρο που παράγει (spanning tree) το $G$ αν είναι δέντρο και έχει ως κορυφή κάθε κορυφή του $G$. Είναι εύκολο να δούμε ότι κάθε συνεκτικό γράφημα έχει τουλαχιστον ένα δέντρο που παράγει. Η ιδέα είναι ο εξής αλγόριθμος: αν το $G$ δεν έχει κύκλους τότε είναι το ίδιο ένα δέντρο που παράγει, αλλιώς το $G$ περιέχει ένα κύκλο. Αν διαγράψουμε μια οποιαδήποτε ακμή του κύκλου δεν επηρεάζεται η συνεκτικότητα του $G$, γιατί αν η ακμή αυτή περιεχόταν σε κάποιο μονοπάτι που συνέδεε δύο κορυφές του $G$ τότε το μονοπάτι αυτό μπορεί να αντικατασταθεί από ένα άλλο όπου αντί για την ακμή που σβήσαμε υπάρχει το υπόλοιπο κομμάτι του κύκλου απ' όπου τη σβήσαμε. Ελέγχουμε τώρα αν έχει μείνει δέντρο, αλλιώς συνεχίζουμε να σβήνουμε ακμές από κύκλους μέχρι να μην υπάρχουν πλέον κύκλοι. Τότε έχουμε καταλήξει σε δέντρο που παράγει το $G$.

Τέλος ορίσαμε τον πίνακα τον πίνακα συνδεσμολογίας ενός γραφήματος. Αν $G$ είναι ένα απλό γράφημα με $n$ κορυφές τότε ο $n\times n$ πίνακας $A$, με στοιχεία $A_{ij} = 1$ αν η κορυφή $i$ συνδέεται με την κορυφή $j$ στο $G$ και 0 αλλιώς, ονομάζεται πίνακας συνδεσμολογίας του $G$ και έχει την εξής σημαντική αλγεβρική ιδιότητα την οποία και δείξαμε: αν $k\ge 1$ είναι ένας φυσικός αριθμός τότε αν πάρουμε την $k$ δύναμη του πίνακα $A$ και κοιτάξουμε το $(i,j)$ στοιχείο του αυτό ισούται ακριβώς με το πλήθος των μονοπατιών από την κορυφή $i$ στην κορυφή $j$ στο $G$, που μπορούν να επαναλαμβάνουν ακμές και έχουν μήκος ακριβώς $k$. Αυτό το δείξαμε με μια απλή επαγωγή ως προς $k$.

5.13 Τα αποτελέσματα της προόδου

Το άριστα είναι το 30 και η βάση το 15. Δείτε εδώ.

5.14 Ανακοίνωση για την εξεταστέα ύλη

Για να προετοιμαστείτε για την τελική εξέταση:

1. Διαβάστε από το βιβλίο για τα αντικείμενα τα οποία αναφέρονται στην ιστοσελίδα αυτή (για το τμήμα της ύλης που καλύψαμε μέχρι την πρόοδο).
2. Διαβάστε ολόκληρο το φυλλάδιο ``Μια πολύ σύντομη εισαγωγή στη Θεωρία Γραφημάτων'' που σας έχει διανεμηθεί (κυλικείο).
3. Διαβάστε από τις προσωπικές σας σημειώσεις (ή από όπου αλλού θέλετε) για τα μικρά κομμάτια που δε συμπεριλαμβάνονται στα δύο παραπάνω (π.χ. για το θεώρημα των 5 χρωμάτων για επίπεδα γραφήματα).

5.15 Ασκήσεις θεωρίας γραφημάτων ως προετοιμασία για τον τελικό

Οι παρακάτω ασκήσεις καλύπτουν μέρος αυτών που πρέπει να ξέρετε από τη θεωρία γραφημάτων, και ειδκότερα το μέρος για το οποίο μπορείτε να διαβάσετε από το βιβλίο του Liu.

• Από βιβλίο Liu, Κεφ. 5: 6, 9, 11, 12, 14(α), 16, 27, 28, 36, 45, 46.
• Από βιβλίο Liu, Κεφ. 6: 1, 2, 3, 5, 8.

5.16 Οι τελικοί βαθμοί και το τελικό διαγώνισμα Ιουνίου.

Το τελικό διαγωνισμα Ιουνίου και οι βαθμοί.

5.17 Σεπτέμβριος

Το διαγώνισμα Σεπτεμβρίου είναι εδώ.

Οι βαθμοί Σεπτεμβρίου είναι εδώ.