Witam
Mam problem jak obliczyć ile jest takich możliwosci pokolorowania n dzieci ( nierozróżnialnych) na k kolorów.
przykładzik dla n = 3 i k = 2:
X X X |
X X | X
X | X X
|X X X
Jak widac sa 4 mozliwosci
Zliczanie ilości rozbić zbioru n-elementowego na max k-pod
-
Sir George
- Użytkownik
- Posty: 1145
- Rejestracja: 27 kwie 2006, o 10:19
- Płeć: Mężczyzna
- Lokalizacja: z Konopii
- Podziękował: 4 razy
- Pomógł: 203 razy
Zliczanie ilości rozbić zbioru n-elementowego na max k-pod
Wynik to \(\displaystyle{ {n+k-1 \choose n}}\)
A dlaczego tak? Pierwszą wskazówkę możesz odczytać ze swojego przykładu: zanim pokolorujemy dzieci wprowadzamy je do k "kolorowych" pokoi (a następnie dzieci z danego pokoju kolorujemy kolorem pokoju )
Ale, ale,... zamiast pokoi możemy użyć boksów, tzn. dużą salę przedzielić k-1 ściankami...
Zapisując schematycznie: każde dziecko to X, a ścianka to I. Pytanie z zadania sprowadza się do pytania o liczbę różnych ciągów, w których występuje n X-ów i k-1 I. A to jest dokładnie tyle, co liczba różnych rozmieszczeń n elementów na n+k-1 miejscach (na pozostałe wstawiamy I).
Jasne?
A dlaczego tak? Pierwszą wskazówkę możesz odczytać ze swojego przykładu: zanim pokolorujemy dzieci wprowadzamy je do k "kolorowych" pokoi (a następnie dzieci z danego pokoju kolorujemy kolorem pokoju )
Ale, ale,... zamiast pokoi możemy użyć boksów, tzn. dużą salę przedzielić k-1 ściankami...
Zapisując schematycznie: każde dziecko to X, a ścianka to I. Pytanie z zadania sprowadza się do pytania o liczbę różnych ciągów, w których występuje n X-ów i k-1 I. A to jest dokładnie tyle, co liczba różnych rozmieszczeń n elementów na n+k-1 miejscach (na pozostałe wstawiamy I).
Jasne?