szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 lis 2017, o 21:56 
Użytkownik

Posty: 133
Lokalizacja: Wrocław
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.
Góra
Mężczyzna Offline
PostNapisane: 21 lis 2017, o 13:16 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
A jaka to jest naturalna pozycja?
Góra
Mężczyzna Offline
PostNapisane: 21 lis 2017, o 14:29 
Użytkownik

Posty: 133
Lokalizacja: Wrocław
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.


8!-{4 \choose 1}*7!+{4 \choose 2}*6!- {4 \choose 3}*5! +{4 \choose 4}*4!
Góra
Mężczyzna Offline
PostNapisane: 21 lis 2017, o 17:08 
Użytkownik
Avatar użytkownika

Posty: 3490
Lokalizacja: blisko
Napiszemy, jest to permutacja z zakazanymi miejscami

Ten Twój wzór jest ok...


Na tym rysunku poniżej masz szachownicę 8 \times 8 , której wiersze odpowiadają permutowanym elementom
a kolumny ich pozycjom.

http://wstaw.org/w/4Idu/linki/

czarne pola to miejsca zakazane. (Tam gdzie nie mogą stanąć poszczególne elementy).

niech teraz -X- zbiór czarnych pól.

r_{k}(X)- będzie liczbą sposobów umieszczenia na X,  k wież wzajemnie się nie atakujących.

Ale w Twoim przypadku wzajemnie nie atakujące się wieże są na każdych polach X jak łatwo zauważyć.

Przyjmujemy jeszcze, że:

r_{0}(X)=1

i dalej:

r_{1}(X)= {4 \choose 1}

r_{2}(X)= {4 \choose 2}

r_{3}(X)= {4 \choose 3}

r_{4}(X)= {4 \choose 4}

oczywiście dla:

k>4,

r_{k}(X)=0

teraz jest wzór:

S_{k}=r_{k}(X)(8-k)!

I ostatecznie wzór na ilośc permutacji z zasady włączania i wyłączania mamy:

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 - X , czasem gorzej jest przeliczyć - r_{k},

dla inaczej zadanego zbioru miejsc zakazanych a u Ciebie było to łatwe z uwagi na prostotę zbioru - X.

Cytuj:
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).
Góra
Mężczyzna Offline
PostNapisane: 21 lis 2017, o 17:58 
Użytkownik
Avatar użytkownika

Posty: 6643
2)
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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 ustawianie cyfr w liczbe - ile mozliwosci?  Anonymous  2
 Ilość suriekcji zbioru k-elementowego na n-elementowy  DEXiu  2
 Zbiór zadań - KOMBINATORYKA  Arek  0
 Pięć pań i pięciu panów - kombinatoryka  Anonymous  1
 Rosnące kombinacje ograniczonego zbioru liczb naturalnych  krislodz  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl