szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Kulki i kosze
PostNapisane: 5 mar 2016, o 21:38 
Użytkownik

Posty: 1
Lokalizacja: tba
Na ile sposobów można umieścić n nierozróżnialnych kulek w k koszach, tak aby dokładnie jeden kosz pozostał pusty?

Moje rozwiązanie:
1. Wybieram kosz, który będzie pusty. Mogę to zrobić na k sposobów.
2. Biorę k-1 kulek i wrzucam po jednej do koszów, które mają być niepuste. Kulki są nierozróżnialne, więc nie obchodzi mnie, którą kulkę wrzucę do którego kosza.
3. Pozostaje mi n-(k-1) kulek. Każdą z nich mogę wrzucić do dowolnego z k-1 koszów, bo już zagwarantowałem ich niepustość - liczba sposobów (k-1)^{n-(k-1)}.

Wynik, który otrzymuję ( k \cdot (k-1)^{n-(k-1)} ) jest jednak niepoprawny. Gdzie w tym rozumowaniu tkwi błąd?
Góra
Mężczyzna Offline
 Tytuł: Kulki i kosze
PostNapisane: 5 mar 2016, o 23:27 
Użytkownik
Avatar użytkownika

Posty: 1472
Lokalizacja: Trójmiasto
przy k nierozróżnialnych kul do n rozróżnialnych koszy można użyć metody separatorów
w takim przypadku, dla np. 5 kul do 4 koszy mamy 5 kul i 3 separatory (zawsze o 1 mniej niż koszy)
możemy rozłożyć je tak:
o|o|o|oo - do ostatniego koszta dwie
|oo|oo|o - pierwszy pusty, 2 i 3 po dwie itd.

wzór na to:
\left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}

w twoim przypadku najpierw na n sposobów wybieramy pusty kosz
potem do n-1 koszy wrzucamy po jednej kuli, zostaje nam do rozmieszczenia k-n+1 kul, potem te k-n+1 kul rozdzielamy sposobem separatorów na n-1 koszy:
\left\langle \begin{array}{c}k-n+1\\n-1\end{array}\right\rangle = {k-1 \choose k-n+1}

stąd mamy ostateczny wynik:
n {k-1 \choose k-n+1}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 rozróznialen kulki w rozróżnialnych pojemnikach  voncuver  10
 kulki - zadanko  Anonymous  1
 Kulki w pudełkach - zadanie 2  MgielkaCuba  1
 Kulki w pudełkach - zadanie 6  Dilectus  7
 Kulki w pudełkach  sebek2301  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl