Άσκηση 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λ σχημάτων.