szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 20 mar 2016, o 17:29 
Użytkownik

Posty: 2
Lokalizacja: Berlin
Witajcie, mam problem z zadaniami tego typu. Mianowicie nie wiem, kiedy konkretnie używać silni a kiedy jedynie mnożyć.
Mam zadanie "Oblicz na ile sposobów można rozmieścić 5 różnych kul w siedmiu szufladach?"
Rozwiązałem to przez silnie, czyli:
{7 \choose 5} =  \frac{7!}{5!(7-5)!}= \frac{5! \cdot 6 \cdot 7}{5! \cdot 2!}= \frac{6 \cdot 7}{2} = \frac{42}{2}  =21

Oraz na zasadzie, że pierwszą kulę można ulokować w jednej z 7 szuflad, drugą w jednej z 6, trzecią w jednej z 5 itd, czyli:
7 \cdot 6 \cdot 5 \cdot 4 \cdot 3=2520

I teraz mi powiedzcie proszę, co robię źle?

Dodatkowo mam dwa zadania:
Losowanie 4 kul ponumerowanych od 1 do 6 spośród 6 kul
czyli 6 \cdot 5 \cdot 4 \cdot 3=360
Na ile sposobów można posadzić 4 drzewa w 6 różnych dołkach
{6 \choose 4} = \frac{6!}{4!(6-4)!} = \frac{4! \cdot 5 \cdot 6}{4! \cdot 2!} = \frac{30}{2}=15
I naprawdę nie rozumiem dlaczego w jednym mnożymy a w drugim liczymy przez silnie. Proszę o pomoc i pozdrawiam :).
Edit: Myśląc logicznie mi bardziej pasuje sposób z mnożeniem, gdyż np. "Na ile sposobów posadzimy 6 osób na 6 krzesłach" wyjdzie: \frac{6!}{6!(6-6)!} = \frac{6!}{6! \cdot 0!} = \frac{6!}{6! \cdot 1} = \frac{1}{1} =1
A jest to niemożliwe, gdyż nie może to być jeden sposób. Osoby te usiąść mogą w kolejności 1 2 3 4 5 6 jak i 2 4 5 3 1 6 itd, czyli bardziej pasuje 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6=750
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 20 mar 2016, o 18:30 
Użytkownik

Posty: 768
Lokalizacja: Warszawa
Problem twój polega na tym iż źle definiujesz sobie powstałe obiekty( licząc kombinacje/wariacje).

Zacznijmy od początku, na początku korzystasz z symbolu newtona. I wszystko jest dobrze tylko zastanów się co chcesz uzyskać korzystając z tego narzędzia.
Nie bez powodu licząc kombinacje jak to zrobiłeś tutaj, każdą z nich traktujemy jako podzbiór zbioru z którego powstają owe kombinacje. Tutaj masz zbiór siedmioelementowy i tworzysz z niego pięcioelementowe podzbiory. I zauważ że przy uwzględnianiu podzbiorów nie ma znaczenia kolejność wyrazów tych podzbiorów bowiem na prostym przykładzie pokażę : \left\{ a,b\right\}= \left\{ b,a\right\}, masz dwa zbiory które składające się z tych samych elementów. I są one równe. Zatem można je potraktować jako jeden zbiór.

Do tego zauważ że jak tworzysz podzbiory pięcioelementowe to jeśli uwzględniać kolejność ich wyrazów to takich podzbiorów byłoby 5!(bo tyle byłoby by permutacji zbioru pięcioelementowego).

I właśnie teraz przejdźmy do twojego drugiego obliczenia .
To co napisałeś też jest prawdziwe i zgodne z intuicją . Zauważ że po podzieleniu tego wyniku przez 5! otrzymasz ilość kombinacji lecz, Ty tutaj potraktowałeś każde rozmieszczenie kul w szufladzie jako unikatowy układ kul . Czyli zmiana kolejności jakiegokolwiek elementu tworzy już nowy układ, pomimo że oba układy powstają z tych samych elementów. Dlatego tutaj(są to wariacje bez powtórzeń) wygodnie jest traktować rozmieszczenia kul jako ciągi. W ciągach liczbowych zmiana kolejności dowolnych elementów tworzy nowy ciąg dlatego każde rozmieszczenie jest uwzględniane w obliczeniach .

I odnośnie polecenia. Masz wyszczególnione że kule są rozróżnialne. Więc jak dla mnie w tym zadaniu rozwiązanie numer dwa jest poprawne.

-- 20 mar 2016, o 17:35 --

Co do ostatniej części , sześć osób można posadzić na sześciu krzesłach na 6! różnych sposobów. Czyli co najmniej jedna osoba zmieni swoje położenie.
(Chociaż w tym zadaniu można by się pokusić o głębszą analizę bowiem można znaleźć tu pewien istotny haczyk)

Natomiast zauważ że każde rozmieszczenie powstaje z tych samych osób. Zatem można by powiedzieć że powstały zbiór sześcioelementowy ze zbioru sześciu osób jest zawsze taki sam i jest tylko jeden taki zbiór :)
Góra
Mężczyzna Offline
PostNapisane: 20 mar 2016, o 20:48 
Użytkownik

Posty: 2
Lokalizacja: Berlin
Zaczynam rozumieć różnicę, dzięki!
Góra
Mężczyzna Offline
PostNapisane: 24 mar 2016, o 01:09 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
Ad 1.
Rozmieszczanie elementów w szufladach, czy w pudełkach to dosyć popularne zadanie, natomiast jedno może się różnić od drugiego. Najczęściej chodzi o umieszczenie k identycznych przedmiotów w n rozróżnialnych pudełkach (albo n w k, zależy od oznaczeń, później o tym wspomnę) i teraz ważne jest, czy nie podane są jakieś dodatkowe informacje, bo z twojego zapisu
Augerz napisał(a):
Oraz na zasadzie, że pierwszą kulę można ulokować w jednej z 7 szuflad, drugą w jednej z 6, trzecią w jednej z 5 itd, czyli:
7 \cdot 6 \cdot 5 \cdot 4 \cdot 3=2520
wynika, że w każdym pudełku może być najwyżej jedna kula i mogą się zdarzyć puste pudełka. Przechodząc do twojego głównego problemu:
Augerz napisał(a):
Mianowicie nie wiem, kiedy konkretnie używać silni a kiedy jedynie mnożyć.
nie chodzi o to, że chce się przyczepić, bo najważniejsze jest żebyś zrozumiał, ale operacja silni na liczbie naturalnej jest mnożeniem, bo przecież \forall n\in \mathbb{N}\quad n!=\prod_{k=1}^{n} k. Chodzi o to, że te operacje są bardzo elastyczne, zaraz pokaże ci, o co mi chodzi. Twoja metoda polega na tym, że najpierw wybierasz jedno z siedmiu pudełek i umieszczasz w nim kule, możesz to zrobić na C_7^1={7 \choose 1} sposobów (uwaga, poza Europą mogliby napisać C_1^7). Potem wybierasz jedno z 6, itd aż skończą ci się kulki albo pudełka. W tym przypadku wszystkich możliwości masz {7 \choose 1}\cdot {6 \choose 1}\cdot {5 \choose 1}\cdot {4 \choose 1}\cdot {3 \choose 1}=7\cdot 6\cdot 5\cdot 4\cdot 3= \frac{7!}{2}. A widząc 7! można by się zastanowić, czy gdzieś nie pojawiają się jakieś permutacje, lub wariacje bez powtórzeń 7-elementowe ze zbioru 7-elementowego. Tak więc czasami do zadania można podejść na kilka sposobów.
Augerz napisał(a):
Rozwiązałem to przez silnie, czyli
{7 \choose 5} = \frac{7!}{5!(7-5)!}= \frac{5! \cdot 6 \cdot 7}{5! \cdot 2!}= \frac{6 \cdot 7}{2} = \frac{42}{2} =21
Tutaj chyba widzę do czego dążyłeś, niestety zapis nie jest szczególnie blisko rozwiązania problemu. Może on najwyżej przedstawiać ilość możliwych sposobów wybrania 5 szuflad z 7. Ogólnie jeżeli w zadaniu jest tylko powiedziane żeby umieścić k identycznych przedmiotów w n rozróżnialnych pudełkach, to mamy do czynienia z kombinacjami z powtórzeniami, których ilość wyraża się wzorem \overline{C}^n_k={{n+k-1}\choose{n}}={{n+k-1}\choose{k-1}}
(i tutaj widać dlaczego często oznacza się n-przedmioty, k-pudełka, bo wtedy mamy \overline{C}^k_n={{k+n-1}\choose{k}}={{k+n-1}\choose{n-1}} i zapis wygląda analogicznie do kimbinacji bez powtórzeń k-elementowych ze zbioru n-elementowego, zamiast n-elementowych z k-elementowego i ludziom łatwiej to przyswoić zapewne bo częściej się to pojawia w takiej formie i wpaja im się, że w definicji tam wszędzie jest k \le n, a w przypadku kombinacji z powtórzeniami nie ma to znaczenia).
Wracając do zadania, jeżeli nie podane zostały żadne dodatkowe warunki, to poprawnym rozwiązaniem byłoby opisanie jakiegoś zbioru szukanych ułożeń i policzenie jego mocy.
A=\{(S_i=\{k_1, k_2, k_3, k_4, k_5\})|(k_j \in S_i),\  gdzie\ (k_j \in S_i => k_j=k)\}, przy czym i=1,...,7 oraz j=1,...,5.
Czyli |A|=\overline{C}^5_7={{5+7-1}\choose{5}}=330.

Ad 2.
Augerz napisał(a):
Losowanie 4 kul ponumerowanych od 1 do 6 spośród 6 kul
Twoje obliczenia prezentują losowanie 4 razy po jednej kuli bez zwracania i znowu jest to wybranie 1 z 6 kul, potem 1 z 5 itd. czyli {6 \choose 1}\cdot {5 \choose 1}\cdot {4 \choose 1}\cdot {3 \choose 1}=6\cdot 5\cdot 4\cdot 3. Natomiast jeżeli nie jest powiedziane, że po jednej kuli mamy losować, to ja bym losował od razu 4, a ilość możliwości policzymy wtedy jako {6 \choose 4}.

Ad 3.
Jak wyżej, kombinacje z powtórzeniami. Ty wybrałes 4 z sześciu dołków i tyle. Gdybyś np. chciał wybrać 4 z 6 dołków, a potem dowolnie w nich posadzić drzewa to możliwości byłoby {6 \choose 4} \cdot {4 \choose 4}=15. Jeżeli chciałbyś np. wybrać 4 dołki i w każdym posadzić jedno z drzewo, to możliwości jest wtedy {6 \choose 1} \cdot {4 \choose 1}+{5 \choose 1} \cdot {3 \choose 1}+{4 \choose 1} \cdot {2 \choose 1}+{3 \choose 1} \cdot {1 \choose 1}=50.

Ad Edit.
Tutaj oczywiście pierwsze rozumowanie jest błędne. Polega ono na wybraniu 6 osób z 6 i na tym koniec. Gdybyś chciał liczyć kombinacje w tym zadaniu, to liczy się je dla konkretnego ułożenia krzeseł, tzn 1 z 6 osób na pierwszym krześle, 1 z 5 na drugim itd. czyli {6 \choose 1} \cdot{5 \choose 1}... (czyli praktycznie rzecz biorąc wariacje, zobacz niżej).
Augerz napisał(a):
Na ile sposobów posadzimy 6 osób na 6 krzesłach"
Czyli na ile sposobów możemy ułożyć 6 osób, zadanie analogiczne do ułożenia np. 6 monet albo czegokolwiek. Oczywiście możemy to policzyć jako wariacje bez powtórzeń 6-elementowe ze zbioru 6-elementowego, czyli V^6_6=6!, albo po prostu dowolnie permutować te osoby na P_6=6! sposobów.

Jeżeli nie bardzo rozumiesz kombinacje z powtórzeniami i chciałbyś to sobie przyswoić to odsyłam do angielskiej wikipedii (combinations with repetition).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kombinatoryka losowanie kart  R?kawiczka  2
 losowanie ze zwracaniem, prosta  karka92  1
 losowanie z szuflady  zyjseprosto  3
 Losowanie dwóch cyfr z 5-elementowego zbioru.  adam882  2
 Losowanie numeru  kasia00  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl