Διακριτά Μαθηματικά — Σεπτέμβριος 2013 (επαναληπτική)¶
Μεταγραφή από το αρχείο examsSep13.pdf (κείμενο PDF).
examsSep13.pdf¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ ΠΟΛΥΤΕΧΝΙΚΗ ΣΧΟΛΗ ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ¶
ΤΟΜΕΑΣ ΕΦΑΡΜΟΓΩΝ & ΘΕΜΕΛΙΩΣΕΩΝ ΤΗΣ ΕΠΙΣΤΗΜΗΣ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ
ΕΠΑΝΑΛΗΠΤΙΚΗ ΕΞΕΤΑΣΗ ΣΕΠΤΕΜΒΡΙΟΥ 2013¶
ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ Ι ΚΑΘΗΓΗΤΗΣ Χ. Ι. ΜΠΟΥΡΑΣ ΣΑΒΒΑΤΟ 7 ΣΕΠΤΕΜΒΡΙΟΥ 2013¶
ΘΕΜΑΤΑ
- Να δείξετε πως για κάθε φυσικό αριθμό \(n\) ισχύει: \(\sum_{i=0}^{n} \binom{n}{i}^2 = \binom{2n}{n}\)
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε ΣΥΝΔΥΑΣΤΙΚΑ ΕΠΙΧΕΙΡΗΜΑΤΑ.
(25 μονάδες)
- Να υπολογίσετε την ακολουθία με γεννήτρια συνάρτηση \(\frac{1 + 2x - x^2 - x^3}{1 + x - x^2 - x^3}\)
(25 μονάδες)
- Να βρεθεί με τη βοήθεια των σχέσεων αναδρομής ο αριθμός των δυαδικών ακολουθιών μήκους \(n\), που δεν περιλαμβάνουν διαδοχικά μηδενικά.
(25 μονάδες)
- Να υπολογίσετε με πόσους τρόπους μπορώ να χρωματίσω έναν κύλινδρο που έχει χωριστεί σε 6 τμήματα (ΟΡΙΖΟΝΤΙΑ) με 1 ή περισσότερα χρώματα.
ΥΠΟΔΕΙΞΗ: Για την επίλυση του ερωτήματος να χρησιμοποιήσετε το ΘΕΩΡΗΜΑ P´olya.
(25 μονάδες)
ΚΑΛΗ ΕΠΙΤΥΧΙΑ¶
Οι ενδεικτικές λύσεις και τα θέματα θα αναρτηθούν στο δικτυακό τόπο του μαθήματος, μετά το τέλος της εξέτασης.
Ενημερωθείτε για τα θέματα των Διπλωματικών Εργασιών για το 2013 − 14 στο http://ru6.cti.gr/bouras/diplwmatikes ~~2~~ 013-2014.pdf
Λύσεις (🟢 official)
Κατάσταση: 🟢 official Πηγή: ενδεικτικές λύσεις (αρχείο «solutionsSep13.pdf» της συλλογής)
Λύσεις — Διακριτά Μαθηματικά — Σεπτέμβριος 2013 (επαναληπτική)¶
solutionsSep13.pdf¶
- Επειδή \(\binom{n}{i} = \binom{n}{n-i}\), είναι \(\sum_{i=0}^{n}\binom{n}{i}^2 = \sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}\).
\(\binom{2n}{n}\) σημαίνει να διαλέξουμε \(n\) από \(2n\) αντικείμενα. Αυτό μπορεί να γίνει ως εξής: Χωρίζουμε τα \(2n\) αντικείμενα σε 2 ομάδες ώστε κάθε μία να έχει \(n\) αντικείμενα.
Για \(i = 0, 1, 2, 3, \ldots, n\), διαλέγουμε \(i\) αντικείμενα από την πρώτη ομάδα με \(\binom{n}{i}\) τρόπους και \(n - i\) αντικείμενα από τη δεύτερη ομάδα με \(\binom{n}{n-i}\) τρόπους.
Για \(i = 0, 1, 2, 3, \ldots, n\), υπάρχουν \(\binom{n}{i}\binom{n}{n-i}\) τρόποι επιλογής.
Τα ενδεχόμενα για διαφορετικές τιμές του \(i\) είναι αμοιβαία αποκλειόμενα, οπότε με κανόνα αθροίσματος έχουμε: $\(\binom{2n}{n} = \sum_{i=0}^{n}\binom{n}{i}\binom{n}{n-i}\)$
- \(A(x) = \dfrac{1+2x-x^2-x^3}{1+x-x^2-x^3} = \dfrac{1+x-x^2-x^3}{1+x-x^2-x^3} + \dfrac{x}{1+x-x^2-x^3} = 1 + \dfrac{x}{1+x-x^2(1+x)} = 1 + \dfrac{x}{(1+x)(1-x^2)} = 1 + \dfrac{x}{(1+x)^2(1-x)}\)
Αναλύουμε το κλάσμα \(\dfrac{x}{(1+x)^2(1-x)}\) σε άθροισμα απλών κλασμάτων: $\(\frac{x}{(1+x)^2(1-x)} = \frac{A}{1-x} + \frac{B}{1+x} + \frac{C}{(1+x)^2} \iff x = A(1+x)^2 + B(1-x)(1+x) + C(1-x) \quad (1)\)$
- Για \(x = 1\) στην (1): \(1 = A\cdot 2^2 \Rightarrow A = \frac{1}{4}\). Αντικαθιστούμε στην (1): \(x - \frac{1}{4}(1+x)^2 = B(1-x)(1+x) + C(1-x) \quad (2)\)
- Για \(x = -1\) στην (2): \(-1 = C\cdot 2 \Rightarrow C = -\frac{1}{2}\). Αντικαθιστούμε στην (2): \(x - \frac{1}{4}(1+x)^2 + \frac{1}{2}(1-x) = B(1-x^2)\). Παραγωγίζουμε και τα δύο μέλη \(\Rightarrow\) \(1 - \frac{2}{4}(1+x) - \frac{1}{2} = -2Bx \quad (3)\)
- Για \(x = 1\) στην (3): \(1 - \frac{1}{2}\cdot 2 - \frac{1}{2} = -2B \Rightarrow -\frac{1}{2} = -2B \Rightarrow B = \frac{1}{4}\)
Έχουμε: \(A(x) = 1 + \frac{1}{4}(1-x)^{-1} + \frac{1}{4}(1+x)^{-1} - \frac{1}{2}(1+x)^{-2} =\) $\(1 + \frac{1}{4}\sum_{k=0}^{\infty}\binom{-1}{k}(-1)^k x^k + \frac{1}{4}\sum_{k=0}^{\infty}\binom{-1}{k}x^k - \frac{1}{2}\sum_{k=0}^{\infty}\binom{-2}{k}x^k =\)$ $\(1 + \frac{1}{4}\sum_{k=0}^{\infty}x^k + \frac{1}{4}\sum_{k=0}^{\infty}(-1)^k x^k - \frac{1}{2}\sum_{k=0}^{\infty}(-1)^k(k+1)x^k =\)$ $\(1 + \sum_{k=0}^{\infty}\left[\frac{1}{4} + \frac{1}{4}(-1)^k - \frac{1}{2}(-1)^k(k+1)\right]x^k = 1 + x - x^2 + 2x^3 - 2x^4 + 3x^5 - 3x^6 + \ldots\)$
- Για \(n \ge 0\), έστω \(a_n\) ο αριθμός των δυαδικών ακολουθιών μήκους \(n\), που δεν περιέχουν διαδοχικά μηδενικά. Ας είναι \(a_n^{(0)}\) ο αριθμός αυτών των ακολουθιών που τελειώνουν σε μηδέν και \(a_n^{(1)}\) αυτών που τελειώνουν σε ένα. Προφανώς \(a_n = a_n^{(0)} + a_n^{(1)}\). Επίσης ισχύει η αναδρομική σχέση, $\(a_n = 2a_{n-1}^{(1)} + 1a_{n-1}^{(0)}\)$ αφού από μία δυαδική ακολουθία \(n-1\) ψηφίων που τελειώνει σε ένα, μπορούμε να πάρουμε δύο αποδεκτές ακολουθίες ν ψηφίων προσθέτοντας στο τέλος έναν άσσο ή ένα μηδενικό, ενώ από μία δυαδική ακολουθία \(n-1\) ψηφίων, που τελειώνει σε μηδέν, μπορούμε να πάρουμε μόνο μία αποδεκτή ακολουθία \(n\) ψηφίων προσθέτοντας έναν άσσο στο τέλος της. Συνεπώς θα έχουμε, $\(a_n = a_{n-1}^{(1)} + \left[a_{n-1}^{(1)} + a_{n-1}^{(0)}\right] = a_{n-1}^{(1)} + a_{n-1} = a_{n-1} + a_{n-2}\)$
Άρα η σχέση αναδρομής που επιλύει το πρόβλημα είναι η \(a_n = a_{n-1} + a_{n-2}\), με \(n \ge 2\) και \(a_0 = 1\), \(a_1 = 2\). Η σχέση αυτή είναι ομογενής αναδρομική δευτέρου βαθμού με χαρακτηριστική εξίσωση \(x^2 - x - 1 = 0\).
Έχουμε \(\left(x = \frac{1-\sqrt{5}}{2} \vee x = \frac{1+\sqrt{5}}{2}\right)\). Έτσι η αναδρομική σχέση έχει γενική λύση της μορφής, $\(a_n = A\left(\frac{1-\sqrt{5}}{2}\right)^n + B\left(\frac{1-\sqrt{5}}{2}\right)^n\)$
[sic: στο πρωτότυπο ο δεύτερος όρος γράφεται με τη βάση \(\frac{1-\sqrt{5}}{2}\)· η γενική λύση απαιτεί τη βάση \(\frac{1+\sqrt{5}}{2}\), όπως φαίνεται στον τελικό τύπο.]
Άρα από αρχικές συνθήκες \(a_0 = 1\) και \(a_1 = 2\) έχουμε, $\(\begin{cases} A + B = 1 \ \frac{1-\sqrt{5}}{2}A + \frac{1+\sqrt{5}}{2}B = 2 \end{cases} \Rightarrow \begin{cases} A = \frac{5-3\sqrt{5}}{10} \ B = \frac{5+3\sqrt{5}}{10} \end{cases}\)$
Επομένως ο αριθμός των δυαδικών ακολουθιών μήκους \(n\) που δεν περιέχουν συνεχόμενα μηδενικά είναι, $\(a_n = \frac{5-3\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^n + \frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^n\)$
- Έστω \(G\) το σύνολο μεταθέσεων που αντιστοιχούν σε όλες τις συμμετρίες του κυλίνδρου. Υπάρχουν 2 μεταθέσεις στο \(G\):
- Ταυτοτική μετάθεση. Κυκλική αναπαράσταση: \(x_1^6\)
- Περιστροφή \(180^o\) γύρω από τον οριζόντιο άξονα που χωρίζει το τρίτο από το τέταρτο μέρος. Κυκλική αναπαράσταση: \(x_2^3\)
[Σχήμα: κύλινδρος χωρισμένος σε έξι τμήματα, με οριζόντιο άξονα που χωρίζει το τρίτο από το τέταρτο μέρος]
Επομένως, ο δείκτης κύκλων του συνόλου μεταθέσεων \(G\) είναι: \(P_G = \frac{1}{2}\left(x_1^6 + x_2^3\right)\)
Αφού έχουμε \(n\) χρώματα, ο κατάλογος προτύπων είναι: \(P_G = \frac{1}{2}\left((x_1 + \ldots + x_n)^6 + (x_1^2 + \ldots + x_n^2)^3\right)\)
Θέτοντας \(w(x_1) = \ldots = w(x_n) = 1\) στην παραπάνω παράσταση, το πλήθος των προτύπων, δηλ. το πλήθος των διαφορετικών χρωματισμών, είναι \(\frac{1}{2}\left(n^6 + n^3\right) = \frac{n^3(n^3+1)}{2}\).