Permutacja z powtórzeniami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
jqakubx
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 23 paź 2019, o 19:14
Płeć: Mężczyzna
wiek: 20
Podziękował: 2 razy

Permutacja z powtórzeniami

Post autor: jqakubx »

Witam, mam problem z zadaniem.
Mamy a kobiet i b mężczyzn. Na ile sposobów można ich ustawić w rzędzie aby dwóch mężczyzn nie stało obok siebie?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Permutacja z powtórzeniami

Post autor: Janusz Tracz »

Jest \(\displaystyle{ a-1}\) miejsc pomiędzy kobietami \(\displaystyle{ +2}\) na początku i końcu zatem można wybrać \(\displaystyle{ b}\) miejsc dla \(\displaystyle{ b}\) chłopaków na \(\displaystyle{ {a+1 \choose b} }\) sposobów a potem można przestawiać na \(\displaystyle{ a!b!}\) sposobów zatem wszystkich ustawiań jest \(\displaystyle{ {a+1 \choose b}a!b! }\)
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Permutacja z powtórzeniami

Post autor: kerajs »

Janusz Tracz pisze: 23 paź 2019, o 19:49 Jest \(\displaystyle{ a-1}\) miejsc pomiędzy kobietami \(\displaystyle{ +2}\) na początku i końcu zatem można wybrać \(\displaystyle{ b}\) miejsc dla \(\displaystyle{ b}\) chłopaków
Tak, o ile \(\displaystyle{ a>b }\).
Należy także rozważyć sytuacje:
1) \(\displaystyle{ a=b}\)
2) \(\displaystyle{ a=b-1}\)
3) \(\displaystyle{ a<b-1}\)
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Permutacja z powtórzeniami

Post autor: Janusz Tracz »

Gdy \(\displaystyle{ a=b}\) to zapełniamy \(\displaystyle{ a-1}\) miejsc \(\displaystyle{ b-1}\) chłopakami a ostatniego można dać na początek lub koniec czyli \(\displaystyle{ 2}\) opcje dodatkowe więc wszystkich jest \(\displaystyle{ 2a!b!}\).
jqakubx
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 23 paź 2019, o 19:14
Płeć: Mężczyzna
wiek: 20
Podziękował: 2 razy

Re: Permutacja z powtórzeniami

Post autor: jqakubx »

Hmm wydaje mi się, że zrozumiałem, tylko czy na pewno konieczne jest mnożenie na końcu razy a! i b!?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: Permutacja z powtórzeniami

Post autor: Janusz Tracz »

Jeśli uznajemy każdą z osób za rozróżnialną (a tak zakładam, że nie ma bliźniaków) to mnożenie przez \(\displaystyle{ a!}\) oraz \(\displaystyle{ b!}\) daje nam liczbę wszystkich permutacji w takich, że na ustalonych miejscach stoją już chłopaki i dziewczyny ale mogą się podmieniać (permutacje zliczają te podmianki).
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Permutacja z powtórzeniami

Post autor: kerajs »

Janusz Tracz pisze: 23 paź 2019, o 20:26 Gdy \(\displaystyle{ a=b}\) to zapełniamy \(\displaystyle{ a-1}\) miejsc \(\displaystyle{ b-1}\) chłopakami a ostatniego można dać na początek lub koniec czyli \(\displaystyle{ 2}\) opcje dodatkowe więc wszystkich jest \(\displaystyle{ 2a!b!}\).
To niestety (i poniekąd jest to także moja wina) nie jest prawidłowa odpowiedź.
janusz47
Użytkownik
Użytkownik
Posty: 7911
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Permutacja z powtórzeniami

Post autor: janusz47 »

Jeżeli mężczyźni nie mogą stać koło siebie, to znaczy że mężczyźni i kobiety muszą ustawić się w szeregu na przemian.

Jeżeli kobiet jest więcej od mężczyzn \(\displaystyle{ a > b,}\) to jako pierwsza w rzędzie musi stać kobieta.

\(\displaystyle{ K M K M ... M K }\)

Skoro miejsca dla kobiet są już ustalone, wystarczy je ustawić na \(\displaystyle{ a! }\) sposobów.

Dołączamy do tego rzędu kobiet - na ustalonych miejscach mężczyzn na \(\displaystyle{ b! }\) sposobów.

Wszystkich możliwych sposobów ustawień kobiet i mężczyzn w rzędzie jest \(\displaystyle{ a! \cdot b!.}\)

Stąd prawdopodobieństwo zdarzenia \(\displaystyle{ A }\) " dwóch mężczyzn nie stoi obok siebie", wynosi

\(\displaystyle{ P(A) = \frac{a!\cdot b!}{(a+b)!} \ \ (1) }\)

W przypadku, gdy mężczyzn jest więcej niż kobiet \(\displaystyle{ b > a, }\) to jako pierwszy w rzędzie musi stać mężczyzna

\(\displaystyle{ M K M K ... KM }\)

Podobnie rozumując- otrzymujemy ten sam wzór \(\displaystyle{ (1) }\) na prawdopodobieństwo zdarzenia \(\displaystyle{ A. }\)

W przypadku, gdy liczba kobiet i mężczyzn jest taka sama \(\displaystyle{ a = b, }\) wtedy na pierwszym miejscu może stać zarówno kobieta jak i mężczyzna.

Liczba wszystkich możliwych ustawień kobiet i mężczyzn tak, aby żaden mężczyzna i żadna kobieta nie stali koło siebie wynosi \(\displaystyle{ 2a!\cdot b! }\)

Prawdopodobieństwo zdarzenia \(\displaystyle{ A }\) w tym przypadku jest dwukrotnie większe i wynosi

\(\displaystyle{ P(A) = \frac{2\cdot a!\cdot b!}{(a + b )!}. }\)

Liczby wszystkich możliwych ustawień kobiet i mężczyzn , które są treścią zadania znajdują się w licznikach prawdopodobieństwa \(\displaystyle{ P(A). }\)
a4karo
Użytkownik
Użytkownik
Posty: 22174
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Permutacja z powtórzeniami

Post autor: a4karo »

janusz47 pisze: 25 paź 2019, o 10:45 Jeżeli mężczyźni nie mogą stać koło siebie, to znaczy że mężczyźni i kobiety muszą ustawić się w szeregu na przemian.

Jeżeli kobiet jest więcej od mężczyzn \(\displaystyle{ a > b,}\) to jako pierwsza w rzędzie musi stać kobieta.

\(\displaystyle{ K M K M ... M K }\)

Chyba nie zrozumiałeś treści zadania. Ustawienie
MKKKKKKKM jest ok
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Permutacja z powtórzeniami

Post autor: arek1357 »

\(\displaystyle{ M \le K+1}\)

Dodano po 15 minutach 10 sekundach:
\(\displaystyle{ a}\)- kobiety, \(\displaystyle{ b}\)- mężczyźni

Wsk: Najpierw ustawiamy kobiety , a między przegródkami mężczyzn , przegródek jest \(\displaystyle{ a+1}\) (w jednej przegródce tylko jeden facet)

najpierw wybieramy \(\displaystyle{ b}\) przegródek bo do nich dajemy gości... na sposobów:

\(\displaystyle{ {a+1 \choose b} }\) - tyle możliwości wyboru przegródek... w których siedzą faceci...

Po ustawieniu kobiet i zaaplikowaniu mężczyzn do przegródek wcześniej wybranych mamy już tylko permutacje...

Zresztą Janusz Tracz już to zrobił nawet nie zauważyłem...
Ostatnio zmieniony 25 paź 2019, o 13:46 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: mężczyźni.
janusz47
Użytkownik
Użytkownik
Posty: 7911
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Permutacja z powtórzeniami

Post autor: janusz47 »

Słuszna uwaga, moje rozumowanie jest dla przypadku, gdy żaden mężczyzna i żadna kobieta nie mogą stać koło siebie.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Permutacja z powtórzeniami

Post autor: Dasio11 »

kerajs pisze: 23 paź 2019, o 20:12Tak, o ile \(\displaystyle{ a>b }\).
Należy także rozważyć sytuacje:
1) \(\displaystyle{ a=b}\)
2) \(\displaystyle{ a=b-1}\)
3) \(\displaystyle{ a<b-1}\)
Rozwiązanie Janusza Tracza działa bez założenia, że \(\displaystyle{ a > b}\), a jeśli twierdzisz inaczej, to wskaż błąd.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Permutacja z powtórzeniami

Post autor: kerajs »

Dasio11 pisze: 25 paź 2019, o 19:42 Rozwiązanie Janusza Tracza działa bez założenia, że \(\displaystyle{ a > b}\), a jeśli twierdzisz inaczej, to wskaż błąd.
Proszę bardzo: \(\displaystyle{ a=2, b \ge 4}\)
Nie negowałem poprawności rozwiązania, lecz pominięcie założeń przy których to rozwiązanie zachodzi. A zachodzi ono dla \(\displaystyle{ a \ge b-1}\). Dla \(\displaystyle{ a < b-1}\) nie można ustawić w rzędzie osób tak, aby dwóch mężczyzn nie stało obok siebie, więc tu jest zero sposobów.

Przyznaję, rozpatrywanie przypadków 1) i 2) jest zbędne, tu wzorek Janusza47 działa także, lecz jego odpowiedź na 1) była niepoprawna.

Przepraszam za zamieszanie.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Permutacja z powtórzeniami

Post autor: Dasio11 »

kerajs pisze: 26 paź 2019, o 06:05
Dasio11 pisze: 25 paź 2019, o 19:42 Rozwiązanie Janusza Tracza działa bez założenia, że \(\displaystyle{ a > b}\), a jeśli twierdzisz inaczej, to wskaż błąd.
Proszę bardzo: \(\displaystyle{ a=2, b \ge 4}\)
To nie jest błąd, tylko równość i nierówność.
kerajs pisze: 26 paź 2019, o 06:05Nie negowałem poprawności rozwiązania, lecz pominięcie założeń przy których to rozwiązanie zachodzi. A zachodzi ono dla \(\displaystyle{ a \ge b-1}\). Dla \(\displaystyle{ a < b-1}\) nie można ustawić w rzędzie osób tak, aby dwóch mężczyzn nie stało obok siebie, więc tu jest zero sposobów.
Otóż nie: rozwiązanie jest poprawne dla dowolnych liczb całkowitych \(\displaystyle{ a, b \ge 0}\). W szczególności: dla \(\displaystyle{ a=2, b=4}\)\(\displaystyle{ 3}\) miejsca, w których można ustawić mężczyzn, i czterech mężczyzn do ustawienia. Sposobów by to zrobić (modulo rozróżnialność) jest więc tyle, ile \(\displaystyle{ 4}\)-elementowych podzbiorów zbioru \(\displaystyle{ 3}\)-elementowego, czyli \(\displaystyle{ \binom{3}{4} = 0}\).

Oczywiście sam fakt, że liczbie o której piszemy zdarza się czasami być zerem, nie czyni rozwiązania niepoprawnym.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Permutacja z powtórzeniami

Post autor: kerajs »

Dasio11 pisze: 26 paź 2019, o 10:01 Otóż nie: (...)
czyli \(\displaystyle{ \binom{3}{4} = 0}\).
Dobrze że napisałeś ten przykład, gdyż powyższa różnica zdań wynika wyłącznie z różnego definiowania współczynnika dwumianowego. Dla mnie \(\displaystyle{ {n \choose k} }\) jest określone dla \(\displaystyle{ 0 \le k \le n}\) , i stąd moje uwagi.
ODPOWIEDZ