1. Ile jest całkowitych i nieujemnych rozwiązań podwójnej nierówności \(\displaystyle{ 4 \le x^{1}
+ x^{2} + x^{3} + x^{4} \le 7}\) , które spełniają warunki, \(\displaystyle{ x}\) jest nieparzyste, \(\displaystyle{ x^{1}}\) zawiera \(\displaystyle{ \lbrace 1, 2 \rbrace , x^{3}}\) podzielne przez \(\displaystyle{ 3}\) i \(\displaystyle{ x^{4} \le 2}\) .
2. Mamy do dyspozycji \(\displaystyle{ 7}\) osób, wśród których są trzy pary małżeńskie. Na ile sposobów można rozdzielić wszystkie te osoby na trzy zespoły tak, aby przynamniej jedna para była w tym samym zespole?
3. Ile różnych ciągów liter, które ani nie zaczynają się na AB, ani nie kończą się na RA, można utworzyć z liter słowa ABRAKADABRA wykorzystując wszystkie litery?
4. Mamy do dyspozycji \(\displaystyle{ 9}\) osób, wśród których są dwie rodziny: czteroosobowa i trzyosobowa. Na ile sposobów mozna ustawić te \(\displaystyle{ 9}\) osób w szereg tak, aby przynajmniej jedna rodzina stała w komplecie obok siebie?
5. Na ile sposobów można przydzielić \(\displaystyle{ 6}\) ponumerowanych procesów \(\displaystyle{ 4}\) ponumerowanym procesorom tak, aby przynajmniej jeden procesor nie był obciążony żadnym procesem? Przydzielić trzeba wszystkie procesy i każdy proces musi być w całości wykonany na jednym procesorze. Kolejność wykonywania procesów nie ma znaczenia.
6. Mamy \(\displaystyle{ 4}\) psy. Ile jest takich kombinacji, gdzie żaden z psów nie zajmuje miejsca na mecie zgodnego ze swoim numerem?
1) \(\displaystyle{ \left( x ^{1} + x ^{3} + x ^{5} + x ^{7} \right) \left( x ^{1} + x ^{2} \right) \left( x ^{3} + x ^{0} + x ^{6} \right) \left( x ^{0} + x ^{1} + x ^{2} \right)}\)
Po wyliczeniu sumuję wszystko od \(\displaystyle{ x ^{7}}\) do \(\displaystyle{ x ^{4}}\). Wynik: \(\displaystyle{ 18}\).
2) \(\displaystyle{ \lbrace \frac{4}{3} \rbrace}\) dlatego, że \(\displaystyle{ 3}\) osoby są ze sobą związane (są w parze z \(\displaystyle{ 3}\) innymi). Ile sposobów? \(\displaystyle{ 6.}\)
3) \(\displaystyle{ \frac{11!}{3!2!} = 3\ 326\ 400}\) ?
6) Tutaj wiem jak rozwiązać zadanie rekurencyjnie, ale raczej wykładowca tego nie akceptuje.
Mógłby ktoś mi wyjaśnić czy dobrze zrobiłem w/w zadania i jak zrobić pozostałe?
Dzięki!
Pozdrawiam!
Kilka zadań z kombinatoryki
Kilka zadań z kombinatoryki
Ostatnio zmieniony 2 lip 2018, o 22:07 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
Powód: Niepoprawnie napisany kod LaTeX-a. Proszę zapoznaj się z http://matematyka.pl/178502.htm .
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Kilka zadań z kombinatoryki
6. Słyszałeś może o nieporządkach? To permutacje bez punktów stałych, jest znany wzór na ich liczbę.
Wzór ten można udowodnić stosując zasadę włączeń i wyłączeń.
Wzór ten można udowodnić stosując zasadę włączeń i wyłączeń.
- kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Kilka zadań z kombinatoryki
Ad 1.
To prawidłowe rozwiązanie, o ile treść zadania byłaby taka:
Doprecyzuj co znaczy: podział na zespoły. Jeśli to podział na trzy niepuste zbiory to podana odpowiedź jest błędna.
Ad 3.
Ta treść wymaga doprecyzowania. Zdanie: które ani nie zaczynają się na AB, ani nie kończą się na RA można interpretować jako:
a) które nie zaczynają się na AB i nie kończą się na RA
\(\displaystyle{ \frac{11!}{5!2!2!}- \frac{7!}{3!}}\)
b) które nie zaczynają się na AB lub nie kończą się na RA
\(\displaystyle{ \frac{11!}{5!2!2!}-\frac{9!}{4!2!}-\frac{9!}{4!2!}+ \frac{7!}{3!}}\)
Ad 4.
Trójka stoi razem + Czwórka stoi razem - nadmiarowe przypadki gdy trójka i czwórka stoją obok siebie:
\(\displaystyle{ 5!3!+4!4!-2 \cdot 4!3!}\)
Ad 5.
Wszystkie możliwe przydziały procesów - przydziały gdy wszystkie procesory są obciążone:
\(\displaystyle{ 4^6- {6 \choose 4} \cdot 4 \cdot 4^2}\)
To prawidłowe rozwiązanie, o ile treść zadania byłaby taka:
Ad 2.1. Ile jest całkowitych i nieujemnych rozwiązań podwójnej nierówności \(\displaystyle{ 4 \le x^{1}
+ x^{2} + x^{3} + x^{4} \le 7}\) , które spełniają warunki, \(\displaystyle{ x_1}\) jest nieparzyste, \(\displaystyle{ x_{2} \in \lbrace 1, 2 \rbrace , \ \ x_{3}}\) podzielne jest przez \(\displaystyle{ 3}\) i \(\displaystyle{ x_{4} \le 2}\) .
Doprecyzuj co znaczy: podział na zespoły. Jeśli to podział na trzy niepuste zbiory to podana odpowiedź jest błędna.
Ad 3.
Ta treść wymaga doprecyzowania. Zdanie: które ani nie zaczynają się na AB, ani nie kończą się na RA można interpretować jako:
a) które nie zaczynają się na AB i nie kończą się na RA
\(\displaystyle{ \frac{11!}{5!2!2!}- \frac{7!}{3!}}\)
b) które nie zaczynają się na AB lub nie kończą się na RA
\(\displaystyle{ \frac{11!}{5!2!2!}-\frac{9!}{4!2!}-\frac{9!}{4!2!}+ \frac{7!}{3!}}\)
Ad 4.
Trójka stoi razem + Czwórka stoi razem - nadmiarowe przypadki gdy trójka i czwórka stoją obok siebie:
\(\displaystyle{ 5!3!+4!4!-2 \cdot 4!3!}\)
Ad 5.
Wszystkie możliwe przydziały procesów - przydziały gdy wszystkie procesory są obciążone:
\(\displaystyle{ 4^6- {6 \choose 4} \cdot 4 \cdot 4^2}\)