Przestawienia osób

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gutek927
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 21 paź 2012, o 22:45
Płeć: Mężczyzna
Lokalizacja: POLSKA
Podziękował: 3 razy

Przestawienia osób

Post autor: gutek927 »

Witam, mam problem z poniższym zdaniem.
N osób ponumerowanych od 1 do N stoi w szeregu tak, że osoba o numerze i stoi na i-tej pozycji. Na ile sposobów możemy poprzestawiać osoby tak, aby w nowym ustawieniu każda osoba stała albo na tej samej pozycji, na której stała na początku, albo na jednej z sąsiednich pozycji?
Nie mogę znaleźć metody, którą powinienem użyć do rozwiązania tego zadania.
Ostatnio zmieniony 14 gru 2017, o 00:50 przez SlotaWoj, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Ortografia.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Przestawienia osób

Post autor: arek1357 »

Dla \(\displaystyle{ n=1}\)

\(\displaystyle{ (1)}\) - jedna możliwość,

\(\displaystyle{ n=2}\)

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

\(\displaystyle{ (12)}\)

\(\displaystyle{ 2}\) możliwości

dla \(\displaystyle{ n=3}\)

\(\displaystyle{ 3}\) możliwości, itd. Łatwo zauważyć, że jak na początku damy \(\displaystyle{ (1)}\) potem będzie \(\displaystyle{ a_{n-1}}\) możliwości,

a jak damy: \(\displaystyle{ (1,2)}\) będzie: \(\displaystyle{ a_{n-2}}\) możliwości

Czyli:

\(\displaystyle{ a_{n}=a_{n-1}+a_{n-2}}\)
gutek927
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 21 paź 2012, o 22:45
Płeć: Mężczyzna
Lokalizacja: POLSKA
Podziękował: 3 razy

Przestawienia osób

Post autor: gutek927 »

Czyli przykładowo dla \(\displaystyle{ n = 10}\) , będzie tych możliwości \(\displaystyle{ 17}\) . Zgadza się?

-- 14 gru 2017, o 01:19 --

\(\displaystyle{ \left( 1\right)\left( 2\right)\left( 3\right)\left( 4\right)\left(5\right)}\)
\(\displaystyle{ \left( 1\right)\left( 2\right)\left( 3\right)\left( 5\right)\left(4\right)}\)
\(\displaystyle{ \left( 1\right)\left( 2\right)\left( 4\right)\left( 3\right)\left(5\right)}\)
\(\displaystyle{ \left( 1\right)\left( 3\right)\left( 2\right)\left( 4\right)\left(5\right)}\)
\(\displaystyle{ \left( 2\right)\left( 1\right)\left( 3\right)\left( 4\right)\left(5\right)}\)
\(\displaystyle{ \left( 2\right)\left( 1\right)\left( 4\right)\left( 3\right)\left(5\right)}\)
\(\displaystyle{ \left( 1\right)\left( 2\right)\left( 3\right)\left( 5\right)\left(4\right)}\)
\(\displaystyle{ \left( 1\right)\left( 3\right)\left( 2\right)\left( 5\right)\left(4\right)}\)

Dla \(\displaystyle{ n = 5}\) naliczyłem \(\displaystyle{ 8}\) kombinacji, więc coś się nie zgadza.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Przestawienia osób

Post autor: arek1357 »

dla: \(\displaystyle{ n=5}\) jest:

\(\displaystyle{ (1)(2)(3)(4)(5)}\)

\(\displaystyle{ (12)(3)(4)(5)}\)

\(\displaystyle{ (1)(23)(4)(5)}\)

\(\displaystyle{ (1)(2)(34)(5)}\)

\(\displaystyle{ (1)(2)(3)(45)}\)

\(\displaystyle{ (12)(34)(5)}\)

\(\displaystyle{ (12)(3)(45)}\)

\(\displaystyle{ (1)(23)(45)}\)

jest:

\(\displaystyle{ 8=a_{4}+a_{3}=5+3}\)

\(\displaystyle{ (12)}\) - oznacza, że np jedynka i dwójka zamienia się miejscami...

Wszystko się zgadza.

\(\displaystyle{ a_{1}=1}\)

\(\displaystyle{ a_{2}=2}\)

\(\displaystyle{ a_{3}=3}\)

\(\displaystyle{ a_{4}=5}\)

\(\displaystyle{ a_{5}=3+5=8}\)

\(\displaystyle{ a_{6}=5+8=13}\)

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

\(\displaystyle{ a_{10}=89}\)
gutek927
Użytkownik
Użytkownik
Posty: 20
Rejestracja: 21 paź 2012, o 22:45
Płeć: Mężczyzna
Lokalizacja: POLSKA
Podziękował: 3 razy

Re: Przestawienia osób

Post autor: gutek927 »

Czyli rozwiązaniem tego zadania jest ciag Fibonacciego
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Przestawienia osób

Post autor: arek1357 »

Taki ciut zmodyfikowany bo ciut inne warunki początkowe ale w sumie to tak...
ODPOWIEDZ