Permutacje zbioru, kombinatoryka

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
kylercopeland
Witam na forum
Witam na forum
Posty: 8
Rejestracja: 20 lis 2017, 21:51
Podziękowania: 1 raz

Permutacje zbioru, kombinatoryka

Post autor: kylercopeland »

Dzień Dobry,
Proszę o pomoc w rozwiązaniu dwóch zadanek.

1) Wyznaczyć liczbę permutacji zbioru {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.
kylercopeland
Witam na forum
Witam na forum
Posty: 8
Rejestracja: 20 lis 2017, 21:51
Podziękowania: 1 raz

Re: Permutacje zbioru, kombinatoryka

Post autor: kylercopeland »

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.


\(8!-{4 \choose 1}*7!+{4 \choose 2}*6!- {4 \choose 3}*5! +{4 \choose 4}*4!\)
radagast
Guru
Guru
Posty: 17549
Rejestracja: 09 lis 2010, 07:38
Lokalizacja: Warszawa
Podziękowania: 41 razy
Otrzymane podziękowania: 7435 razy
Płeć:

Post autor: radagast »

\({4 \choose 4}*4!\) tyle jest permutacji, w których wszystkie cztery parzyste stoją na swoim miejscu,
\({4 \choose 3}*5!\) tyle jest permutacji, w których każde trzy parzyste stoją na swoim miejscu (pozostała gdzie chce),
\({4 \choose 2}*6!\) tyle jest permutacji, w których każde dwie parzyste stoją na swoim miejscu (pozostałe gdzie chcą),
\({4 \choose 1}*7!\) tyle jest permutacji, w których każda parzysta stoi na swoim miejscu .

\({4 \choose 3}*5!-{4 \choose 4}*4!\) tyle jest permutacji, w których każde trzy parzyste stoją na swoim miejscu ale cztery to już nie. Czyli dokładnie trzy parzyste stoją na swoim miejscu

\({4 \choose 2}*6!- \left( {4 \choose 3}*5!-{4 \choose 4}*4!\right)\) tyle jest permutacji, w których każde dwie parzyste stoją na swoim miejscu ale trzy to już nie. Czyli dokładnie dwie parzyste stoją na swoim miejscu

\({4 \choose 1}*7! -\left[{4 \choose 2}*6!- \left( {4 \choose 3}*5!-{4 \choose 4}*4!\right) \right]\) tyle jest permutacji, w których wszystkie parzyste stoją na swoim miejscu ale dwie to już nie. Czyli dokładnie jedna parzysta stoi na swoim miejscu.

No i jeszcze jeden krok i masz co trzeba :)
radagast
Guru
Guru
Posty: 17549
Rejestracja: 09 lis 2010, 07:38
Lokalizacja: Warszawa
Podziękowania: 41 razy
Otrzymane podziękowania: 7435 razy
Płeć:

Re: Permutacje zbioru, kombinatoryka

Post autor: radagast »

kylercopeland pisze: 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.
To wydaje się znacznie łatwiejsze:
\({7 \choose 2 } \cdot 5!=2520\) wybieramy dwie osoby, które otrzymają swoje parasole, a pozostałym dajemy "jak popadnie".
kylercopeland
Witam na forum
Witam na forum
Posty: 8
Rejestracja: 20 lis 2017, 21:51
Podziękowania: 1 raz

Post autor: kylercopeland »

Pierwsze zadanie było dobrze, drugie niestety nie. Powinno być 7! - !7 -7*!6
kerajs
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Re:

Post autor: kerajs »

kylercopeland pisze: Powinno być 7! - !7 -7*!6
To wynik z książki, czy koszałki jakiegoś ignoranta na innym forum ?
kylercopeland
Witam na forum
Witam na forum
Posty: 8
Rejestracja: 20 lis 2017, 21:51
Podziękowania: 1 raz

Re: Permutacje zbioru, kombinatoryka

Post autor: kylercopeland »

Z książki.
radagast
Guru
Guru
Posty: 17549
Rejestracja: 09 lis 2010, 07:38
Lokalizacja: Warszawa
Podziękowania: 41 razy
Otrzymane podziękowania: 7435 razy
Płeć:

Re:

Post autor: radagast »

kylercopeland pisze: Powinno być 7! - !7 -7*!6
Co oznacza zapis "!7" oraz "!6" ?
kerajs
Fachowiec
Fachowiec
Posty: 2963
Rejestracja: 14 lis 2016, 14:38
Podziękowania: 33 razy
Otrzymane podziękowania: 1303 razy
Płeć:

Post autor: kerajs »

@Radagast
To podsilnia. Zlicza liczbę nieporządków: https://pl.wikipedia.org/wiki/Nieporz%C4%85dek

@kylercopeland
A jaka to książka?
ODPOWIEDZ