###### tags: `Matematyka Dyskretna M`

# Lista 6
## 1

$\displaystyle\sum_{k=1}^nk\binom{n}{k}$ rozpatrza wiele przypadków, zależnie od tego ilu osobową grupę weźmiemy. Dla przypadku k-tego wybieramy $k$ z pośród $n$ ludzi do delegacji i robimy to na $\binom{n}{k}$
sposobów, a potem z tej grupy wybieramy przewodniczącego na $k$ sposobów. Czyli grupe $k$ osobową z przewodniczącym wybieramy na $k\times\binom{n}{k}$, czyli po zsumowaniu po $k$ od $k=1$ do $k=n$ $k\times\binom{n}{k}$ dostaniemy liczbę sposobów wybrania spośród $n$ osób delegacji z jej przewodniczącym.

$n2^{n-1}$- Wybieramy przewodniczącego delegacji na $n$ sposobów. Zostało nam $n-1$ osób. Każdą osobę albo weźmiemy do grupy albo nie, więc można ich wybrać na $2^{n-1}$ sposobów. Czyli całą delegację z przewodniczącym możemy wybrać na $n2^{n-1}$ sposobów.
## 2
Na stałych pozycjach umieszczamy $k$ jedynek. I pomiędzy nimi umieszczamy $k-1$ zer.

Teraz zostało nam $l - (k-1) = l-k+1$ zer. Musimy je rozmieścić na k + 1 pozycjach. Dzięki temu, że ustawiliśmy już obowiązkowe zera pomiędzy jedynkami, musimy znaleźć na ile sposobów możemy ustawić $l-k+1$ zer na $k + 1$ miejscach. Można to zrobić na $\binom{n + m - 1}{m - 1}$ sposobów, gdzie n to liczba zer, a m to liczba miesjc, na które możemy je rozmieścić. Czyli n = l-k+1, a m = k+1, więc po podstawieniu do wzoru otrzymujemy $\binom{l-k+1 + k+1 - 1}{k+1- 1} = \binom{l+1}{k}$. Czyli tych ciągów jest $\binom{l+1}{k}$.

## 3
Liczb, które są podzielne przez x w przedziale $<1,n>$ jest $\lfloor\frac{n}{x}\rfloor$.
Korzystając z tego:

Liczb które są podzielne przez:
2 jest: $\lfloor\frac{n}{2}\rfloor$
3 jest: $\lfloor\frac{n}{2}\rfloor$
2 lub 3 jest: $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{3}\rfloor - \lfloor\frac{n}{2\times3}\rfloor$ Mamy tutaj odejmowanie przypadków, które liczyliśmy podwójnie.

Teraz rozpatrzmy liczby, które chcemy odjąć od naszego wyniku.
Liczb które są podzielne przez:
2 i przez 5 jest: $\lfloor\frac{n}{2\times5}\rfloor$
3 i 5: $\lfloor\frac{n}{3\times5}\rfloor$
2 i 5 lub 3 i 5: $\lfloor\frac{n}{2\times5}\rfloor + \lfloor\frac{n}{3\times5}\rfloor - \lfloor\frac{n}{2\times3\times5}\rfloor$

2 i 7: $\lfloor\frac{n}{2\times7}\rfloor$
3 i 7: $\lfloor\frac{n}{3\times7}\rfloor$
2 i 7 lub 3 i 7: $\lfloor\frac{n}{2\times7}\rfloor + \lfloor\frac{n}{3\times7}\rfloor - \lfloor\frac{n}{2\times3\times7}\rfloor$

Teraz na koniec musimy rozpatrzyć jeszcze przypadki takie, które znowu policzyliśmy podwójnie:

Liczb które są podzielne przez:
2 i 5 i 7 jednocześnie: $\lfloor\frac{n}{2\times5\times7}\rfloor$
3 i 5 i 7: $\lfloor\frac{n}{3\times5\times7}\rfloor$
2 i 5 i 7 lub 3 i 5 i 7: $\lfloor\frac{n}{2\times5\times7}\rfloor + \lfloor\frac{n}{3\times5\times7}\rfloor - \lfloor\frac{n}{2\times3\times5\times7}\rfloor$

Czyli odpowiedź w tym zadaniu to: $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{3}\rfloor - \lfloor\frac{n}{2\times3}\rfloor - (\lfloor\frac{n}{2\times5}\rfloor + \lfloor\frac{n}{3\times5}\rfloor - \lfloor\frac{n}{2\times3\times5}\rfloor + \lfloor\frac{n}{2\times7}\rfloor + \lfloor\frac{n}{3\times7}\rfloor - \lfloor\frac{n}{2\times3\times7}\rfloor - (\lfloor\frac{n}{2\times5\times7}\rfloor + \lfloor\frac{n}{3\times5\times7}\rfloor - \lfloor\frac{n}{2\times3\times5\times7}\rfloor))$
## 4

$|\Omega| = n!$
$A_i$ - zbiór takich rozwiązań, że na $i$ pozycji, zbiór nie posiada swojej liczby.
$|A_1| = (n-1)!$
$|A_1 \cap A_2| = (n-2)!$
$|A_1 \cap A_2 \cap ... \cap A_k| = (n-k)!$

Czyli musimy policzyć (korzystając zasady włączeń i wyłączeń)

$|\Omega| - |A_1 \cup A_2 \cup... \cup A_k| = n! - \displaystyle\sum_{i=1}^k(-1)^{i+1}\binom{k}{i}(n-i)! = \displaystyle\sum_{i=0}^k(-1)^i\binom{k}{i}(n-i)!$

## 6

$|\Omega| = 20^n$
$A_i$ - zbiór takich rozwiązań, że $i$-ta komoda jest pusta (czyli żadna z czterech jej szufla nie posiada żadnego przedmiotu)
$A_1 = (20-4\times1)^n = 16^n$
$|A_1 \cap A_{2}|= (20-4\times2)^n = 12^n$
$|A_1 \cap A_2 \cap ... \cap A_k| = (20-4\times k)^n$

Czyli musimy policzyć (korzystając zasady włączeń i wyłączeń)$|\Omega|-|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5| = 20^n - \displaystyle\sum_{k=1}^5(-1)^{k+1}\binom{5}{k}(20-4k)^n = \displaystyle\sum_{k=0}^5(-1)^k\binom{5}{k}(20-4k)^n$

## 7
Treść zrozumiałem, że w tym ciągu nie może zdarzyć się sytuacja, że obok siebie będą wszystkie wystąpienia którejkolwiek litery.

$|\Omega| = \frac{(\alpha+\beta+\gamma)!}{\alpha!\beta!\gamma!}$

$|A_1|$ Gdy znajduje się cały blok $a$.
$|A_2|$ Gdy znajduje się cały blok $b$.
$|A_3|$ Gdy znajduje się cały blok $c$.

$|A_1| = \frac{(1 + \beta + \gamma)!}{\beta!\gamma!}$ traktując blok złożonych z litery "a" jako jedno wystąpienie
$|A_2| = \frac{(\alpha + 1 + \gamma)!}{\alpha!\gamma!}$
$|A_3| = \frac{(\alpha + \beta + 1)!}{\alpha!\beta!}$

$|A_1 \cap A_2| =\frac{(\gamma+2)!}{\gamma!}$
$|A_2 \cap A_3| =\frac{(\alpha+2)!}{\alpha!}$
$|A_1 \cap A_3| =\frac{(\beta+2)!}{\beta!}$
$|A_1 \cap A_2 \cap A_3|=3!$

Z zasady włączeń i wyłączeń
$|\Omega| - |A \cup B \cup C|=|\Omega|- |A_1| - |A_2| - |A_3| + |A_1 \cap A_2|+|A_2 \cap A_3|+|A_1 \cap A_3| - |A_1 \cap A_2 \cap A_3| =$
$=\frac{(\alpha+\beta+\gamma)!}{\alpha!\beta!\gamma!}- \frac{(1 + \beta + \gamma)!}{\beta!\gamma!} - \frac{(\alpha + 1 + \gamma)!}{\alpha!\gamma!} - \frac{(\alpha + \beta + 1)!}{\alpha!\beta!} + \frac{(\gamma+2)!}{\gamma!} + \frac{(\alpha+2)!}{\alpha!} + \frac{(\beta+2)!}{\beta!}-3!$

## 8

Załóżmy bez straty ogólności, że $a_1\leq a_2\leq...\leq a_n$

Wtedy Lewa strona $L = max(a_1,a_2,...,a_n) = a_n$
Prawa strona $P = \displaystyle\sum_{i=0}^{n-1}(-1)^{i}\binom{n-1}{i}a_1 + \displaystyle\sum_{i=0}^{n-2}(-1)^{i}\binom{n-2}{i}a_2 + \displaystyle\sum_{i=0}^{n-3}(-1)^{i}\binom{n-3}{i}a_3 + ... + \displaystyle\sum_{i=0}^{1}(-1)^{i}\binom{1}{i}a_{n-1} + \displaystyle\sum_{i=0}^{0}(-1)^{i}\binom{0}{i} a_n=$
$=(1-1)^{n-1}a_1+(1-1)^{n-2}a_2+(1-1)^{n-3}a_3+...+(1-1)^1a_{n-1}+\displaystyle\sum_{i=0}^{0}(-1)^{i}\binom{0}{i}a_n = 0^{n-1}a_1+0^{n-2}a_2+0^{n-3}a_3+...+0^1a_{n-1}+a_n = a_n$

Czyli L=P co kończy dowód.
## 9
$|\Omega| = \frac{(2n)!}{2n\times2^n} = \frac{(2n-1)!}{2^n}$
Ponieważ każda osoba osoba wybiera dowolne miejsce na $(2n)!$ sposobów, następnie dzielimy przez $2n$, ponieważ traktuję stół po obrocie o ileś osób jako równoważny, od tego jescze odejmujemy podwójnie liczonych wrogów, ponieważ uznaję, że wrogowie są nierozróżnialni.

$|A_i|$ - zbiór takich rozwiązań, że $i$-ta para siedzi obok siebie.

$|A_1 \cap A_2 \cap ... \cap A_k| = \frac{(2n-k)!}{2n-k}$, ponieważ traktuję dwóch wrogów, którzy siedzą obok siebie jako jedną osobę. Więc zostaje nam $2n-k$ osób, które wybierają miejsca na (2n-k)! sposobów. Dzielimy przez $2n-k$, ponieważ traktuję stół po obrocie o ileś osób jako równoważny.

Czyli musimy policzyć (korzystając zasady włączeń i wyłączeń)$|\Omega|-|A_1 \cup A_2 \cup ... \cup A_k|= \frac{(2n-1)!}{2^n} - \displaystyle\sum_{k=1}^n(-1)^{k+1}\binom{n}{k}\frac{(2n-k)!}{2n-k}=\frac{(2n-1)!}{2^n} - \displaystyle\sum_{k=0}^n(-1)^k\binom{n}{k}(2n-k-1)!$