Alfabet - słowa

[mol_ksiazkowy]

Ile jest słów \(\displaystyle{ m}\) literowych nad alfabetem mającym \(\displaystyle{ n}\) liter, w których pierwsza i ostatnia litera nie są obok siebie ?

[arek1357]

Trzeba będzie skorzystać z zasady włączania i wyłączania.

Pokażę idee na przykładzie alfabetu trzycyfrowego :\(\displaystyle{ 1,2,3}\)

i wiadomo, że jedynka i trójka nie może stać koło siebie, niech możliwość słów dozwolonych będzie \(\displaystyle{ a(n)}\) - to słowa o długości \(\displaystyle{ n}\)

niech teraz\(\displaystyle{ b(n)}\) ilość słów w których końcowe przynajmniej raz stoją koło siebie

z obserwacji:

\(\displaystyle{ a(1)=3, b(1)=0}\)

\(\displaystyle{ a(2)=7, b(2)=2: (1,3)(3,1)}\)

Wszystkich możliwości jest \(\displaystyle{ 3^2}\)

zauważmy , że:

\(\displaystyle{ a(n)=3^n-b(n)}\)

\(\displaystyle{ b(3)=2 \cdot 2 \cdot 3^1-2 \cdot}\)

\(\displaystyle{ b(4)=2 \cdot 3 \cdot 3^2-2 \cdot 2+2 \cdot 2 \cdot 3-2}\)


teraz może mały komentarz jak to leci:

Pierwszy składnik składa się z jednego nazwijmy to bąbelka typu:

\(\displaystyle{ (1,3)}\) lub \(\displaystyle{ (3,1)}\) dlatego zawsze bąbelek na początku jest mnożony przez dwa bo mogą być dwie permutacje, czyli pierwszy składnik jest postaci:

\(\displaystyle{ (1,3)x,y}\) gdzie \(\displaystyle{ x, y}\) dowolne liczby alfabetu na \(\displaystyle{ 3^2}\) sposobów

i widać elementów jest trzy a więc jest \(\displaystyle{ 3}\)

Drugi składnik w tej sumie jest postaci dwóch bąbelków:

\(\displaystyle{ (1,3)(1,3)}\) i dlatego:\(\displaystyle{ 2 \cdot 2}\)

Trzeci składnik jest typu potrójnego bąbelka:

\(\displaystyle{ (1,3,1)x}\) lub \(\displaystyle{ (3,1,3)x}\) x dowolna liczba z alfabetu czyli razy trzy, razem:

\(\displaystyle{ 2 \cdot 3}\)

Ostatni składnik jest typu bąbelka poczwórnego czyli:

\(\displaystyle{ (1,3,1,3)}\) lub \(\displaystyle{ (3,1,3,1)}\) dlatego tylko dwa.

Teraz uogólnienie:

\(\displaystyle{ b(n)=2 {n-1 \choose n-2}3^{n-2}-2^2 {n-2 \choose n-4}3^{n-4}+.....+(-2)^{ \left[ \frac{n}{2}\right] } {n \pmod{2}+1 \choose n\pmod{2} }3^{n \pmod{2}}}\) - bąbelki podwójne

\(\displaystyle{ -\left( +2 {n-2 \choose n-3}3^{n-3}-2^2 {n-4 \choose n-6}3^{n-6}+.....+(-2)^{\left[ \frac{n}{3}\right] } {n \pmod{3}+1 \choose n\pmod{3} }3^{n \pmod{3}}\right)}\) - bąbelki potrójne

............................................................................................

\(\displaystyle{ \pm \left( 2 {n-k+1 \choose n-k} 3^{n-k}-2^2 {n-2k+2 \choose n-2k}3^{n-2k}+...(-2)^{\left[ \frac{n}{k} \right] } {n \pmod{k}+1 \choose n\pmod{k} }3^{n \pmod{k}}\right)}\) - bąbelki k tej długości

................................................................................................

No i mieszane

..............................................................

\(\displaystyle{ \pm 2}\)

- jeden największy bąbelek

Korzystam jak widać podwójnie z zasady włączania i wyłączania



kombinacje biorę z tego, że jak mam np: dwa bąbelki:

\(\displaystyle{ ...(1,2)... (1,2).....}\)

To między nimi daję pozostałe słowa czyli w tym przypadku: \(\displaystyle{ n-4}\)

Na sposobów:

\(\displaystyle{ x+y+z=n-4}\),

czyli:

\(\displaystyle{ {n-4+3-1 \choose n-4}= {n-2 \choose n-4}}\)

Przedtem była pomyłka bo dawałem silnię a to było źle!


Oczywiście ja cały czas liczę ilość\(\displaystyle{ b(n)}\), ale wyliczenie \(\displaystyle{ a(n)}\) to tylko odjęcie od wszystkich możliwości czyli \(\displaystyle{ 3^n}\)

Pokazałem dla jasności jak zrobić dla alfabetu trzyliterowego, uogólnienie dla alfabetu n - literowego jest analogiczne!

[a4karo]

Słowa, w których pierwsza i ostatnia litera są obok siebie są słowami dwuliterowymi, więc dla \(\displaystyle{ m=2}\) ta ilośc wynosi zero. Dla pozostałych rachunek jest elementarny

[norwimaj]

Słowa, w których pierwsza i ostatnia litera są obok siebie są słowami dwuliterowymi

To tylko jeden z co najmniej trzech sposobów rozumienia treści. Kto inny powie, że w słowie \(\displaystyle{ bacba}\) pierwsza litera występuje obok ostatniej, a jednak nie jest ono dwuliterowe. Najpewniej jednak chodzi o pierwszą i ostatnią literę alfabetu (chociaż treść nie mówi, że alfabet jest uporządkowany).

[Edytowałem, bo słowo \(\displaystyle{ baba}\) nie było dobrym przykładem.]

Trzeba będzie skorzystać z zasady włączania i wyłączania.

Nieprawda. Możesz ułożyć wzory rekurencyjne na takie ciągi:

\(\displaystyle{ a_m}\) - liczba słów długości \(\displaystyle{ m}\), kończących się literą \(\displaystyle{ \alpha}\) (jest to też liczba słów długości \(\displaystyle{ m}\), kończących się literą \(\displaystyle{ \omega}\))
\(\displaystyle{ b_m}\) - liczba słów długości \(\displaystyle{ m}\), które nie kończą się na \(\displaystyle{ \alpha}\) ani na \(\displaystyle{ \omega}\)

Wówczas liczba \(\displaystyle{ 2a_m+b_m}\) jest odpowiedzią do zadania.

[arek1357]

Jeżeli mamy alfabet trzyliterowy a,b,c

to niepoprawne są słowa:

\(\displaystyle{ \left( aca\right)}\)

\(\displaystyle{ \left( acb\right)}\)

\(\displaystyle{ \left( acc\right)}\)

\(\displaystyle{ \left( caa\right)}\)

\(\displaystyle{ \left( cab\right)}\)

\(\displaystyle{ \left( cac\right)}\)

\(\displaystyle{ \left( aac\right)}\)

\(\displaystyle{ \left( bac\right)}\)

\(\displaystyle{ \left( bca\right)}\)

\(\displaystyle{ \left( cca\right)}\)

co widać , że \(\displaystyle{ b(3)=10}\)

zgodnie z tym co napisałem wcześniej:

stosując zasadę włączania i wyłączania:

\(\displaystyle{ b(3)=2 \cdot 2 \cdot 3^1-2=10}\)

w związku z tym:

\(\displaystyle{ a(3)=3^3-10=17}\)


Tak ja napisałem:

Trzeba będzie skorzystać z zasady włączania i wyłączania.

Norwimaj napisał:

nieprawda

Czy jeśli napiszę:

Można skorzystać z zasady włączania i wyłączania.

Czy też temu zaprzeczysz?

A czy nie lepiej napisać:

Można użyć rekurencji lub zasady włączania i wyłączania

Nie jest to bardziej adekwatne takie zdanie?

A teraz odnoszą się do Twojej rekurencji jak ją dalej pociągniesz?

Rozpisz mi ją dla przypadku tego co podałem czyli alfabet trzyliterowy a ciąg długości trzy...
zobaczymy czy się zgodzi!

Jeśli się zgodzi będzie to bardzo dobra wiadomość.

[norwimaj]

Czy jeśli napiszę:

Można skorzystać z zasady włączania i wyłączania.

Czy też temu zaprzeczysz?

Nie.

A czy nie lepiej napisać:

Można użyć rekurencji lub zasady włączania i wyłączania

Nie jest to bardziej adekwatne takie zdanie?

Nie wiem.

A teraz odnoszą się do Twojej rekurencji jak ją dalej pociągniesz?

Rozpisz mi ją dla przypadku tego co podałem czyli alfabet trzyliterowy a ciąg długości trzy...
zobaczymy czy się zgodzi!

Dla ciągów \(\displaystyle{ a_m, b_m}\) takich, jak je zdefiniowałem, zachodzi wzór rekurencyjny:

\(\displaystyle{ \begin{pmatrix}a_m\\ b_m\end{pmatrix}=
\begin{pmatrix}1 & 1 \\ 2(n-2) & n-2\end{pmatrix}
\cdot\begin{pmatrix}a_{m-1}\\ b_{m-1}\end{pmatrix},}\)

stąd wynik jest równy:

\(\displaystyle{ 2a_m+b_m= \begin{pmatrix}2&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ 2(n-2) & n-2\end{pmatrix}^m
\cdot\begin{pmatrix}0\\1\end{pmatrix}.}\)

Dla \(\displaystyle{ n=3}\) i \(\displaystyle{ m=3}\) dostajemy:

\(\displaystyle{ \begin{pmatrix}2&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix}^3
\cdot\begin{pmatrix}0\\1\end{pmatrix}=\\
\begin{pmatrix}2&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix}^2
\cdot\begin{pmatrix}1\\1\end{pmatrix}=\\
\begin{pmatrix}2&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix}
\cdot\begin{pmatrix}2\\3\end{pmatrix}=\\
\begin{pmatrix}2&1\end{pmatrix}
\cdot\begin{pmatrix}5\\7\end{pmatrix}=17.}\)

Ogólniej dla \(\displaystyle{ n=3}\) wynik jest równy:

\(\displaystyle{ 2a_m+b_m=b_{m+1}=
\begin{pmatrix}0&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ 2 & 1\end{pmatrix}^{m+1}
\cdot\begin{pmatrix}0\\1\end{pmatrix}=\\\\
\frac1{2\sqrt2}\cdot\begin{pmatrix}0&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ \sqrt2 & -\sqrt2\end{pmatrix}
\cdot\begin{pmatrix}(1+\sqrt2)^{m+1} & 0 \\ 0 & (1-\sqrt2)^{m+1}\end{pmatrix}
\cdot\begin{pmatrix}\sqrt2 & 1 \\ \sqrt2 & -1\end{pmatrix}
\cdot\begin{pmatrix}0\\1\end{pmatrix}=\\\\
\frac1{2\sqrt2}\cdot\begin{pmatrix}0&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ \sqrt2 & -\sqrt2\end{pmatrix}
\cdot\begin{pmatrix}(1+\sqrt2)^{m+1} & 0 \\ 0 & (1-\sqrt2)^{m+1}\end{pmatrix}
\cdot\begin{pmatrix}1\\-1\end{pmatrix}=\\\\
\frac1{2\sqrt2}\cdot\begin{pmatrix}0&1\end{pmatrix}
\cdot\begin{pmatrix}1 & 1 \\ \sqrt2 & -\sqrt2\end{pmatrix}
\cdot\begin{pmatrix}(1+\sqrt2)^{m+1} \\ -(1-\sqrt2)^{m+1}\end{pmatrix}=\\\\
\frac1{2\sqrt2}\cdot\begin{pmatrix}0&1\end{pmatrix}
\cdot\begin{pmatrix}(1+\sqrt2)^{m+1}-(1-\sqrt2)^{m+1} \\
\sqrt2(1+\sqrt2)^{m+1}+\sqrt2(1-\sqrt2)^{m+1}\end{pmatrix}=\\\\
\frac1{2\sqrt2}\cdot\begin{pmatrix}\sqrt2(1+\sqrt2)^{m+1}+\sqrt2(1-\sqrt2)^{m+1}\end{pmatrix}=\\\\
\frac{(1+\sqrt2)^{m+1}+(1-\sqrt2)^{m+1}}2.}\)

[arek1357]

No to teraz się zgadza wszystko!

Czas sprawdzić oba wzory i porównać czy się zgadzają bo inaczej nie miałoby to sensu.

U mnie:

\(\displaystyle{ b(4)=2 {3 \choose 2}3^2-4 \cdot 1}\) - bąbelki podwójne ( dwie sztuki)

\(\displaystyle{ -2 {2 \choose 1} \cdot 3}\) - bąbelki potrójne ( jedna sztuka)

\(\displaystyle{ +2}\) - bąbelki poczwórne (jedna sztuka)

\(\displaystyle{ =54-4-12+2=40}\)

Ja korzystam w sposób podwójny z zasady włączania i wyłączania!

czyli:

\(\displaystyle{ b(4)=40}\)

ostatecznie:

\(\displaystyle{ a(4)=3^4-40=41}\)

U Norwimaja:

\(\displaystyle{ a(4)=\frac{(1+\sqrt{2})^{4+1}+(1-\sqrt{2})^{4+1}}{2}=41}\)

Co łatwo wyliczyć.

\(\displaystyle{ b(5)=2 \cdot 4 \cdot 27-36-54+10+8=144}\)

\(\displaystyle{ a(5)=243-144=99}\)

W tym przypadku mieszane będą dwa typu:

\(\displaystyle{ (---)(--)}\)

co daje osiem możliwości: \(\displaystyle{ 2 \cdot 2 \cdot 2=8}\)

\(\displaystyle{ a(5)=\frac{(1+\sqrt{2})^{5+1}+(1-\sqrt{2})^{5+1}}{2}=99}\)

Oczywiście dla ciągów o długości trzy też się zgadza bo wychodzi:

\(\displaystyle{ b(3)=10, a(3)=17}\)

Jasne jest , że wzór Norwimaja jest dużo ładniejszy jak gdyby zwinięty.
Zresztą nigdy nie przepadałem za zasadą włączania i wyłączania rekurencja jest zawsze elegantsza!

U mnie we wzorze jak za trzy podstawimy jakąś inną liczbę będziemy mieć wzór dla dowolnego alfabetu!