Kombinatoryka - rozmieszczenia, zbiory.

[Apic16]

Witam, kilka zadań do rozwiązania, ktoś chętny?
1. Rozmieszczamy przy okrągłym stole \(\displaystyle{ n}\) par małżeńskich tak by żadna para nie siedziała obok siebie .Ile jest takich rozmieszczeń?(Wyprowadź wzór ogólny.)
2. Ile jest \(\displaystyle{ k}\)−elementowych podzbiorów zbioru liniowo uporządkowanego \(\displaystyle{ n}\)−elementowego \(\displaystyle{ (X, \ge ≥)}\)
takich, w których nie ma pary elementów bezpośrednio sąsiadujących ze sobą względem porządku \(\displaystyle{ \ge}\).
3. W rodzinie \(\displaystyle{ \beta}\) zbiorow z powtorzeniami o elementach z danego (skonczonego) zbioru \(\displaystyle{ X}\) relacje
"zawierania" definiujemy w naturalny sposob gdy \(\displaystyle{ f,g \in \beta}\) to \(\displaystyle{ f \subset ⊂ g}\) oznacza, ze kazdy element z \(\displaystyle{ X}\)
występujący w \(\displaystyle{ f}\), wystepuje tez w \(\displaystyle{ g}\) nie rzadziej niz w \(\displaystyle{ f}\) . Czy liczba takich \(\displaystyle{ k}\) −elementowych
"podzbiorów" ustalonego zbioru \(\displaystyle{ f \in \beta}\) zależy tylko od mocy \(\displaystyle{ f}\)?
(Jeśli tak to udowodnij, jeśli nie podaj kontrprzykład.)-- 21 cze 2018, o 18:26 --Czy do zadania 4 będzie dobry wzór : \(\displaystyle{ \sum_{i=0}^{n}(-1)^i {n \choose i}(2n-i-1)! \cdot 2^i}\) ?

[Dilectus]

Chętny do czego?

[Premislav]

To dopiero niezłe nieporozumienie, pisać trzy zadania i pytać, czy do czwartego będzie dobry jakiś wzór.

2. W porządku liniowym chodzi, jak pamiętam, o to, że dowolne dwa elementy zbioru, na którym tenże porządek wprowadzamy, są porównywalne względem tegoż porządku. No to mamy zbiór n-elementowy \(\displaystyle{ X}\) i dwa elementy \(\displaystyle{ x<y}\) nie są bezpośrednimi sąsiadami, jeśli istnieje takie \(\displaystyle{ z\in X}\), że
\(\displaystyle{ x<z}\) i \(\displaystyle{ z<y}\). A, no i relacja porządku daje nam słabą antysymetrię. Czyli \(\displaystyle{ X}\) z tą relacją tworzy łańcuch i nasze zadanie sprowadza się do takiego pytania. Mamy w rzędzie \(\displaystyle{ n}\) kulek (pierwsza kulka to element najmniejszy, druga to ten bezpośrednio nad nim itd.). Na ile sposobów możemy spośród nich wybrać tak \(\displaystyle{ k}\) kulek, aby żadne dwie wybrane kulki nie leżały obok siebie?
To jest chyba znany problem, odpowiedź to \(\displaystyle{ {n-k+1 \choose k}}\).