Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Alfabet - słowa

Strona 1 z 1

[ Posty: 7 ]

Autor

Wiadomość

mol_ksiazkowy Offline

Tytuł: Alfabet - słowa

Napisane: 31 gru 2015, o 15:02

Posty: 5666
Lokalizacja: Kraków

Ile jest słów $m$ literowych nad alfabetem mającym $n$ liter, w których pierwsza i ostatnia litera nie są obok siebie ?

Góra

arek1357 Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 11:07

Posty: 3488
Lokalizacja: blisko

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

Pokażę idee na przykładzie alfabetu trzycyfrowego : $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 $a(n)$ - to słowa o długości $n$

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

z obserwacji:

$a(1)=3, b(1)=0$

$a(2)=7, b(2)=2: (1,3)(3,1)$

Wszystkich możliwości jest $3^2$

zauważmy , że:

$a(n)=3^n-b(n)$

$b(3)=2 \cdot 2 \cdot 3^1-2 \cdot$

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

$(1,3)$ lub $(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:

$(1,3)x,y$ gdzie $x, y$ dowolne liczby alfabetu na $3^2$ sposobów

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

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

$(1,3)(1,3)$ i dlatego: $2 \cdot 2$

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

$(1,3,1)x$ lub $(3,1,3)x$ x dowolna liczba z alfabetu czyli razy trzy, razem:

$2 \cdot 3$

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

$(1,3,1,3)$ lub $(3,1,3,1)$ 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ą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)$ - 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)$ - bąbelki k tej długości

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

No i mieszane

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

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

$...(1,2)... (1,2).....$

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

Na sposobów:

$x+y+z=n-4$ ,

czyli:

${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ść $b(n)$ , ale wyliczenie $a(n)$ to tylko odjęcie od wszystkich możliwości czyli $3^n$

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

Góra

a4karo Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 11:34

Posty: 15823
Lokalizacja: Bydgoszcz

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

Góra

norwimaj Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 12:06

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E

a4karo napisał(a):

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 $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 $baba$ nie było dobrym przykładem.]

arek1357 napisał(a):

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

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

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

Wówczas liczba $2a_m+b_m$ jest odpowiedzią do zadania.

Góra

arek1357 Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 13:34

Posty: 3488
Lokalizacja: blisko

Jeżeli mamy alfabet trzyliterowy a,b,c

to niepoprawne są słowa:

$\left( aca\right)$

$\left( acb\right)$

$\left( acc\right)$

$\left( caa\right)$

$\left( cab\right)$

$\left( cac\right)$

$\left( aac\right)$

$\left( bac\right)$

$\left( bca\right)$

$\left( cca\right)$

co widać , że $b(3)=10$

zgodnie z tym co napisałem wcześniej:

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

$b(3)=2 \cdot 2 \cdot 3^1-2=10$

w związku z tym:

$a(3)=3^3-10=17$

Tak ja napisałem:

Cytuj:

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

Norwimaj napisał:

Cytuj:

nieprawda

Czy jeśli napiszę:

Cytuj:

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

Czy też temu zaprzeczysz?

A czy nie lepiej napisać:

Cytuj:

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ść.

Góra

norwimaj Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 15:55

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E

arek1357 napisał(a):

Czy jeśli napiszę:

Cytuj:

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

Czy też temu zaprzeczysz?

Nie.

arek1357 napisał(a):

A czy nie lepiej napisać:

Cytuj:

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

Nie jest to bardziej adekwatne takie zdanie?

Nie wiem.

arek1357 napisał(a):

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 $a_m, b_m$ takich, jak je zdefiniowałem, zachodzi wzór rekurencyjny:

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

$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 $n=3$ i $m=3$ dostajemy:

$\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 $n=3$ wynik jest równy:

$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.$

Góra

arek1357 Offline

Tytuł: Alfabet - słowa

Napisane: 1 sty 2016, o 16:48

Posty: 3488
Lokalizacja: blisko

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:

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

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

$+2$ - bąbelki poczwórne (jedna sztuka)

$=54-4-12+2=40$

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

czyli:

$b(4)=40$

ostatecznie:

$a(4)=3^4-40=41$

U Norwimaja:

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

Co łatwo wyliczyć.

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

$a(5)=243-144=99$

W tym przypadku mieszane będą dwa typu:

$(---)(--)$

co daje osiem możliwości: $2 \cdot 2 \cdot 2=8$

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

$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!

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 7 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
słowa długości n	onmyway	1
Alfabet	Manio0017	1
układanie słowa	titazez11	4
Wybrać 3-osobową delegację i drugie- różne słowa 3-literowe.	jajokop	2
alfabet Morse`a	monia255	1

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]