Άσκηση 1η
Να αποδειχτεί ότι οποιαδήποτε δυαδική συμβολοσειρά μήκους λ αποτελεί στιγμιότυπο από 2λ διαφορετικά σχήματα.
Λύση:
Ας θεωρήσουμε ότι η
δυαδική συμβολοσειρά είναι η (αλαλ-1αλ-2...α2α1).
Αυτή η συμβολοσειρά είναι στιγμιότυπο κάθε σχήματος που προκύπτει από την
αντικατάσταση r γονιδίων της συμβολοσειράς με το
αδιάφορο σύμβολο, όπου
0 ≤ r ≤ λ. Προφανώς υπάρχουν
διαφορετικοί τρόποι να αντικαταστήσουμε r
γονίδια της
συμβολοσειράς με αδιάφορα
σύμβολα, χωρίς να λαμβάνουμε υπόψη μας τη σειρά με την οποία γίνεται η αντικατάσταση των γονιδίων με αδιάφορα σύμβολα. Από την τελευταία αυτή παρατήρηση προκύπτει ότι όλα τα σχήματα που περιέχουν r αδιάφορα σύμβολα θα είναι διαφορετικά μεταξύ τους. Προφανώς σχήματα που περιέχουν διαφορετικό αριθμό αδιάφορων συμβόλων είναι διαφορετικά μεταξύ τους.
Αν π.χ. είναι λ=5 και r=2 τότε η συμβολοσειρά (10110) είναι στιγμιότυπο των παρακάτω σχημάτων:
(**110), (*0*10), (*01*0), (*011*), (1**10),
(1*1*0), (1*11*), (10**0), (10*1*), (101**).
Το πλήθος των
παρακάτω σχημάτων είναι πράγματι και όλα τα σχήματα είναι διαφορετικά μεταξύ τους.
Όμως για κάθε
r = 0,1,2,3,...,λ υπάρχουν
διαφορετικά σχήματα. Επομένως το συνολικό πλήθος των
διαφορετικών σχημάτων των οποίων στιγμιότυπο
αποτελεί η παραπάνω
συμβολοσειρά μήκους λ είναι ίσο με .
Γνωρίζουμε ότι το ανάπτυγμα διωνύμου του Newton είναι:
Θέτοντας n=λ και x=1 προκύπτει ότι:
που δίνει το ζητούμενο πλήθος των διαφορετικών σχημάτων των οποίων στιγμιότυπο αποτελεί η συμβολοσειρά μήκους λ.
Το παραπάνω αποτέλεσμα μπορεί να προκύψει και πιο απλά με τον εξής συλλογισμό:
Κάθε θέση της συμβολοσειράς μπορεί να πάρει δύο τιμές, είτε την πραγματική της τιμή είτα το αδιάφορο σύμβολο. Επειδή η συμβολοσειρά έχει μήκος λ προκύπτει ότι είναι στιγμιότυπο 2λ σχημάτων.