Άσκηση 2η
Υπάρχουν περιπτώσεις στις οποίες ένας πληθυσμός από n δυαδικές συμβολοσειρές μήκους λ περιέχει ακριβώς n × 2λ διαφορετικά σχήματα;
Λύση:
Βασιζόμενοι στην προηγούμενη άσκηση προκύπτει εύκολα ότι το θεωρητικό μέγιστο πλήθος των διαφορετικών σχημάτων είναι n × 2λ, στιγμιότυπα των οποίων είναι οι n δοσμένες συμβολοσειρές. Όμως κάθε μία από αυτές τις n συμβολοσειρές είναι στιγμιότυπο του σχήματος:
, όπου ο αριθμός των αδιάφορων συμβόλων είναι ίσο με λ.
Αφού το παραπάνω σχήμα λαμβάνεται υπόψη για κάθε μία από τις n συμβολοσειρές δεν είναι δυνατόν να υπάρχουν
n × 2λ διαφορετικά σχήματα, αλλά το πολύ n × 2λ – n + 1, αποτέλεσμα που προκύπτει αν λάβουμε μόνο μία φορά το παραπάνω σχήμα υπόψη μας.
Φυσικά τα παραπάνω
ισχύουν αν . Αν n = 1 τότε μπορούμε να
χρησιμοποιήσουμε το αποτέλεσμα της προηγούμενης άσκησης, όπου δείξαμε ότι κάθε
συμβολοσειρά είναι στιγμιότυπο ακριβώς 2λ σχημάτων.