kobinatoryka, klatki

[prawyakapit]

Mamy \(\displaystyle{ 13}\) różnych drapieżników i chcemy umieścić część z nich (być może wszystkie) w klatkach.
Na ile sposobów możemy to zrobić, jeżeli
a) klatka jest jedna i nie może być pusta?
b) klatki są dwie (różne) i żadna nie może być pusta?


co do a) na początku myślałam że będą to wariacje bez powtórzeń ale wychodzi że mozliwości jest \(\displaystyle{ 13}\) co jest nieprawdą.

[Huub900]

a) Musimy wybrać niepusty podzbiór drapieżników, które wylądują w klatce. Zbiór 13 elementowy ma
\(\displaystyle{ 2^{13}-1}\) niepustych podzbiorów.

Można też na sprawę spojrzeć trochę inaczej (co ułatwi rozwiązanie punktu b): każdemu drapieżnikowi przyczepiamy etykietkę: 1 - do klatki, 0 - na wolności. Mamy więc 13 elementowe ciągi zerojedynkowe. Ciągów takich jest \(\displaystyle{ 2^{13}}\), w tym jeden - składający się z samych zer - który nie spełnia założenia.

b) Teraz mamy 13 elementowe ciągi składające się z 1 (pierwsza klatka), 2 (druga klatka), 0 (na wolności). Takich ciągów jest \(\displaystyle{ 3^{13}}\), ale od tej liczby trzeba odjąć te, które składają się tylko 1 i 0 oraz te, które składają się z 2 i 0. Trzeba będzie skorzystać z zasady włączania-wyłączania:

\(\displaystyle{ 3^{13} - 2 \cdot 2^{13} + 1^{13}}\)

[prawyakapit]

co do punktu a teoretycznie rozumiem twoje rozumowanie ale zastanawiam się co jest zlegio w moim rozwiązaniu, ja rozpatrzyłam 13 przypadków tj.
I-do klatki trafia 1 drapieznik
II- 2 drapieżniki
III- 3 drapieżniki
.
.
.
.
.
.
XIII-13 drapieżników

i tworzyłam kombinacje \(\displaystyle{ I- {13\choose\\1} II- {13\choose\\2}.................XIII {13\choose\\3}}\)

[Huub900]

W Twoim rozwiązaniu nie ma absolutnie nic złego:

\(\displaystyle{ \sum_{k=1}^{n}{n\choose k}=2^n-1}\)

[prawyakapit]

wyniki się jednak nie zgadzają

[Huub900]

Co się nie zgadza?

\(\displaystyle{ {13\choose 1}+{13\choose 2} +\ldots +{13\choose 13}=2^{13}-1}\)

Wychodzi tyle samo co u mnie.

[prawyakapit]

rzeczywiście musiałam się gdzies pomylić w rachunkach wcześniej ; )

-- 1 kwi 2012, o 17:31 --

a jeszcze co do podpunktu b:

skąd ta \(\displaystyle{ 1^{13} ?}\)

[Huub900]

Z zasady włączania wyłączania. Mamy 13-elementowe ciągi, składające się z 0, 1, 2. Takich ciągów jest \(\displaystyle{ 3^{13}}\). Ciągi składające się z 0 i 1 lub 0 i 2 nie spełniają założenia, bo wtedy jedna z klatek jest pusta. Jednych i drugich jest \(\displaystyle{ 2^{13}}\). Ale i wśród jednych i drugich jest ciąg składający się z samych zer. On też nie spełnia założenia, ale odjęliśmy go dwa razy więc trzeba raz z powrotem dodać.-- 2 kwi 2012, o 13:25 --Można to też zamodelować podziałem zbioru na bloki. Mamy dwa przypadki:
1. Wszystkie drapieżniki trafią do klatek -- wtedy dzielimy zbiór drapieżników na dwa bloki (dodatkowo musimy uwzględnić permutowanie tych bloków -- zamiana klatek)
2. Część zostaje na wolności -- dzielimy zbiór na trzy bloki (również uwzględniamy permutacje)

\(\displaystyle{ 2!\cdot\begin{Bmatrix}13 \\ 2\end{Bmatrix} + 3!\cdot\begin{Bmatrix} 13 \\ 3 \end{Bmatrix}}\)

Wynik wychodzi taki sam jak poprzednio.

[prawyakapit]

14. Na ile sposobów mo»na wybrać niepustą grupę spośród 25 ludzi?


czy to zadanie jest analogiczne to jest będzie

\(\displaystyle{ 25+ {25\choose 2}+ {25\choose 3}+.......+{25 \choose 4} +1}\) ??

[Huub900]

Można i tak, ale lepiej wiedzieć, że zbiór n-elementowy ma \(\displaystyle{ 2^n}\) podzbiorów, w tym jeden pusty.

[prawyakapit]

dzięki, właśnie tak zastanawiałam się czy mogę to tez policzyć tak jak ty poprzednio ale nie znałam tej zależności ; )