szukanie zaawansowane
 [ Posty: 7 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 gru 2015, o 16:02 
Użytkownik

Posty: 5550
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 ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 12:07 
Użytkownik
Avatar użytkownika

Posty: 3224
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 terazb(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
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 12:34 
Użytkownik

Posty: 14723
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
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 13:06 
Użytkownik

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
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 14:34 
Użytkownik
Avatar użytkownika

Posty: 3224
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
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 16:55 
Użytkownik

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
Mężczyzna Offline
PostNapisane: 1 sty 2016, o 17:48 
Użytkownik
Avatar użytkownika

Posty: 3224
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
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 7 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość wyrazów z jednego słowa.  truskawkowa  4
 Ułożenie słowa, oblicz wartość wyrażenia  marcink13  5
 możliwa liczba słów ze słowa 'matematyka' (wytłumaczenie)  exculibrus  4
 Alfabet i ilość czwórek  Jedwabisty  1
 Tworzenie par ze słowa  MgielkaCuba  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl