Dzień Dobry,
Proszę o pomoc w rozwiązaniu dwóch zadanek.
1) Wyznaczyć liczbę permutacji zbioru \(\displaystyle{ \{1,2,3,4,5,6,7,8\}}\), w których żadna liczba parzysta nie znajduje się na swojej naturalnej pozycji.
2) Przed spektaklem 7 osób zostawiło w szatni swoje parasole. Na ile sposobów parasole te mogą zostać zwrócone pod warunkiem, że co najmniej dwie osoby otrzymają swoje parasole.
Wyznaczyć liczbę permutacji zbioru, kombinatoryka
-
- Użytkownik
- Posty: 150
- Rejestracja: 20 lis 2017, o 21:52
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 54 razy
Wyznaczyć liczbę permutacji zbioru, kombinatoryka
Ostatnio zmieniony 21 lis 2017, o 00:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 150
- Rejestracja: 20 lis 2017, o 21:52
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 54 razy
Wyznaczyć liczbę permutacji zbioru, kombinatoryka
Myślę że np. dla 2 pozycja 2, dla 4 pozycja 4 itd.-- 21 lis 2017, o 15:00 --Udało mi się znaleźć wzór, który sprawdziłem generując takie permutacje i jest on poprawny. Nie wiem jednak skąd się on bierze.
\(\displaystyle{ 8!-{4 \choose 1}*7!+{4 \choose 2}*6!- {4 \choose 3}*5! +{4 \choose 4}*4!}\)
\(\displaystyle{ 8!-{4 \choose 1}*7!+{4 \choose 2}*6!- {4 \choose 3}*5! +{4 \choose 4}*4!}\)
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Wyznaczyć liczbę permutacji zbioru, kombinatoryka
Napiszemy, jest to permutacja z zakazanymi miejscami
Ten Twój wzór jest ok...
Na tym rysunku poniżej masz szachownicę \(\displaystyle{ 8 \times 8}\) , której wiersze odpowiadają permutowanym elementom
a kolumny ich pozycjom.
czarne pola to miejsca zakazane. (Tam gdzie nie mogą stanąć poszczególne elementy).
niech teraz -\(\displaystyle{ X}\)- zbiór czarnych pól.
\(\displaystyle{ r_{k}(X)}\)- będzie liczbą sposobów umieszczenia na \(\displaystyle{ X, k}\) wież wzajemnie się nie atakujących.
Ale w Twoim przypadku wzajemnie nie atakujące się wieże są na każdych polach \(\displaystyle{ X}\) jak łatwo zauważyć.
Przyjmujemy jeszcze, że:
\(\displaystyle{ r_{0}(X)=1}\)
i dalej:
\(\displaystyle{ r_{1}(X)= {4 \choose 1}}\)
\(\displaystyle{ r_{2}(X)= {4 \choose 2}}\)
\(\displaystyle{ r_{3}(X)= {4 \choose 3}}\)
\(\displaystyle{ r_{4}(X)= {4 \choose 4}}\)
oczywiście dla:
\(\displaystyle{ k>4,}\)
\(\displaystyle{ r_{k}(X)=0}\)
teraz jest wzór:
\(\displaystyle{ S_{k}=r_{k}(X)(8-k)!}\)
I ostatecznie wzór na ilośc permutacji z zasady włączania i wyłączania mamy:
\(\displaystyle{ N= \sum_{i=0}^{8}(-1)^iS_{i}= \sum_{i=0}^{4}(-1)^iS_{i}=8!- {4 \choose 1} \cdot 7!+{4 \choose 2} \cdot 6!-{4 \choose 3} \cdot 5!+{4 \choose 4} \cdot 4!}\)
reasumując masz to co napisałeś...
To są permutacje z zakazanymi miejscami (ograniczeniami) warto o tym poczytać...
Wszystko tu zależy od zbioru - \(\displaystyle{ X}\) , czasem gorzej jest przeliczyć - \(\displaystyle{ r_{k}}\),
dla inaczej zadanego zbioru miejsc zakazanych a u Ciebie było to łatwe z uwagi na prostotę zbioru - \(\displaystyle{ X}\).
Bo ja liczyłem ze wzoru, który mi Pani podała w szkółce niedzielnej (Zapyziałowice Dolne, pow. Bagno).
Ten Twój wzór jest ok...
Na tym rysunku poniżej masz szachownicę \(\displaystyle{ 8 \times 8}\) , której wiersze odpowiadają permutowanym elementom
a kolumny ich pozycjom.
Kod: Zaznacz cały
http://wstaw.org/w/4Idu/linki/
czarne pola to miejsca zakazane. (Tam gdzie nie mogą stanąć poszczególne elementy).
niech teraz -\(\displaystyle{ X}\)- zbiór czarnych pól.
\(\displaystyle{ r_{k}(X)}\)- będzie liczbą sposobów umieszczenia na \(\displaystyle{ X, k}\) wież wzajemnie się nie atakujących.
Ale w Twoim przypadku wzajemnie nie atakujące się wieże są na każdych polach \(\displaystyle{ X}\) jak łatwo zauważyć.
Przyjmujemy jeszcze, że:
\(\displaystyle{ r_{0}(X)=1}\)
i dalej:
\(\displaystyle{ r_{1}(X)= {4 \choose 1}}\)
\(\displaystyle{ r_{2}(X)= {4 \choose 2}}\)
\(\displaystyle{ r_{3}(X)= {4 \choose 3}}\)
\(\displaystyle{ r_{4}(X)= {4 \choose 4}}\)
oczywiście dla:
\(\displaystyle{ k>4,}\)
\(\displaystyle{ r_{k}(X)=0}\)
teraz jest wzór:
\(\displaystyle{ S_{k}=r_{k}(X)(8-k)!}\)
I ostatecznie wzór na ilośc permutacji z zasady włączania i wyłączania mamy:
\(\displaystyle{ N= \sum_{i=0}^{8}(-1)^iS_{i}= \sum_{i=0}^{4}(-1)^iS_{i}=8!- {4 \choose 1} \cdot 7!+{4 \choose 2} \cdot 6!-{4 \choose 3} \cdot 5!+{4 \choose 4} \cdot 4!}\)
reasumując masz to co napisałeś...
To są permutacje z zakazanymi miejscami (ograniczeniami) warto o tym poczytać...
Wszystko tu zależy od zbioru - \(\displaystyle{ X}\) , czasem gorzej jest przeliczyć - \(\displaystyle{ r_{k}}\),
dla inaczej zadanego zbioru miejsc zakazanych a u Ciebie było to łatwe z uwagi na prostotę zbioru - \(\displaystyle{ X}\).
A ty skąd wygenerowałeś ten wzór wytłumacz mi to, bo moje hobby to szukanie różnych wzorów,Udało mi się znaleźć wzór, który sprawdziłem generując takie permutacje i jest on poprawny
Bo ja liczyłem ze wzoru, który mi Pani podała w szkółce niedzielnej (Zapyziałowice Dolne, pow. Bagno).
Ostatnio zmieniony 21 lis 2017, o 17:59 przez arek1357, łącznie zmieniany 1 raz.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Wyznaczyć liczbę permutacji zbioru, kombinatoryka
2)
\(\displaystyle{ 7!-!7- {7 \choose 1} \cdot !6}\)
Od wszystkich układów odejmuję sytuacje gdy nikt nie dostał swojego parasola i te gdy tylko jedna dostała swój parasol.
\(\displaystyle{ 7!-!7- {7 \choose 1} \cdot !6}\)
Od wszystkich układów odejmuję sytuacje gdy nikt nie dostał swojego parasola i te gdy tylko jedna dostała swój parasol.