Kilka zadań z kombinatoryki

[Raven42]

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!

[Premislav]

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ń.

[kerajs]

Ad 1.
To prawidłowe rozwiązanie, o ile treść zadania byłaby taka:

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}\) .

Ad 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}\)