szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 kwi 2016, o 11:18 
Użytkownik

Posty: 104
Znajdź liczbę wszystkich rozmieszczeń 4 diamentów w 10 różnych szkatułkach, jeśli

a) diamenty są rozróżnialne i w żadnej szkatułce nie może być więcej niż jeden diament
b) diamenty są nierozróżnialne i w każdej szkatułce może być dowolna ilość diamentów

Co do a), moim zdaniem odpowiedzią będzie po prostu
10 \cdot 9 \cdot 8 \cdot 7

W b) natomiast nie rozumiem zbytnio jak wpływa na rozwiązanie rozróżnialność diamentów oraz dowolność ilości w danej szufladce? Czy mógłby mi ktoś nakreślić z czysto teoretycznej strony, jak te dwie sprawy zmieniają mi rozwiązanie?

Z góry dziękuję :)
Góra
Mężczyzna Offline
PostNapisane: 26 kwi 2016, o 19:59 
Użytkownik
Avatar użytkownika

Posty: 58
Lokalizacja: Kraków
Podpunkt a) się zgadza, użyłeś wariacji bez powtórzeń, równie dobrze można to policzyć na przykład jako {10 \choose 4}\cdot 4!.

W podpunkcie b) mamy do czynienia z typową sytuacją umieszczania n nierozróżnialnych przedmiotów w k rozróżnialnych pudełkach. Trochę mówi nam o tym zasada szufladkowa Dirichleta. Ogólnie zasada takiego rozmieszczania brzmi, że jeżeli mamy przedmioty i pudełka jak wyżej, to sposobów rozmieszczenia jest
{n+k-1 \choose k-1}={n+k-1 \choose n}.
Skąd to się bierze? Sytuacja jest analogiczna do liczenia kombinacji z powtórzeniami n-elementowych ze zbioru k-elementowego. Liczbę takich kombinacji u nas zapisujemy symbolem \overline C_k^n i liczymy następująco:
\overline C_k^n={n+k-1 \choose n}.
Równie dobrze mogliśmy oznaczyć pudełka przez n, a przedmioty przez k, k i n we wzorze by się zamieniło i wyszło by na to samo, tylko trzeba być konsekwentnym. Ogólnie warto pamiętać też, że kiedy liczymy kombinacje bez powtórzeń k-elementowe ze zbioru n-elementowego to musi być spełniony warunek k \le n. Przy kombinacjach z powtórzeniami natomiast - nie musi.

Teraz bardziej rozjaśnimy wzór. Weźmy na warsztat nasze 4 diamenty. Chcemy je w dowolny sposób rozmieścić w 10 szkatułkach. No więc jak utworzymy już te kombinacje z powtórzeniami to mamy problem, bo przecież elementy w zbiorze się nie powtarzają. mamy na to sposób - każdy taki zbiór zamieniamy bijektywnie, czyli jednoznacznie, na ciąg zer i jedynek, co będzie dobrze widać na przykładzie. Niech zera oznaczają diamenty, a jedynki szkatułki. Tworzymy np. ciąg 0010101111111. Ilość zer przed każdą jedynką oznacza ilość elementów w szkatułce o numerze opdowiadającym kolejności jedynek. To znaczy, że u nas w pierwszej szkatułce (pierwsza jedynka od lewej) umieścimy 2 diamenty (2 zera przed jedynką), w drugiej i trzeciej po jednym diamencie, a w pozostałych zero. Żeby przedstawić sytuację jasno, napiszę kropki wszędzie tam, gdzie mogą pojawić się zera: .1.1.1.1.1.1.1.1.1. Widzimy, że aby ustawić 0 na dziesięciu różnych miejscach wystarczy nam 10-1=9 jedynek. Stąd k-1 we wzorze. Więc mamy ciąg k-1 jedynek (tutaj 9\ :\ 111111111). Wybieramy póki co k-1 miejsc na jedynki, spośród k-1 możliwych miejsc na te jedynki. Ale mamy jeszcze dodatkowe n miejsc na n zer (u nas 4 miejsca na 4 zera). Tak więc wystarczy wybrać teraz nasze k-1 miejsc spośród nie k-1, a k-1+n miejsc możliwych i wynik gotowy.

Więcej na temat kombinacji w powtórzeniami możesz poczytać na wiki [Combination - Number of combinations with repetition]
Tutaj zapis gwiazdek i kresek (analogia do zer i jedynek) - en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba trójkątów jakie możemy utworzyć z przekątnych n-kąta  Transpluton  2
 Wariacja bez powtórzeń - liczba 5-cyfrowa większa od 60000  faust1002  2
 Liczba chromatyczna - zadanie 6  darex99  1
 Zbadać czy czterdziesty wyraz dwumianu jest liczbą naturalną  margor  3
 liczba słów dlugości n  Demon  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl