liczba permutacji

[waliant]

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

[a4karo]

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

[waliant]

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

[porfirion]

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

[waliant]

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

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

[porfirion]

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

[waliant]

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

[porfirion]

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 --

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}\)

[waliant]

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