Hey,
mam takie zadanko:
Masz 5 szuflad i każda z nich ma 4 przegrody. Na ile sposobów można włożyć do szuflad n różnokolorowych koszulek, tak żeby żadna szuflada nie była pusta.
Moja propozycja:
Koszulki można ułożyć na kupce na n! sposobów. I teraz bierzemy po kolei z tej kupki koszulki i wkładamy do 5 szuflad tak żeby żadna nie była pusta: Jest \(\displaystyle{ \left\{ \frac{n}{5} \right\}}\) sposobów (2 liczba Stirlinga). A więc ogólnie mamy :
\(\displaystyle{ n! \cdot \left\{ \frac{n}{5} \right\}}\) sposobów
Co wy na to?
5 szulad i 4 przegrody - wkładam n różnokolorowych koszulek
-
- Użytkownik
- Posty: 4618
- Rejestracja: 8 lis 2009, o 10:22
- Płeć: Mężczyzna
- Lokalizacja: Racibórz
- Pomógł: 866 razy
5 szulad i 4 przegrody - wkładam n różnokolorowych koszulek
Nie bardzo rozwiązanie pasuje wg mnie do treści zadania.
Liczby Stirlinga II-go rodzaju mówią nam na ile sposobów możemy podzielić n-elementowy zbiór na k niepustych podzbiorów. Jeżeli mamy \(\displaystyle{ \left\{ ^n_5\right\}}\) możliwości podziału n koszulek na \(\displaystyle{ 5}\) zestawów, to po pierwsze te zestawy są nierozróżnialne (zakładam, że szuflady o których mowa w zadaniu są rozróżnialne) a po drugie nie rozumiem co zyskujemy na pomnożeniu ilości tych wariantów przez \(\displaystyle{ n!}\).
Na przykładzie np. dwóch szuflad i czterech koszulek wyglądałoby to tak:
\(\displaystyle{ \left\{ ^4_2\right\}=7}\)
Mamy takie możliwości podziału zbioru koszulek na dwa niepuste podzbiory (koszulki zamiast kolorów mają kolejne numery):
\(\displaystyle{ 1. \left\{ 1\right\} ; \left\{ 2,3,4\right\} \\
2. \left\{ 2\right\} ; \left\{ 1,3,4\right\} \\
3. \left\{ 3\right\} ; \left\{ 1,2,4\right\} \\
4. \left\{ 4\right\} ; \left\{ 1,2,3\right\} \\
5. \left\{ 1,2\right\} ; \left\{ 3,4\right\} \\
6. \left\{ 1,3\right\} ; \left\{ 2,4\right\} \\
7. \left\{ 1,4\right\} ; \left\{ 2,3\right\} \\}\)
Teraz co uzyskujemy uwzględniając permutacje każdego zestawu?
Przykładowo dla zestawu 1. uzyskamy warianty z różną kolejnością elementów zbioru z trzema elementami (co taka różna kolejność miałaby oznaczać?) ale także warianty nr 2, 3 oraz 4 już wcześniej uwzględnione przy liczbie Stirlinga.
Natomiast łatwo zauważyć, że taki sposób rozwiązania nie uwzględnia zarówno rozróżnialności szuflad (np. dla wariantu 1. koszulka o numerze 1. może być w pierwszej lub drugiej szufladzie) jak i ułożenia koszulek w każdej z nich.
Jeżeli mamy np. taki wariant podziału koszulek na szuflady (jeden z siedmiu przy nierozróżnialności szuflad lub jeden z czternastu przy rozróżnialności szuflad)
\(\displaystyle{ A \rightarrow \left\{ 1\right\} ; B \rightarrow \left\{ 2,3,4\right\}}\) to w szufladzie A koszulkę nr 1 możemy rozmieścić ze względu na przegrody na \(\displaystyle{ 4^1=4}\) możliwości, natomiast w szufladzie B koszulki nr 2, 3, 4 możemy rozmieścić ze względu na przegrody na \(\displaystyle{ 4^3=64}\) możliwości.
Widać, że tylko dla tego jednego wariantu podziału koszulek pomiędzy szuflady A i B mamy \(\displaystyle{ 4 \cdot 64=256}\) wariantów ich rozmieszczenia w tych szufladach uwzględniając istnienie przegród.
Podsumowując proponuję rozwiązanie wg schematu:
- podział koszulek na pięć niepustych zestawów.
- przyporządkowanie każdego zestawu do jednej z pięciu szuflad
- przyporządkowanie każdej z koszulek w szufladzie do jednej z czterech przegród.
Liczby Stirlinga II-go rodzaju mówią nam na ile sposobów możemy podzielić n-elementowy zbiór na k niepustych podzbiorów. Jeżeli mamy \(\displaystyle{ \left\{ ^n_5\right\}}\) możliwości podziału n koszulek na \(\displaystyle{ 5}\) zestawów, to po pierwsze te zestawy są nierozróżnialne (zakładam, że szuflady o których mowa w zadaniu są rozróżnialne) a po drugie nie rozumiem co zyskujemy na pomnożeniu ilości tych wariantów przez \(\displaystyle{ n!}\).
Na przykładzie np. dwóch szuflad i czterech koszulek wyglądałoby to tak:
\(\displaystyle{ \left\{ ^4_2\right\}=7}\)
Mamy takie możliwości podziału zbioru koszulek na dwa niepuste podzbiory (koszulki zamiast kolorów mają kolejne numery):
\(\displaystyle{ 1. \left\{ 1\right\} ; \left\{ 2,3,4\right\} \\
2. \left\{ 2\right\} ; \left\{ 1,3,4\right\} \\
3. \left\{ 3\right\} ; \left\{ 1,2,4\right\} \\
4. \left\{ 4\right\} ; \left\{ 1,2,3\right\} \\
5. \left\{ 1,2\right\} ; \left\{ 3,4\right\} \\
6. \left\{ 1,3\right\} ; \left\{ 2,4\right\} \\
7. \left\{ 1,4\right\} ; \left\{ 2,3\right\} \\}\)
Teraz co uzyskujemy uwzględniając permutacje każdego zestawu?
Przykładowo dla zestawu 1. uzyskamy warianty z różną kolejnością elementów zbioru z trzema elementami (co taka różna kolejność miałaby oznaczać?) ale także warianty nr 2, 3 oraz 4 już wcześniej uwzględnione przy liczbie Stirlinga.
Natomiast łatwo zauważyć, że taki sposób rozwiązania nie uwzględnia zarówno rozróżnialności szuflad (np. dla wariantu 1. koszulka o numerze 1. może być w pierwszej lub drugiej szufladzie) jak i ułożenia koszulek w każdej z nich.
Jeżeli mamy np. taki wariant podziału koszulek na szuflady (jeden z siedmiu przy nierozróżnialności szuflad lub jeden z czternastu przy rozróżnialności szuflad)
\(\displaystyle{ A \rightarrow \left\{ 1\right\} ; B \rightarrow \left\{ 2,3,4\right\}}\) to w szufladzie A koszulkę nr 1 możemy rozmieścić ze względu na przegrody na \(\displaystyle{ 4^1=4}\) możliwości, natomiast w szufladzie B koszulki nr 2, 3, 4 możemy rozmieścić ze względu na przegrody na \(\displaystyle{ 4^3=64}\) możliwości.
Widać, że tylko dla tego jednego wariantu podziału koszulek pomiędzy szuflady A i B mamy \(\displaystyle{ 4 \cdot 64=256}\) wariantów ich rozmieszczenia w tych szufladach uwzględniając istnienie przegród.
Podsumowując proponuję rozwiązanie wg schematu:
- podział koszulek na pięć niepustych zestawów.
- przyporządkowanie każdego zestawu do jednej z pięciu szuflad
- przyporządkowanie każdej z koszulek w szufladzie do jednej z czterech przegród.
5 szulad i 4 przegrody - wkładam n różnokolorowych koszulek
Zatem rozwiązanie powinno chyba wyglądać tak:
Żeby żadna szuflada nie była pusta to mamy z 2-liczby stirlinga \(\displaystyle{ \left\{ ^n_5\right\}}\)
po trafieniu do szuflady każda koszulka może trafić to jednej z 4 miejsc(przy podawaniu treści pomyliłem się - mamy 3 przegrody czyli podział "na 4" danej szuflady) a mamy n koszulek zatem \(\displaystyle{ 4^{n}}\)
Czyli ostatecznie otrzymujemy \(\displaystyle{ \left\{ ^n_5\right\} \cdot 4^{n}}\)
Co Ty na to?
Żeby żadna szuflada nie była pusta to mamy z 2-liczby stirlinga \(\displaystyle{ \left\{ ^n_5\right\}}\)
po trafieniu do szuflady każda koszulka może trafić to jednej z 4 miejsc(przy podawaniu treści pomyliłem się - mamy 3 przegrody czyli podział "na 4" danej szuflady) a mamy n koszulek zatem \(\displaystyle{ 4^{n}}\)
Czyli ostatecznie otrzymujemy \(\displaystyle{ \left\{ ^n_5\right\} \cdot 4^{n}}\)
Co Ty na to?
-
- Użytkownik
- Posty: 4618
- Rejestracja: 8 lis 2009, o 10:22
- Płeć: Mężczyzna
- Lokalizacja: Racibórz
- Pomógł: 866 razy
5 szulad i 4 przegrody - wkładam n różnokolorowych koszulek
Czy zakładasz, że szuflady są rozróżnialne?
Jeżeli tak, to po podziale koszulek na 5 zestawów należy każdy z nich przyporządkować do konkretnej szuflady.
Jeżeli nie rozróżniasz szuflad to rozwiązanie jest wg mnie OK.
Jeżeli tak, to po podziale koszulek na 5 zestawów należy każdy z nich przyporządkować do konkretnej szuflady.
Jeżeli nie rozróżniasz szuflad to rozwiązanie jest wg mnie OK.