Wyznaczyć liczbę permutacji zbioru, kombinatoryka

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kylercopeland
Użytkownik
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

Post autor: kylercopeland »

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.
Ostatnio zmieniony 21 lis 2017, o 00:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Wyznaczyć liczbę permutacji zbioru, kombinatoryka

Post autor: arek1357 »

A jaka to jest naturalna pozycja?
kylercopeland
Użytkownik
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

Post autor: kylercopeland »

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!}\)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Wyznaczyć liczbę permutacji zbioru, kombinatoryka

Post autor: arek1357 »

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.

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}\).
Udało mi się znaleźć wzór, który sprawdziłem generując takie permutacje i jest on poprawny
A ty skąd wygenerowałeś ten wzór wytłumacz mi to, bo moje hobby to szukanie różnych wzorów,


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.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Wyznaczyć liczbę permutacji zbioru, kombinatoryka

Post autor: kerajs »

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