malowanie ścian

[zaklopotany93]

Malarz ma nałożyć na każdą z \(\displaystyle{ m}\) różnych ścian \(\displaystyle{ n}\) różnych ponumerowanych farb przy czym każdą ścianę musi malować w następujący sposób: najpierw nakłada na nią pierwszą farbę, potem drugą, potem trzecią itd. aż do \(\displaystyle{ n}\)-tej farby i w dowolnym momencie może odstąpić od malowania danej ściany (po nałożeniu na nią farby/farb) i zacząć malować jakąkolwiek inną z pozostałych ścian (o ile ta nie została już pomalowana wszystkimi \(\displaystyle{ n}\) farbami). Na ile sposobów malarz może wykonać powierzone mu zadanie?

[mat_61]

Wskazówka:

Oznaczmy sobie kolejne malowania, czyli zestaw numer ściany + numer koloru jako \(\displaystyle{ x_{m} - y_{n}}\).

Wszystkich ciągów takich zestawów mamy:

\(\displaystyle{ \left(m \cdot n) !}\)

Teraz zastanów się ile razy tych zestawów jest za dużo gdy kolejność kolorów dla każdej ściany jest ustalona?

[zaklopotany93]

Prawdę mówiąc na tym mój problem polega, że nie wiem jak to zliczyć.

[mat_61]

Zgodnie z treścią zadania każdą ze ścian malujemy na jeden sposób.
Oznacza to, że dla każdej z możliwości spośród \(\displaystyle{ \left( mn\right) !}\) nie traktujemy jako różnych tych sekwencji które różnią się tylko kolejnością elementów \(\displaystyle{ y_{n}}\) dla każdej ze ścian.

Różnych sekwencji różniących się tylko kolejnością elementów \(\displaystyle{ y_{n}}\) dla jednej ściany mamy \(\displaystyle{ n!}\), a ponieważ ścian mamy \(\displaystyle{ m}\) , to wszystkich różnych sposobów malowania mamy:

\(\displaystyle{ \frac{\left( m \cdot n\right)! }{m \cdot n!}}\)

Wcześniejszą wskazówką chciałem Cię naprowadzić na permutacje z powtórzeniami.

Zastanów się jak może przebiegać takie malowanie. Po prostu wybieramy kolejne ściany w dowolnej kolejności (po wyborze ściany nie mamy wybory jaką farbą ją malujemy) w taki sposób, że każdą z nich musimy wybrać \(\displaystyle{ n}\) razy. Układamy więc ciąg z elementów takiego zbioru:

\(\displaystyle{ \left\{ \underbrace{x_{1};x_{1};...x_{1}}_{n \ razy};\underbrace{x_{2};x_{2};...x_{2}}_{n \ razy};...;\underbrace{x_{m};x_{m};...x_{m}}_{n \ razy};\right\}}\)

Jak widzisz są to typowe permutacje z powtórzeniami. Przykładowo taki ciąg:

\(\displaystyle{ \left( x_{3};x_{2};x_{8};x_{1};x_{1};x_{4};...x_{7}\right)}\)

oznacza, że malujemy kolejno ściany numer \(\displaystyle{ 3; 2; 8; 1; 1; 4;...;7}\) odpowiednimi kolorami wynikającymi z kolejności malowania.

[zaklopotany93]

Różnych sekwencji różniących się tylko kolejnością elementów \(\displaystyle{ y_{n}}\) dla jednej ściany mamy \(\displaystyle{ n!}\), a ponieważ ścian mamy \(\displaystyle{ m}\) , to wszystkich różnych sposobów malowania mamy:

\(\displaystyle{ \frac{\left( m \cdot n\right)! }{m \cdot n!}}\)

No ale jak mamy \(\displaystyle{ 2}\) różne ściany \(\displaystyle{ A_1}\) \(\displaystyle{ A_2}\) i jedną farbę, to możemy na dwa sposoby je pomalować - jeden sposób to taki, że najpierw malujemy ścianę \(\displaystyle{ A_1}\) nakładając na nią tę jedną farbę, a potem malujemy ścianę \(\displaystyle{ A_2}\) tą samą farbą. Podobnie możemy zacząć od malowania ściany \(\displaystyle{ A_2}\) tą farbą, a potem pomalować ścianę \(\displaystyle{ A_1}\) tą samą farbą, czyli ogółem mamy \(\displaystyle{ 2}\) sposoby malowania, ale \(\displaystyle{ 2 \neq \frac{(2 \cdot 1)!}{2 \cdot 1!}=1}\)

PS: Myślałem nad tym trochę - nie powinno być przypadkiem \(\displaystyle{ \frac{(mn)!}{(n!)^m}}\)?

[mat_61]

Przepraszam za pomyłkę. Oczywiście powinno być:

\(\displaystyle{ \frac{(mn)!}{(n!)^m}}\)

Permutacje z powtórzeniami:

Jeżeli mamy \(\displaystyle{ k}\) elementów: \(\displaystyle{ a_{1}; a_{2}; ... ; a_{k}}\) i każdy z nich powtarza się odpowiednio \(\displaystyle{ n_{1}; n_{2}; ... ; n_{k}}\) razy to liczba permutacji n-elementowych gdzie \(\displaystyle{ n=n_{1}+n_{2}+... + n_{k}}\) wynosi:

\(\displaystyle{ \frac{n!}{n_{1}! \cdot n_{2}! \cdot ... \cdot n_{k}!}}\)

Jeżeli \(\displaystyle{ n_{1}=n_{2}=...=n_{k}=p}\) to oczywiście liczba permutacji n-elementowych gdzie \(\displaystyle{ n=p \cdot k}\) wynosi:

\(\displaystyle{ \frac{n!}{\left( p!\right)^k }}\)

[zaklopotany93]

Dziękuję bardzo, pomogła mi ta informacja o tych permutacjach, dopiero to zaczynam więc nie jestem w tym biegły choć powinienem na to wpaść . Oczywiście daję pomógł.