Άσκηση 2η

 

Υπάρχουν περιπτώσεις στις οποίες ένας πληθυσμός από n δυαδικές συμβολοσειρές μήκους λ περιέχει ακριβώς n × 2λ διαφορετικά σχήματα;

 


Λύση:

 

Βασιζόμενοι στην προηγούμενη άσκηση προκύπτει εύκολα ότι το θεωρητικό μέγιστο πλήθος των διαφορετικών σχημάτων είναι n × 2λ, στιγμιότυπα των οποίων είναι οι n δοσμένες συμβολοσειρές. Όμως κάθε μία από αυτές τις n συμβολοσειρές είναι στιγμιότυπο του σχήματος:

 

, όπου ο αριθμός των αδιάφορων συμβόλων είναι ίσο με λ.

 

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

n × 2λ διαφορετικά σχήματα, αλλά το πολύ n × 2λn + 1, αποτέλεσμα που προκύπτει αν λάβουμε μόνο μία φορά το παραπάνω σχήμα υπόψη μας.

 

Φυσικά τα παραπάνω ισχύουν αν . Αν n = 1 τότε μπορούμε να χρησιμοποιήσουμε το αποτέλεσμα της προηγούμενης άσκησης, όπου δείξαμε ότι κάθε συμβολοσειρά είναι στιγμιότυπο ακριβώς 2λ σχημάτων.