szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 19 cze 2014, o 13:23 
Użytkownik
Avatar użytkownika

Posty: 1799
Lokalizacja: warszawa
ile jest permutacji zbioru \left\{ 1,...,n\right\} takich, że żadne dwie sąsiednie liczby nie są parzyste? Jak to się liczy?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:20 
Użytkownik

Posty: 16622
Lokalizacja: Bydgoszcz
Zacznij od parzystych n. Jak muszą być umieszczone liczby, żeby były spełnione waruniki zadania?
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:26 
Użytkownik
Avatar użytkownika

Posty: 1799
Lokalizacja: warszawa
dla parzystych n muszą być naprzemiennie parzyste i nieparzyste rozpoczynając od obojętnie której. Czyli ile ich będzie?
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:31 
Użytkownik

Posty: 319
Lokalizacja: Warszawa
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 2.
Czyli mamy jakieś k liczb parzystych które tworzą nam k+1 szufladek - przy czym tych k-1 środkowych szufladek nie może być pustych:

_p_p_p_p_p...p_p_

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

Mam nadzieję, że to ma sens i jest zrozumiałe XD
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:33 
Użytkownik
Avatar użytkownika

Posty: 1799
Lokalizacja: warszawa
porfirion napisał(a):

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


Nie jest, chyba lepszym sposobem będzie tutaj rozpatrzenie tych przypadków.
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:44 
Użytkownik

Posty: 319
Lokalizacja: Warszawa
Imo wychodzi:
dla n=2k : k! \cdot k! {k+1 \choose 1}

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

Jak będziesz miał swój wynik to napisz :p
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:51 
Użytkownik
Avatar użytkownika

Posty: 1799
Lokalizacja: warszawa
a możesz napisać skąd taki wynik u Ciebie?
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 14:59 
Użytkownik

Posty: 319
Lokalizacja: Warszawa
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 2, czyli dla permutacji 1,2,3,4,5 mamy
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 1,2,3,4,5 mamy 1,3,5 i 2,4

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

Czyli wystarczy się zastanowić jak wygląda ten 0/1-kowy ciąg z 1).

-- 19 cze 2014, o 14:04 --

waliant napisał(a):
dla parzystych 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ć : 2,1,3,4
Góra
Mężczyzna
PostNapisane: 19 cze 2014, o 15:10 
Użytkownik
Avatar użytkownika

Posty: 1799
Lokalizacja: warszawa
niestety nie rozumiem Twojego rozwiązania, ale dzięki za chęci
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba permutacji  prs613  1
 liczba permutacji - zadanie 5  nieOna3  4
 Liczba permutacji - zadanie 3  Heniek1991  0
 Liczba permutacji - zadanie 8  ludozyad  5
 Liczba permutacji - zadanie 2  Marshall32  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl