szukanie zaawansowane
 [ Posty: 13 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 12:05 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
Cześć uczę się kolokwium i mam kilka przykładowych zadań które mogą się pojawić, ale nie wiem czy dobrze rozwiązuję.

1. Na ile sposobów 6 osób może rozdzielić między siebie 10 jednakowych przedmiotów tak, by:
a. Każda osoba wzięła przynajmniej jeden przedmiot.
b. Dokładnie dwie spośród nich nie wzięły żadnego

2. Na ile sposobów można rozdzielić między 5 osób opracowanie 15 różnych tematów tak, by:
a. Każdy osoba opracowała przynajmniej jeden.
b. Jaś opracował dokładnie 10, a pozostali – po co najmniej jednym temacie

3. Niech X = \{1,2,3,...,45\} i niech A będzie dowolnym 10-elementowym podzbiorem zbioru X.
Udowodnij, że w rodzinie wszystkich dwuelementowych podzbiorów zbioru A istnieją dwa podzbiory mające identyczny moduł różnicy elementów.

Zad 1.
a) {9\choose 5}
b) {9\choose 3}

Zad 2.
a) 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 5^{10}
Bo: pierwsze 5 tematów możemy wybrać na 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11, pozostałe 10 tematów możemy każdy z nich przyporządkować na 5 sposobów bo tyle jest osób.
b) {15\choose 10} \cdot 5!
Bo: wybieramy najpierw 10 tematów dla Jasia, później pozostaje nam 5 tematów gdzie musimy rozdać 5x po 1 temacie.

Trzeciego totalnie nie mam pojęcia jak rozwiązać.
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 12:25 
Użytkownik
Avatar użytkownika

Posty: 1392
Lokalizacja: Polska, Warmia, Olsztyn :)
w trzecim skorzystaj z zasady szufladkowej, podzbiorów dwuelementowych zbioru dziesięcioelementowego jest 45 a możliwych wartości modułu różnic jest 44
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 14:07 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
Mimo podpowiedzi nadal nie wiem co z tym dalej zrobić.
Czy pozostałe moje rozwiązania są poprawne ?
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 14:08 
Użytkownik
Avatar użytkownika

Posty: 6670
To nie była podpowiedź, ale rozwiązanie zadania.

Tylko 1a) masz dobrze.
piolug93 napisał(a):
Zad 1.
a) {9\choose 5}
b) {9\choose 3}
1b) Osoby są rozróżnialne (tak je traktujesz w 1a)) więc musisz zdecydować kto nic nie dostanie.
{6 \choose 4} {9\choose 3}

piolug93 napisał(a):
Zad 2.
a) 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 5^{10}
Bo: pierwsze 5 tematów możemy wybrać na 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11, pozostałe 10 tematów możemy każdy z nich przyporządkować na 5 sposobów bo tyle jest osób.
Tu te same zestawy zliczasz kilkukrotnie.
Z zasady włączeń i wyłączeń:
2a) 5^{15}- {5 \choose 1} 4^{15} +{5 \choose 2} 3^{15} -{5 \choose 3} 2^{15} +{5 \choose 4} 1^{15}

piolug93 napisał(a):
Zad 2.
b) {15\choose 10} \cdot 5!
Bo: wybieramy najpierw 10 tematów dla Jasia, później pozostaje nam 5 tematów gdzie musimy rozdać 5x po 1 temacie.
J.w.
2b)
{15 \choose 10}\left(  4^{5}- {4 \choose 1} 3^{5} +{4 \choose 2} 2^{5} -{4 \choose 3} 1^{5} \right)
albo
{15 \choose 10} {4 \choose 1} {5 \choose 2}3!
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 14:40 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
2b)
{15 \choose 10} {4 \choose 1} {5 \choose 2}3!

Mógł byś to objaśnić ?
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 17:05 
Użytkownik
Avatar użytkownika

Posty: 6670
piolug93 napisał(a):
2b)
{15 \choose 10} {4 \choose 1} {5 \choose 2}3!

Skoro Jaś wybrał 10 tematów z 15, to z 4 pozostałych osób wybieram 1, co opracuje 2 z pozostałych 5 tematów. Ostatnie 3 tematy rozdzielam po jednym wśród pozostałych 3 osób.
Góra
Mężczyzna Offline
PostNapisane: 9 sty 2019, o 20:45 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
Hmm, a czy 2a) można rozwiązać dzięki liczbie Stirlinga ?
5^{15}- {5 \choose 1} 4^{15} +{5 \choose 2} 3^{15} -{5 \choose 3} 2^{15} +{5 \choose 4} 1^{15}
Czy nie powinno być:
5^{15}- {5 \choose 1} 4^{10} +{5 \choose 2} 3^{10} -{5 \choose 3} 2^{10} +{5 \choose 4} 1^{10}
Zostaje nam przecież 10 tematów wtedy. Chyba, że ja to wszystko źle rozumiem.
Góra
Mężczyzna Offline
PostNapisane: 10 sty 2019, o 09:01 
Użytkownik
Avatar użytkownika

Posty: 6670
piolug93 napisał(a):
Hmm, a czy 2a) można rozwiązać dzięki liczbie Stirlinga ?
Można
2a)
\left\{\begin{matrix}15\\5\end{matrix}\right\} \cdot 5!
2b)
{15 \choose 10} \cdot  \left\{\begin{matrix} 5 \\ 4 \end{matrix}\right\} \cdot 4!

O ile w drugim przypadku wynik liczbowy jest natychmiastowy:
2b)
{15 \choose 10} \left\{\begin{matrix} 5 \\ 4 \end{matrix}\right\}  4!={15 \choose 10} {5 \choose 2}  4!={15 \choose 10} \cdot 2 \cdot 5!=2 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11=....
to w pierwszym trzeba rekurencyjnie zjechać do wartości występujących w posiadanej tabelce liczb Stirlinga II rodzaju, lub dalej do elementarnych wzorków na te liczby.


piolug93 napisał(a):
5^{15}- {5 \choose 1} 4^{15} +{5 \choose 2} 3^{15} -{5 \choose 3} 2^{15} +{5 \choose 4} 1^{15}
Czy nie powinno być:
5^{15}- {5 \choose 1} 4^{10} +{5 \choose 2} 3^{10} -{5 \choose 3} 2^{10} +{5 \choose 4} 1^{10}
Zostaje nam przecież 10 tematów wtedy. Chyba, że ja to wszystko źle rozumiem.
Przypuszczam, że błędnie interpretujesz podane wyrażenie. Tam jest tak:
Możliwe przyporządkowania 5 osobom 15 tematów - nadmiarowo liczone przyporządkowania 4 osobom 15 tematów + brakujące (w wyniku odejmowania poprzednich dwóch wyrażeń) przyporządkowania 3 osobom 15 tematów - nadmiarowo (w wyniku poprzednich działań) liczone przyporządkowania 2 osobom 15 tematów + brakujące (w wyniku poprzednich działań) przyporządkowania 1 osobie 15 tematów.
Góra
Mężczyzna Offline
PostNapisane: 10 sty 2019, o 13:49 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
5^{15}- {5 \choose 1} 4^{15} +{5 \choose 2} 3^{15} -{5 \choose 3} 2^{15} +{5 \choose 4} 1^{15}
{5 \choose 1} 4^{15} czym jest w tym przypadku symbol Newtona ?
Góra
Mężczyzna Offline
PostNapisane: 10 sty 2019, o 20:38 
Użytkownik

Posty: 1
Lokalizacja: Warszawa
Cześć, mam pytanie odnośnie 1b)
kerajs napisał(a):
Tylko 1a) masz dobrze.
piolug93 napisał(a):
Zad 1.
a) {9\choose 5}
b) {9\choose 3}
1b) Osoby są rozróżnialne (tak je traktujesz w 1a)) więc musisz zdecydować kto nic nie dostanie.
{6 \choose 4} {9\choose 3}


Moglibyście wyjaśnić w jaki sposób otrzymaliśmy {9\choose 3} ?
Czy nie jest tak, że po wybraniu osób mamy do rozdzielenia 10 przedmiotów na 4 osoby, czyli: {10+4-1\choose 4-1}={13\choose 3} ?
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2019, o 01:51 
Użytkownik
Avatar użytkownika

Posty: 6670
piolug93 napisał(a):
5^{15}- {5 \choose 1} 4^{15} +{5 \choose 2} 3^{15} -{5 \choose 3} 2^{15} +{5 \choose 4} 1^{15}
{5 \choose 1} 4^{15} czym jest w tym przypadku symbol Newtona ?

Zgodnie z treścią zadania 15 zestawów należy rozdzielić między 5 osób (nazwę je A, B, C, D, E) tak, aby każda osoba opracowała przynajmniej jeden.
Wyrażenie 5^{15} to ilość wszystkich możliwych rozdziałów zestawów między osoby, w tym i takie w których niektóre z osób nic nie dostały. Chcąc zliczyć tylko takie zestawy w których obdzielani są wszyscy próbuję odjąć podziały z mniejszą ilością obdzielonych zestawami osób. Przydział 15 zestawów 4 osobom realizuje się na 4^{15} sposobów (w tym i takich, w których niektóre z osób nic nie dostały). Jednak tymi osobami mogą być {ABCD}, {ABCE}, {ABDE}, {ACDE}, {BCDE} (albo osoby bez E, bez D, bez C, bez B albo bez A) i stąd czynnik o który pytasz.

mikel0o7 napisał(a):
Czy nie jest tak, że po wybraniu osób mamy do rozdzielenia 10 przedmiotów na 4 osoby, czyli: {10+4-1\choose 4-1}={13\choose 3} ?
Tak by było gdyby uwzględniać także podziały w których będzie osoba lub osoby które nic nie dostaną.
A przecież treść zadania z tematu narzuca warunek:
Cytuj:
(...)tak, by:
a. Każda osoba wzięła przynajmniej jeden przedmiot.
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2019, o 10:13 
Użytkownik

Posty: 6
Lokalizacja: Legionowo
1. Na ile sposobów 5 osób może rozdzielić między siebie 10 różnych przedmiotów tak, by:
a. Każda osoba wzięła przynajmniej jeden przedmiot.
b. Jaś (a może nie tylko Jaś) nie wziął żadnego.

Odp.
a) S(10,5)\cdot5!
b) 4^{10}

Czy poprawnie to rozwiązałem ?
Góra
Mężczyzna Offline
PostNapisane: 11 sty 2019, o 14:09 
Użytkownik
Avatar użytkownika

Posty: 6670
Tak.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 13 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile liczb 8 cyfrowych można utworzyć...  enef  1
 Na ile sposobów można rozsadzić dzieci  TrzyRazyCztery  3
 Na ile sposobów można wybrać - zadanie 2  mida  4
 Na ile sposobów można przedstawić liczbę.  1608  6
 Ile można wariacia/kombinatoryka  Acura_100  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl