Ile jest różnych ciągów.

1608 · Post autor: **1608** » 5 gru 2013, o 22:18

Ile jest różnych ciągów powstałych z ciągu \(\displaystyle{ \left\{ 1,2,...,n\right\}}\) przez przestawienie każdego z elementów o co najwyżej jedno miejsce w lewo lub prawo? Znajdź zależności rekurencyjną.
Bardzo proszę o wyjaśnienie jak rozwiązać to zadanie.

Gouranga · Post autor: **Gouranga** » 5 gru 2013, o 22:59

przesuwając jeden element w lewo przesuwasz sąsiadujący z nim z lewej w prawo
\(\displaystyle{ 1,2,3,\ldots \underbrace{k, k+1}_{\text{zamieniamy}} \ldots, n\\
1,2,3,\ldots k+1, k \ldots, n}\)

po tej operacji nie możemy już ruszyć k+1 ani k w żadną stronę

ile jest takich par sąsiadujących ze sobą elementów w ciągu długości n?
ile par odpada nam po każdym ruchu?

1608 · Post autor: **1608** » 6 gru 2013, o 09:26

Takich par jest \(\displaystyle{ \frac{n}{2}}\)?
Przy każdym ruchu odpada jedna para ?

Gouranga · Post autor: **Gouranga** » 6 gru 2013, o 10:27

takich par jest \(\displaystyle{ n-1}\) (1 i 2, 2 i 3, 3 i 4 ... n-1 i n)

patrząc na ciąg który napisałem wyżej:
możemy na 2 sposoby wybrać parę z krańców (1,2 albo n-1,n) lub na n-3 ze środka
jeśli zamieniliśmy coś ze środka to odpadają 3
-k+1 i k
-k-1 i k+1
-k i k+2
i powstają nam 2 rozłączne ciągi (od 1 do k-1 i od k+2 do n) więc odpada nam jeszcze jedna para (między k-1 a k+2)
zobacz dla przykładu ciąg od 1 do 10
\(\displaystyle{ 1,2,3,4,5,6,7,8,9,10}\)
jest 9 par do wyboru, możemy wybrać 2 z krańców lub 7 ze środka (od 2,3 do 8,9)
\(\displaystyle{ 1,2,3,4,\underbrace{5,6}_{zamiana},7,8,9,10\\
1,2,3,4,6,5,7,8,9,10}\)

teraz osobno rozpatrujesz od 1 do 4 i osobno od 7 do 10

jest tylko jeden problem, którego nie umiem rozwiązać, otóż zawsze można jeszcze na 2 sposoby wybrać przy krańcu tak, żeby został jeden element nie do ruszenia (2,3 albo 8,9 w przykładzie) i nie wiem jak to dalej wpływa na zmniejszanie liczby możliwości, to musiałbyś sam przemyśleć

vpprof · Post autor: **vpprof** » 6 gru 2013, o 15:47

A jeśli chcę przesunąć drugi i trzeci element w lewo, to gdzie ląduje pierwszy element? Na trzeciej pozycji? Czyli tym samym przesunął się o dwa miejsca w prawo?

Gouranga · Post autor: **Gouranga** » 6 gru 2013, o 17:22

nie
mając fragment
1,2,3
możesz
-przesunąć 1 w prawo (lub 2 w lewo, to to samo) zyskując 2,1,3
-przesunąć 2 w prawo lub 3 w lewo zyskując 1,3,2

po każdej z nich nie możesz przesuwać nic dalej bo każdy element możesz tylko raz przesunąć i przykładowo z 2,1,3 nie możesz ruszyć 1 ani 2 bo już je ruszyłeś, 3 też nie bo to będzie równoznaczne z przesunięciem 1 w prawo a 1 nie możesz już ruszać

vpprof · Post autor: **vpprof** » 6 gru 2013, o 22:19

No dobrze, w takim razie ja to widzę tak. Jeśli ciąg ma jeden element to jest jeden ciąg, jeśli dwa elementy, to są dwa ciągi: \(\displaystyle{ \left\{ 1,2\right\},\left\{ 2,1\right\}}\). Dołożenie elementu powoduje, że można przestawić go:

o zero miejsc (nie ruszać go) — w tym przypadku mamy tyle ciągów, ile mieliśmy bez tego elementu,
o jedno miejsce w lewo — wtedy mamy tyle ciągów, ile mielibyśmy, gdyby dwóch ostatnich elementów nie było

Czyli nasze równanie rekurencyjne to \(\displaystyle{ \begin{cases}f(1)=1 \\ f(2)=2 \\ f(n+2)=f(n+1)+f(n)\end{cases}}\). Czyli ciąg Fibonacciego.

Gouranga · Post autor: **Gouranga** » 6 gru 2013, o 23:18

dokładnie
bo mając ciąg n-elementowy mamy na nim ileś możliwości, dostawiając nowy element mamy tyle ile było na n-elementowym + możliwość zamiany nowo dostawionego z przedostatnim i wszystkie możliwosci na n-1-elementowym

Przykładowo mamy
1,2,3 - 3 możliwości
dostawiamy nowy element
1,2,3,4
mamy 3 możliwości na 1,2,3 zostawiając 4 na końcu + 2 możliwości na 1,2 zakładając że na końcówce zamienimy na 4,3

Czyli ciąg Fibonacciego

vpprof · Post autor: **vpprof** » 6 gru 2013, o 23:23

Co przy okazji pokazuje dlaczego zawsze należy zaczynać od szukania rekurencji, nawet jeśli w poleceniu nie ma o nią prośby (a tu była).