Matematyka.pl

Ile jest permutacji zbioru \(\displaystyle{ \left[ n\right]}\), które nie zawierają parzystych puntków stałych? Tzn. dla każdej zliczanej permutacji \(\displaystyle{ \sigma}\) i każdego \(\displaystyle{ k}\) mamy \(\displaystyle{ \sigma\left( 2k\right) \neq 2k}\).

Czy to zadanie można zrobić za pomocą zasady włączeń i wyłączeń, tzn. przyjąć

\(\displaystyle{ A _{i}}\)-zbiór permutacji taki, że \(\displaystyle{ \sigma\left( i\right)=i}\)

Wtedy dla n parzystego trzeba by policzyć \(\displaystyle{ \left| A _{2}' \cup A _{4}' \cup ... \cup A _{n}' \right|}\)
Dla nieparzystego do \(\displaystyle{ n-1}\)?

Czy w jakiś inny sposób rozwiązać do zadanie?

nieOna3 pisze:Wtedy dla n parzystego trzeba by policzyć \(\displaystyle{ \left| A _{2}' \cup A _{4}' \cup ... \cup A _{n}' \right|}\)
Dla nieparzystego do \(\displaystyle{ n-1}\)?

No nie bardzo, bo do \(\displaystyle{ A_2'}\) mogą należeć permutacje takie, że \(\displaystyle{ \sigma(4)=4}\). Jeśli założymy, że nasz szukany zbiór to \(\displaystyle{ B=\{\sigma:\ \forall_{2k}\ \sigma(2k)\neq 2k \}}\), to wtedy \(\displaystyle{ B'=\{\sigma:\ \exists_{2k}\ \sigma(2k)=2k\}=A_2\cup A_4\cup ...}\), gdzie \(\displaystyle{ A_i}\) jak u Ciebie. I tu można stosować zasadę w-w, o ile da się w miarę łatwo

Źle napisałam
Chodziło mi o \(\displaystyle{ \left| A _{2}' \cap A _{4}' \cap ... \cap A _{n} ' \right|}\).
Czy wtedy to zadziała?

A to ok, to jest to samo co napisałem, tylko, że jak chcesz skorzystać z zasady włączeń-wyłączeń to powinnaś mieć sumę (czyli np. dopełnienie tego, co napisałaś).

Wiem, że muszę mieć sumę, ale to już łatwo do tego dojść. Dziękuje za pomoc