liczba permutacji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
waliant
Użytkownik
Użytkownik
Posty: 1799
Rejestracja: 9 gru 2010, o 22:16
Płeć: Mężczyzna
Lokalizacja: warszawa

liczba permutacji

Post autor: waliant » 19 cze 2014, o 13:23

ile jest permutacji zbioru \(\displaystyle{ \left\{ 1,...,n\right\}}\) takich, że żadne dwie sąsiednie liczby nie są parzyste? Jak to się liczy?

a4karo
Użytkownik
Użytkownik
Posty: 16760
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz

liczba permutacji

Post autor: a4karo » 19 cze 2014, o 14:20

Zacznij od parzystych \(\displaystyle{ n}\). Jak muszą być umieszczone liczby, żeby były spełnione waruniki zadania?

Awatar użytkownika
waliant
Użytkownik
Użytkownik
Posty: 1799
Rejestracja: 9 gru 2010, o 22:16
Płeć: Mężczyzna
Lokalizacja: warszawa

liczba permutacji

Post autor: waliant » 19 cze 2014, o 14:26

dla parzystych \(\displaystyle{ n}\) muszą być naprzemiennie parzyste i nieparzyste rozpoczynając od obojętnie której. Czyli ile ich będzie?

porfirion
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 6 gru 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: Warszawa

liczba permutacji

Post autor: porfirion » 19 cze 2014, o 14:31

Można pomyśleć o tych zadanych ciągach jak o specyficznie "zaplecionych" permutacjach liczb parzystych z tego zbioru i nieparzystych.
Więc tak naprawdę to wystarczy policzyć ile jest takich różnych permutacji mod \(\displaystyle{ 2}\).
Czyli mamy jakieś \(\displaystyle{ k}\) liczb parzystych które tworzą nam \(\displaystyle{ k+1}\) szufladek - przy czym tych \(\displaystyle{ k-1}\) środkowych szufladek nie może być pustych:

_p_p_p_p_p...p_p_

Zostaje nam \(\displaystyle{ 1}\) względnie \(\displaystyle{ 2}\) nierozróżnialne liczby nieparzyste np, które trzeba upchać w \(\displaystyle{ k+1}\) szufladek.

Mam nadzieję, że to ma sens i jest zrozumiałe XD
Ostatnio zmieniony 19 cze 2014, o 14:52 przez porfirion, łącznie zmieniany 3 razy.

Awatar użytkownika
waliant
Użytkownik
Użytkownik
Posty: 1799
Rejestracja: 9 gru 2010, o 22:16
Płeć: Mężczyzna
Lokalizacja: warszawa

liczba permutacji

Post autor: waliant » 19 cze 2014, o 14:33

porfirion pisze:
Mam nadzieję, że to ma sens i jest zrozumiałe XD

Nie jest, chyba lepszym sposobem będzie tutaj rozpatrzenie tych przypadków.

porfirion
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 6 gru 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: Warszawa

liczba permutacji

Post autor: porfirion » 19 cze 2014, o 14:44

Imo wychodzi:
dla \(\displaystyle{ n=2k}\) : \(\displaystyle{ k! \cdot k! {k+1 \choose 1}}\)

dla \(\displaystyle{ n=2k+1}\) : \(\displaystyle{ k!(k+1)!( {k+1 \choose 2}+ {k+1 \choose 1})}\)

Jak będziesz miał swój wynik to napisz :p
Ostatnio zmieniony 19 cze 2014, o 14:52 przez porfirion, łącznie zmieniany 1 raz.

Awatar użytkownika
waliant
Użytkownik
Użytkownik
Posty: 1799
Rejestracja: 9 gru 2010, o 22:16
Płeć: Mężczyzna
Lokalizacja: warszawa

liczba permutacji

Post autor: waliant » 19 cze 2014, o 14:51

a możesz napisać skąd taki wynik u Ciebie?

porfirion
Użytkownik
Użytkownik
Posty: 319
Rejestracja: 6 gru 2011, o 20:54
Płeć: Mężczyzna
Lokalizacja: Warszawa

liczba permutacji

Post autor: porfirion » 19 cze 2014, o 14:59

Poprzednio się pomyliłem w odejmowaniu...

Możemy sobie pomyśleć, że cała informacja o tym jak wygląda taka konkretna permutacja jest zawarta w dwóch rzeczach:

1) jak wygląda ta permutacja mod \(\displaystyle{ 2}\), czyli dla permutacji \(\displaystyle{ 1,2,3,4,5}\) mamy
\(\displaystyle{ 1,0,1,0,1}\)

2) jakie dwa ciągi byśmy dostali gdybyśmy rozważali same podciągi zawierające same liczby parzyste i same nieparzyste. Np: z \(\displaystyle{ 1,2,3,4,5}\) mamy \(\displaystyle{ 1,3,5}\) i \(\displaystyle{ 2,4}\)

Oba podciągi z 2) to zwykłe permutacje skąd człon \(\displaystyle{ (k+1)!k! \vee k!k!}\) zależnie od parzystości \(\displaystyle{ n}\)

Czyli wystarczy się zastanowić jak wygląda ten 0/1-kowy ciąg z 1).-- 19 cze 2014, o 14:04 --
waliant pisze:dla parzystych \(\displaystyle{ n}\) muszą być naprzemiennie parzyste i nieparzyste rozpoczynając od obojętnie której. Czyli ile ich będzie?
No właśnie nie, bo może być : \(\displaystyle{ 2,1,3,4}\)

Awatar użytkownika
waliant
Użytkownik
Użytkownik
Posty: 1799
Rejestracja: 9 gru 2010, o 22:16
Płeć: Mężczyzna
Lokalizacja: warszawa

liczba permutacji

Post autor: waliant » 19 cze 2014, o 15:10

niestety nie rozumiem Twojego rozwiązania, ale dzięki za chęci

ODPOWIEDZ