Πέμπτη 21 Δεκεμβρίου 2023

Παλίνδρομες ακολουθίες

Βρείτε τον αριθμό των ακολουθιών $11$ γραμμάτων που αποτελούνται από γράμματα που επιλέχθηκαν από τα $A, B$ και $C$ έτσι ώστε να μην είναι ίδια τρία γειτονικά γράμματα και ολόκληρη η ακολουθία να είναι παλίνδρομη. 
(Παλίνδρομη είναι μια ακολουθία που διαβάζει το ίδιο προς τα εμπρός και προς τα πίσω.)
Για παράδειγμα, οι ακολουθίες 
$AABABABABABAA$ και $CBAABCBAABC$ 
αλλά όχι οι ακολουθίες
$CABBBCBBBAC$ ή $CCAABBCCAAB$.
Αναρτήθηκε από στις 21.12.23
Ετικέτες ,

1 σχόλιο:

  1. papadim22 Δεκεμβρίου 2023 στις 3:59 μ.μ.

    Λόγω παλινδρομικότητας, οι χαρακτήρες της 5ης θέσης και της 7ης θέσης αναγκαστικά θα είναι ίδιοι, επομένως ο χαρακτήρας της 6ης θέσης θα πρέπει να είναι διαφορετικός από αυτόν της 5ης. Επίσης, τα ζευγάρια των θέσεων 1ης-11ης, 2ης-10ης, 3ης-9ης, 4ης-8ης θα έχουν τον ίδιο χαρακτήρα.
    Αν f(ν) ο αριθμός ακολουθιών μήκους ν όπου δεν υπάρχουν τρεις ίδιοι διαδοχικοί χαρακτήρες, ισχύει η αναδρομική σχέση:
    f(ν)=2f(ν-1)+2f(ν-2), με f(1)=3, f(2)=9
    Επομένως f(3)=24, f(4)=66, f(5)=180 και οι αποδεκτές ακολουθίες 11 χαρακτήρων, όπως περιγράφονται, είναι 2*180=360.

    ΑπάντησηΔιαγραφή

Εγγραφή σε: Σχόλια ανάρτησης (Atom)