Ilość palindromów.

[dagi]

Ile jest palindromów długości \(\displaystyle{ n}\) ( zakładamy, że alfabet ma \(\displaystyle{ 26}\) liter ) ?

-- 15 kwi 2012, o 11:05 --

Kombinowałam coś takiego, ale nie wiem czy to ma sens, więc będę wdzięczna za pomoc :

Weźmy np. \(\displaystyle{ n=3}\), to mamy pierwsze miejsce i nie ważne co tam będzie, więc \(\displaystyle{ 26 \cdot}\), potem będzie środek, więc też nie istotne \(\displaystyle{ 26 \cdot 26}\) no i na końcu musi być ta co na początku, a więc \(\displaystyle{ 26 \cdot 26 \cdot 1}\)

Weźmy np. \(\displaystyle{ n=4}\), to mamy pierwsze dwa miejsca nieistotne, a więc \(\displaystyle{ 26 \cdot 26}\), a dalsze wymuszone \(\displaystyle{ 26 \cdot 26 \cdot 1 \cdot 1}\)

To tak zrobiłam, żeby sobie jakoś zobrazować, a co do ogólności, to wydaje mi się, że dla \(\displaystyle{ n}\) parzystych będzie to po prostu \(\displaystyle{ 26^{ \frac{n}{2} }}\), no ale przy \(\displaystyle{ n}\) nieparzystych trzeba jeszcze wziąć pod uwagę tą środkową literę, a więc bedzie tu \(\displaystyle{ 26^ \frac{n+1}{2}}\)

A, więc dla ogólności było by to : \(\displaystyle{ 26^{\left\lfloor \frac{n+1}{n} \right\rfloor }}\)

Tylko nie wiem jak to formalnie uzasadnić ?

[octahedron]

To uzasadnienie jest prawidłowe: skoro słowo ma być symetryczne, to dobieramy tylko jego połowę, czyli \(\displaystyle{ \left\lfloor \frac{n+1}{2} \right\rfloor}\) liter