szukanie zaawansowane
 [ Posty: 17 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 13 gru 2014, o 05:24 
Użytkownik

Posty: 8
Lokalizacja: warszawa
witam, mam problem, ktory nie daje mi spokoju, od kilku godzin sie mecze i nie wiem jak to ugryzc, wiec bede wdzieczny za pomoc :)

mam siedmiocyfrowa liczbe 1234567, przestawiam losowo cyfry aby stworzyc nowa liczbe, wg wzoru na wariacje bez powtorzen mam 5040 mozliwych kombinacji. Ile mozliwych kombinacji mam jesli doloze do tego warunek, ze zadna cyfra nie moze stac na tym samym miejscu co w liczbie wyjsciowej 1234567? czyli np. 1723456 nie spelnia warunku bo '1' znow stoi na tym samym miejscu. Z tego co do tej pory mi wyszlo nie do konca matematycznymi sposobami takich kombinacji bedzie cos ok. 1890 ale ile dokladnie?

jaki wzor zastosowac? jak obliczyc analogiczny problem ale np dla 9cyfrowej liczby 123456789?

jak obliczyc podobny problem w ktorym poza tym warunkiem beda dolozone jeszcze dodatkowe warunki, ze '1 w nowej liczbie nie moze takze stac na drugim miejscu, a '3' na czwartym?

z gory dzieki za pomoc :)
Góra
Mężczyzna Offline
PostNapisane: 13 gru 2014, o 10:32 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
Metoda włączania i wyłączania:

wszystkich permutacji jest 7!
wszystkich, gdzie co najmniej jedna jest na swoim miejscu jest {7 \choose 1} (7-1)! bo wybieramy jedną z siedmiu która zostaje a resztę przestawiamy

zwróć uwagę, że jeśli odejmiemy te opcje od wszystkich to np. taki układ: 1245673 odejmiemy dwukrotnie (dla 1 na swoim miejscu i dla 2 na swoim miejscu)
dlatego należy do wyniku dodać wszystkie opcje, gdzie co najmniej dwie stoją na swoim miejscu czyli {7 \choose 2}(7-2)! (analogicznie, 2 wybierz, resztę przemieszaj)

a co z układami gdzie np. 3 są na swoich miejscach?
zobaczmy: 1235674
najpierw odjęliśmy do 3 razy dla pojedynczych
potem dodaliśmy go trzy razy dla par 12, 13, 23
więc wyszliśmy do punktu wyjścia i trzeba odjąć te układy z conajmniej trzema na swoich miejscach
oczywiście tym działaniem np. układ 1234675 odejmiemy czterokrotnie ale to wszystko jest wliczone i takie dodawanie i odejmowanie na zmianę uzupełnia te nadmiary, z resztą możesz to sobie przeanalizować, układ 1234675 został 4 razy odjęty dla pojedynczych, 6 razy dodany dla podwójnych (12,13,14,23,24,34), potem 4 razy odjęty dla potrójnych (123,124,134,234) więc po podliczeniu został odjęty dwa razy czyli teraz trzeba znów go dodać

ostatecznie dostajemy:
\sum_{i=0}^{7} (-1)^i {7 \choose i}(7-i)! = 5040 - 7\cdot 720 + 21 \cdot 120 - 35 \cdot 24 + 35\cdot 6 - 21\cdot 2 + 7\cdot 1 - 1 = 1854

dla dziewięciocyfrowej analogicznie

a co do warunku że 1 nie może stać na drugim miejscu a 3 na czwartym robi się dokładnie to samo tzn. od wszystkich, które już mamy czyli tych 1854 najpierw odejmiemy wszystkie, gdzie nie jest spełniony pierwszy warunek czyli wszystkie z jedynką na drugim miejscu, jest ich 6!, potem odejmiemy wszystkie gdzie nie jest spełniony drugi czyli też 6! dla trójki na czwartym i potem dodamy wszystkie, w których oba warunki na raz nie są spełnione (bo się zdublowały przy odejmowaniu) czyli dodamy 5!
czyli takich opcji że żadna nie trafia na swoje miejsce i dodatkowo jedynka nie trafia na drugie a trójka na czwarte jest 1854 - 1440 + 120 = 534
Góra
Kobieta Offline
PostNapisane: 13 gru 2014, o 10:51 
Użytkownik
Avatar użytkownika

Posty: 2505
Do zliczania nieporządków służy słabnia:

!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}
Góra
Mężczyzna Offline
PostNapisane: 13 gru 2014, o 10:59 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
Medea 2,
!n = n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!} = \sum_{k=0}^n (-1)^k \frac{n!}{k!} = \sum_{k=0}^n (-1)^k {n \choose k} (n-k)! czyli dokładnie to samo co wywnioskowałem z metody włączania i wyłączania :)
Góra
Kobieta Offline
PostNapisane: 13 gru 2014, o 11:00 
Użytkownik
Avatar użytkownika

Posty: 2505
Tak, wiem, ale jeżeli arekk zainteresuje się tym tematem, to będzie chociaż wiedział, pod jakim hasłem szukać dalszych wskazówek - Twoje rozwiązanie jest oczywiście poprawne.
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 03:37 
Użytkownik

Posty: 8
Lokalizacja: warszawa
wielkie dzieki Gouaranga za lopatologiczne wyjasnienie, teraz juz wiem jak to dziala :) jak rowniez dzieki Medea2 za przedstawienie jak ten caly problem sie nazywa :)

o ile moj podstawowy problem wiem juz jak sie oblicza o tyle ciagle mam problem z dodatkowymi warunkami. W wikipedii pod linkiem http://pl.m.wikipedia.org/wiki/Nieporządek#Zliczanie_nieporz.C4.85dk.C3.B3w jest fajny przyklad z nauczycielem rozdajacym uczniom sprawdziany, ktory maja sprawdzic sobie nawzajem.

I teraz mam kolejny problem...powiedzmy, ze mamy siedmiu uczniow ABCDEFG, zaden nie moze sprawdzic sprawdzianu samemu sobie (czyli 1854 kombinacje), dodatkowo uczen A nie moze sprawdzac sprawdzianu uczniowi B i odwrotnie bo siedza razem w lawce, ta sama sytuacja dotyczy uczniow C i D oraz E i F.

Probowalem to policzyc tak jak Gouaranga sugerowal, ale nic sensownego mi nie wychodzi. Bede wdzieczny za pomoc :)
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 09:14 
Użytkownik

Posty: 704
drobna uwaga,

Gouranga napisał(a):
wszystkich, gdzie co najmniej jedna jest na swoim miejscu jest {7 \choose 1} (7-1)!


To nie jest prawda. To jest liczba wszystkich permutacji.
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 10:57 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
SidCom, istotnie, ale jest to także taka suma wszystkie z dokładnie jedną na swoim miejscu + 2 razy wszystkie z dokładnie dwoma na swoim miejscu + 3 razy wszystkie z dokładnie trzema itd.
bo na {7 \choose 1} wybieramy 1 z 7 która ma zostać a na (7-1)! permutujemy resztę ale tutaj się będą powtarzać przypadki jak już wsześniej tłumaczyłem

arekk, więc masz 6 dodatkowych warunków:
A nie sprawdza B
B nie sprawdza A
C nie sprawdza D
D nie sprawdza C
E nie sprawdza F
F nie sprawdza E

od 1854 odejmij wszystkie gdzie A sprawdza B, będzie ich dokładnie !6 = 265
liczymy przez słabnię bo nie możemy odjąć wszystkich permutacji bo one już są odjęte
odejmij też !6 dla każdego pozostałego warunku, potem dodaj {7 \choose 2}!5 bo dodajesz przekroje dwóch warunków (czyli 2 wybierasz, 5 mieszasz ale już w nieporządkach) itd.

czyli dla przykładu z uczniami powinno wyjść
\sum_{i=0}^{7} (-1)^i {7 \choose i} \cdot !(7-i)
Góra
Kobieta Offline
PostNapisane: 14 gru 2014, o 11:43 
Użytkownik
Avatar użytkownika

Posty: 2505
arekk, to zadanie jest już znacznie trudniejsze i raczej nie dostaniesz zwartej odpowiedzi. Jako rekurencja wygląda ona tak:

b_n = a_n \cdot {2^n}

Gdzie (a_0, a_1) = (1, 0), zaś

a_n = (2 n^2 - n) \cdot a_{n-1} + (2n^2  - 2n) \cdot a_{n-2}- 2n + 1
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 12:37 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
Medea 2, po co rekurencyjnie? Tak samo włączanie i wyłączanie, odejmujesz przekroje pojedyncze, dodajesz podwójne, odejmujesz potrójne etc. tylko trzeba pamiętać, że już działamy na nieporządkach
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 20:07 
Użytkownik

Posty: 8
Lokalizacja: warszawa
Gouranga napisał(a):
od 1854 odejmij wszystkie gdzie A sprawdza B, będzie ich dokładnie !6 = 265
liczymy przez słabnię bo nie możemy odjąć wszystkich permutacji bo one już są odjęte
odejmij też !6 dla każdego pozostałego warunku, potem dodaj {7 \choose 2}!5 bo dodajesz przekroje dwóch warunków (czyli 2 wybierasz, 5 mieszasz ale już w nieporządkach) itd.

czyli dla przykładu z uczniami powinno wyjść
\sum_{i=0}^{7} (-1)^i {7 \choose i} \cdot !(7-i)


Rozwijając wzór który podałeś na końcu wyszło mi:
1854 - 1855 + 924 - 315 + 70 - 21 + 0 - 1 = 656
Czyli rozumiem, że to jest prawidłowy wynik dla tego zadania?

Wyżej piszesz "odejmij !6 dla każdego warunku", warunków jest sześć, a więc niby powinniśmy odjąć 1590...ale według podanego przez Ciebie na końcu wzoru powinniśmy odjąć 1855 czyli 7  \cdot  !6...to jak to w końcu jest? :) Nie bardzo rozumiem też o co chodzi w "liczeniu przez słabnię"...w którym momencie to robimy?
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 20:57 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
oczywiście zamuliłem z tym wzorem, tam w newtonie na górze powinno być 6 bo tyle mamy pojedynczych warunków, potem będziemy wybierać pary warunków, ich trójki etc.
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 21:16 
Użytkownik

Posty: 8
Lokalizacja: warszawa
Czyli rozumiem, że wzór powinien mieć postać:
\sum_{i=0}^{6} (-1)^i {6 \choose i} \cdot !(7-i)

(w znaku sumy na początku też zamieniłem 7 na 6, bo w przeciwnym razie głupoty wychodziły ;))

Rozwinięcie wzoru daje wynik:
1854 - 1590 + 660 - 180 + 30 - 6 + 0 = 768
Rozumiem, że to jest już prawidłowy wynik ? :)
Góra
Mężczyzna Offline
PostNapisane: 14 gru 2014, o 23:26 
Użytkownik

Posty: 1471
Lokalizacja: Trójmiasto
tak, ten jest prawidłowy, przepraszam jeszcze raz za zamieszanie, coś mi zaćmiło umysł jak pisałem tamten wzór
Góra
Mężczyzna Offline
PostNapisane: 15 gru 2014, o 00:09 
Użytkownik

Posty: 8
Lokalizacja: warszawa
Mam pewne wątpliwości...postanowiłem zrobić takie zadanie dla czterech uczniów (tak jak w przykładzie w wikipedii) z dodatkowymi dwoma warunkami, że A nie może wylosować B, a B wylosować A. Rozpisałem wszystkie kombinacje na kartce i wyszło, że są cztery prawidłowe dla ABCD: CADB, CDBA, DCAB, DCBA.

No to spróbowałem sprawdzić to samo za pomocą analogicznego wzoru, tym razem są dwa dodatkowe warunki, więc zamiast szóstki dwójki, uczniów jest czworo, więc zamiast (7-i) na końcu (4-i):
\sum_{i=0}^{2} (-1)^i {2 \choose i} \cdot !(4-i)

wyszło mi:
9 - 4 + 1 = 6

Co tu jest nie tak?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 17 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 wariacje bez powtórzeń - zadanie 4  aurela123  1
 Kombinacja czy wariacja? - zadanie 2  rNest  2
 Kombinacja a Wariacja bez powtórzeń.  Steeve  2
 Zadania z kmbinacji bez powtórzeń ...  MitS  2
 Kombinacja z ograniczną ilością powtórzeń.  gummis  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl