Wyjaśnienie do dwóch zadań z kombinatoryki

dextereczek · Post autor: **dextereczek** » 12 paź 2010, o 20:57

1. Iloma sposobami mozna ustawic n osób w jednym rzedzie, a iloma
w koło? Czy wynik ulegnie zmianie, jesli osoby tworzace koło zaczna poruszac
sie po okregu tego koła trzymajac sie za rece? (Zakładamy, ze ruch po okregu
odbywa sie zgodnie z ustalonym obiegiem).

Ok jasne, w rzędzie to n!. Jak się połączą w kółko to nic się nie zmieni i dalej mam n!. A już jak się zaczną poruszać po okręgu to ma wyjść jakimś sposobem (n-1)!. Jakim cudem?

2. Mam n ponumerowanych kul i n ponumerowanych pudełek. Ile jest sposobów rozmieszczenia kul tak aby jedno pudełko było puste?
Odpowiedź: 0,5*n*(n-1)*n!
Moje rozumowanie: jedno pudełko ma być puste, więc będzie n-1. Każde z nich może być puste więc n*(n-1), dodatkowo kule można pomieszać więc mam n*(n-1)*n!. Tylko skąd to 0,5 na początku? Wiadomo - w jednym pudełku będą 2 kule, to jakoś na to wpływa?

I jeszcze jedno, w ogóle nie podchodzi mi kombinatoryka, mam z tym ogromny problem. Bardzo ciężko jest mi się nawet tego uczyć, nie wiem czy kolejność jest ważna czy nie, czy coś jest rozróżnialne czy nie (często nie podają tego w zadaniach). Jak nie wiem jaka będzie odpowiedź to prawie na pewno moje myślenie będzie błędne. Znacie jakieś dobre strony/książki z których można się tego nauczyć? W końcu muszę jakoś tą probabilistykę zaliczyć

piasek101 · Post autor: **piasek101** » 12 paź 2010, o 21:08

1. Wg mnie bez cudów.
Okrąg \(\displaystyle{ (n-1)!}\) i mogą łazić ile chcą.

mat_61 · Post autor: **mat_61** » 12 paź 2010, o 21:12

1)
W rzędzie to będzie oczywiście n! - tu nie ma wątpliwości.

W kole zaczyna się problem, bo:

a) jeżeli miejsca są rozróżnialne, czyli jeżeli mamy jakiś układ osób i przesunięcie się każdego np. o jedno miejsce w prawo uznajemy za inny układ, to jest oczywiście także n!

b) jeżeli miejsca są nierozróżnialne (tzn. nie mamy np. żadnego punktu odniesienia, nie mamy numerowanych miejsc, osoby chodzą w kółko w określoną stronę itp.) to każdy "nowy" układ polegający na przesunięciu się wszystkich w daną stronę uważamy za taki sam. Wówczas mamy n takich przesunięć aż układ wróci do stanu początkowego. Skoro wszystkie takie układy uważamy za takie same, to wszystkich możliwości jest:

\(\displaystyle{ \frac{n!}{n} =(n-1)!}\)

dextereczek · Post autor: **dextereczek** » 12 paź 2010, o 21:16

Hmm, no trochę mi rozjaśniłeś. Ale dlatego to się właściwie dzieli? Chodzi mi o n!/n. Nie mogę znaleźć tu logiki
Drugie zadanie chyba zaczynam pomału łapać. Co nie zmienia faktu, że nie mając odpowiedzi nigdy bym w ten sposób tego nie zrobił.

mat_61 · Post autor: **mat_61** » 12 paź 2010, o 21:27

1) jeżeli masz permutacje dla ustawienia w rzędzie np 5 elementów gdzie wszystkich możliwości jest 5!, to ustawienia jak poniżej:

ABCDE
BCDEA
CDEAB
DEABC
EABCD

są różne.

Natomiast jeżeli teraz zapiszesz je w kółku (czyli początek połączysz z końcem) to będzie to takie samo ustawienie. Czyli ustawień w kółku będzie o 5 razy mniej niż ustawień w szeregu.

Albo w drugą stronę:
Jeżeli 5 osób siedzi przy stole to teraz możesz je ustawić w szeregu "rozcinając" kółko w dowolnym z pięciu miejsc. Czyli ustawień w szeregu jest 5 razy więcej niż ustawień w kółku.

dextereczek · Post autor: **dextereczek** » 12 paź 2010, o 21:35

O widzisz, teraz już czaję - dzięki wielkie

mat_61 · Post autor: **mat_61** » 12 paź 2010, o 21:36

2) Tutaj możesz sobie przeprowadzić takie rozumowanie:

Ponieważ dwie kule muszą być razem to można je wybrać spośród n kul na \(\displaystyle{ C^{2}_{n}}\) sposobów. Teraz te kulki związujemy razem i traktujemy jak jeden element. W ten sposób otrzymujemy zbiór (n-1) elementowy. Teraz wybieramy na n możliwych sposobów pudełko które będzie puste. W pozostałych pudełkach na (n-1)! sposobów porządkujemy nasz zbiór. Czyli możliwości jest:

\(\displaystyle{ C^{2}_{n} \cdot n \cdot (n-1)!}\)

dextereczek · Post autor: **dextereczek** » 12 paź 2010, o 21:44

No to już wszystko jasne, jak ktoś zrobi pomału i wyjaśni to rozumiem, gorzej jak mam sam coś wymyślić. Z tym kołem nie wpadłbym na to na pewno.
Jeszcze raz dzięki!

mat_61 · Post autor: **mat_61** » 12 paź 2010, o 21:48

dextereczek pisze:Bardzo ciężko jest mi się nawet tego uczyć, nie wiem czy kolejność jest ważna czy nie, czy coś jest rozróżnialne czy nie (często nie podają tego w zadaniach)

Z tym niestety jest problem. Ponieważ treść zadań z tej dziedziny wymaga interpretacji tekstu "niematematycznego" to często wynikają różne niejednoznaczności i niedopowiedzenia. Oczywiście bardzo dużo zależy od autora zadania i staranności w sformułowaniu jego treści.
Jeżeli np. będzie mowa o okrągłym stole, to w starannie sformułowanym zadaniu pojawi się informacja o nierozróżnialnych (lub rozróżnialnych) miejscach. Jeżeli takiego rozróżnienia nie będzie, to niestety rozwiązanie będzie zależało od interpretacji rozwiązującego. I tak można przytoczyć bardzo wiele przykładów o niejednoznacznych sformułowaniach, np.:

- w trzech losowaniach mamy wylosować dwie kule białe (czy trzecia kula może być biała?)
- rozmieszczamy w pudełkach cukierki (czy cukierki różnią się między sobą?)
- rozmieszczamy osoby w przedziale kolejowym (czy rozróżniamy siedzenia zgodne z kierunkiem jazdy i przeciwne do niego?)
- dwie osoby mają siedzieć razem na wyciągu (dwie konkretne osoby i reszta pojedynczo, czy może dwie dowolne i reszta pojedynczo?)

itd. itd.