Na ile sposobów można pomalować ławki

[maciek00]

Witam, mam problem z następującym zadaniem:

W parku jest \(\displaystyle{ 10}\) ławek. Każda z nich zostanie pomalowana na jeden z trzech kolorów. Wiedząc, że każdy kolor zostanie wykorzystany co najmniej raz, oblicz, na ile sposobów można pomalować te ławki.

Mój sposób rozwiązania jest taki:

Każdy kolor musi być wykorzystany przynajmniej raz, więc na pewno są \(\displaystyle{ 3}\) ławki, z których każda jest innego koloru. Ilość sposobów ułożenia tych trzech ławek to: \(\displaystyle{ {10 \choose 3} \cdot 3!}\) (możemy je ustawić na \(\displaystyle{ 3}\) z \(\displaystyle{ 10}\) miejsc, i ponieważ kolejność ma znaczenie, to mnożę przez \(\displaystyle{ 3!}\)). Pozostałe \(\displaystyle{ 7}\) ławek można pomalować na \(\displaystyle{ 3^{7}}\) sposobów. Dlatego wszystkie ławki można pomalować na \(\displaystyle{ {10 \choose 3} \cdot 3! \cdot 3^{7} = 1 574 640}\) sposobów.

Prawidłową odpowiedzią jest \(\displaystyle{ 55\, 980}\). Co jest nie tak w moim rozumowaniu?

[kmarciniak1]

Wielokrotnie liczysz te same ustawienia.
Czy znane są ci liczby stirlinga drugiego rodzaju?

[maciek00]

Liczby stirlinga wykraczają poza moją obecną wiedzę. Które ustawienia liczę wielokrotnie?

[kmarciniak1]

Liczby stirlinga wykraczają poza moją obecną wiedzę. Które ustawienia liczę wielokrotnie?

No na przykład, najpierw wybierzesz pierwszą ławkę na czerwono, drugą na zielono a trzecią na niebiesko i reszta tak sie zdarzy że bedzie niebieska.Według twoich obliczeń jeśli zamiast trzeciej ławki wybierzesz czwartą to jest inne ustawienie a przecież jest to samo.Tak więc takie ustawienie(czerwona,zielona i reszta niebieskich) policzysz aż osiem razy.

Pomyśl o tym tak że dzielisz ławki do trzech szuflad. Wszystkich możliwości jest \(\displaystyle{ 3 ^{10}}\) i odejmij te sytuacje gdy któraś szuflada jest pusta i te gdy dwie szuflady są puste.

[VirtualUser]

Pamiętam te zadanie - było chyba w zbiorze pazdro .
Wracając. kmarciniak udzielił Ci wyjaśnienia, ja za to zostawię inny sposób ze studiów na rozwiązanie tego zadania, bardziej informatyczny.
Niech \(\displaystyle{ [x^q]Q(x)}\) oznacza współczynnik przy \(\displaystyle{ x^q}\) w wielomianie \(\displaystyle{ Q}\).
To co chcesz znaleźć to
\(\displaystyle{ [x^{10}](x+x^2+x^3 + ...)(x+x^2+x^3 + ...)(x+x^2+x^3 + ...)}\)
\(\displaystyle{ = [x^{10}] \left( \frac{x}{1-x} \right)^3}\)
Każdy nawias jest odpowiedzialny za inny kolor. Współczynnik, który wybierasz z danego nawiasu, mówi Tobie jak wiele razy użyłeś tego koloru.

[MrCommando]

Żeby sobie z tym poradzić, nie trzeba znać bardziej zaawansowanych narzędzi typu liczby Stirlinga. Wystarczy najprostsza na świecie zasada włączeń i wyłączeń.

Niech \(\displaystyle{ X}\) będzie zbiorem wszystkich kolorowań \(\displaystyle{ 10}\) ławek na \(\displaystyle{ 3}\) kolory. Możemy każde takie kolorowanie utożsamić z funkcją ze zbioru \(\displaystyle{ [10]}\) w zbiór \(\displaystyle{ [3]}\). Stąd \(\displaystyle{ |X|=3^{10}}\). Oznaczmy przez \(\displaystyle{ A_i}\) zbiór takich kolorowań, w których \(\displaystyle{ i}\)-ty kolor występuje co najmniej raz (dla \(\displaystyle{ i\in[3]}\)). Chcemy obliczyć \(\displaystyle{ |A_1 \cap A_2 \cap A_3|}\). Skorzystamy w tym celu z praw de Morgana i zasady włączeń i wyłączeń. Mamy \(\displaystyle{ |A_i'|=2^{10}}\) dla \(\displaystyle{ i\in[3]}\) oraz \(\displaystyle{ |A_i' \cap A_j'|=1}\) dla \(\displaystyle{ i\neq j}\) oraz \(\displaystyle{ |A_1' \cap A_2' \cap A_3'|=0}\) (zostawiam Ci zastanowienie się dlaczego). Z zasady włączeń i wyłączeń wynika, że
\(\displaystyle{ |A_1' \cup A_2' \cup A_3'|= |A_1'|+|A_2'|+|A_3'|-|A_1' \cap A_2'|-|A_2'\cap A_3'| -|A_3'\cap A_1'|+|A_1'\cap A_2' \cap A_3'|}\).

Teraz:

\(\displaystyle{ |A_1 \cap A_2 \cap A_3|=|X|-|A_1' \cup A_2' \cup A_3'|=3^{10}-\binom{3}{1}2^{10}+\binom{3}{2}\cdot 1-\binom{3}{3}\cdot 0=55980}\), i po sprawie.

Oczywiście pisząc \(\displaystyle{ A'}\) mamy na myśli dopełnienie zbioru \(\displaystyle{ A}\) w przestrzeni \(\displaystyle{ X}\).