Trzeba będzie skorzystać z zasady włączania i wyłączania.
Pokażę idee na przykładzie alfabetu trzycyfrowego :

i wiadomo, że jedynka i trójka nie może stać koło siebie, niech możliwość słów dozwolonych będzie

- to słowa o długości

niech teraz

ilość słów w których końcowe przynajmniej raz stoją koło siebie
z obserwacji:


Wszystkich możliwości jest

zauważmy , że:



teraz może mały komentarz jak to leci:
Pierwszy składnik składa się z jednego nazwijmy to bąbelka typu:

lub

dlatego zawsze bąbelek na początku jest mnożony przez dwa bo mogą być dwie permutacje, czyli pierwszy składnik jest postaci:

gdzie

dowolne liczby alfabetu na

sposobów
i widać elementów jest trzy a więc jest

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

i dlatego:

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

lub

x dowolna liczba z alfabetu czyli razy trzy, razem:

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

lub

dlatego tylko dwa.
Teraz uogólnienie:
![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(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}}](/latexrender/pictures/8/f/8f582043c549f284bb524feb7328bcd5.png)
- bąbelki podwójne
![-\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) -\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)](/latexrender/pictures/9/2/92c610cca46ce8164bc96b055e96b495.png)
- bąbelki potrójne
............................................................................................
![\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) \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)](/latexrender/pictures/6/8/6808d174ff967d3791a96f8b468f5df9.png)
- bąbelki k tej długości
................................................................................................
No i mieszane
..............................................................

- 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:

To między nimi daję pozostałe słowa czyli w tym przypadku:

Na sposobów:

,
czyli:

Przedtem była pomyłka bo dawałem silnię a to było źle!
Oczywiście ja cały czas liczę ilość

, ale wyliczenie

to tylko odjęcie od wszystkich możliwości czyli

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