====== Matematyka dyskretna (M) - Lista 6. ======

===== Zadanie 1. =====
Po lewej stronie równości mamy wybranie reprezentacji z n osób(może być od 1 do n osób) - to przedstawiamy przez $\sum_{k=1}^n$ . $n\choose{k}$ przedstawia wybranie $k$ osobowej reprentacji z $n$ osób. $k$ to możliwości wybrania szefa.\\
Po prawej stronie: $n$ możliwości wybrania szefa i $2^{n-1}$ to moc zbioru potęgowego jakiegoś zbioru o mocy $n-1$, czyli ilość podzbiorów ludzi bez szefa.
===== Zadanie 2. =====
Wzór z wykładu, na ilość sposobów rozmieszczenia $a$ nierozróżnialnych przedmiotów w $b$ szufladach.\\

$N=$ ${a+b-1}\choose{b-1}$\\

Mamy $L$ zer i $K$ jedynek.\\
Wstawiamy $K-1$ zer między nasze jedynki.\\
Mamy ciąg: $1010...101$\\
Zostało nam $L-(K-1)$ zer.\\
Mamy $K+1$ szufladek, $K-1$ między jedynkami i $2$ - na początku i końcu.\\
Podstawiamy do wzoru:\\
$a=L-K+1$\\
$b=K+1$\\
$N=$ ${L+1}\choose{K}$\\

===== Zadanie 3. =====
$\displaystyle 
\lfloor\frac{n}{2}\rfloor - \lfloor\frac{n}{2*5}\rfloor - \lfloor\frac{n}{2*7}\rfloor + \lfloor\frac{n}{2*5*7}\rfloor + \lfloor\frac{n}{3}\rfloor - \lfloor\frac{n}{3*5}\rfloor - \lfloor\frac{n}{3*7}\rfloor + \lfloor\frac{n}{3*5*7}\rfloor - \left(\lfloor\frac{n}{2*3}\rfloor - \lfloor\frac{n}{2*3*5}\rfloor -\lfloor\frac{n}{2*3*7}\rfloor + \lfloor\frac{n}{2*3*5*7}\rfloor\right)$
===== Zadanie 6. =====
$20^n - ( {5 \choose 1}16^n - {5 \choose 2}12^n + {5 \choose 3}8^n - {5 \choose 4}4^n + {5 \choose 5}0^n)$\\
Korzystam z zasady włączeń i wyłączeń. Od wszystkich możliwości ($20^n$, bo każdy element można wsadzić do jednej z 20 szuflad, czyli 20*20...*20) odejmuje sytuację kiedy jakaś komoda jest pusta. 

===== Zadanie 16. =====
Nasze karty to kwadraty $3$x$3$. Grupa symetrii kwadratu wygląda to:

$G = \{ id , o90, o180, o270, sx ,sy , sd1 ,sd2 \}$\\

$fix(id) =$ ${9}\choose{2} $, bo wybieramy 2 dziurki z 9 miejsc, punktem stalym od id są wszystkie przypadki\\
$fix(o90)=fix(o270)=0$, bo żadne takie podziurkowanie nie ma punktów stałych przy takich obrotach\\
$fix(o180)=4$, są to dziurkowania w postaciach:\\
|0| | |
| | | |
| | |0|

| |0| |
| | | |
| |0| |

| | | |
|0| |0|
| | | |

| | |0|
| | | |
|0| | |
$fix(sx)=fix(sy)=fix(sd1)=fix(sd2)=6$, bo w każdym mamy 3 możliwości wybrania punktów, które nie leza na osi symetrii(wybieramy jedno pole, ktore nie jest na osi symetrii, a drugie jest determinowane przez symetrie, mozemy wybierać z 3 pól, czyli $(^3_1)=3$) lub 3 możliwości rozłożenia tych punktów na tej osi(kładziemy pierwszy punkt na osi symetrii, nie możemy położyć drugiego nie na osi, bo wymagałby odbicia, więc drugi też kładziemy na osi, czyli $(^3_2)=3$).\\

Liczba możliwości $=\frac{1}{|G|}\sum_{g\in G}fix(g)=\frac{36+2\cdot0+4+4\cdot6}{|G|}=\frac{36+2\cdot0+4+4\cdot6}{8}=\frac{64}{8}=8$\\
gdzie $fix(g)=\{x\in X: g(x)=x\}$.

===== Zadanie 17. =====
Wszystkich naszyjników = $2^P$\\

Nasza grupa to grupa obrotów i symetrii p-kąta foremnego:\\

$G = \{ id, o(\frac{2\cdot\pi}{p}), o(2\cdot\frac{2\cdot\pi}{p}), ... , o( (p-1)\cdot\frac{2\pi}{p}), s1, s2, ..., sp\}$\\

Z tego, że liczba jest pierwsza wiemy, że dla każdego $n$ w postaci $i\cdot\frac{2\cdot\pi}{p}$ zachodzi:\\
$fix(o(n) )=2$, bo jedyne takie naszyjniki, to cały czarny lub cały biały. Z twierdzenia Lagrange, rząd elementu musi dzielić rząd grupy.

$fix(s(n) )=2^{(\frac{p-1}{2})+1}$, bo oś symetrii zawsze wygląda tak, ze przechodzi przez jeden kamień i przeciwległą krawędź, mamy $2$ możliwości wyboru koloru korala na osi symetrii i $\frac{p-1}{2}$ możliwości wyboru koloru dla kamieni po jednej stronie, bo pozostale beda symetryczne.\\

Liczba naszyjników = $\displaystyle \frac{1}{|G|}\sum_{g\in G}fix(g)=\frac{2^p + 2\cdot (p-1)+p\cdot2^{(\frac{p-1}{2})+1} }{2p} =\frac{2^{p-1} + (p-1)+p\cdot2^{\frac{p-1}{2}}}{p} $.\\
Jest całkowite, bo $2^{p-1}$ z tw. Fermata daje reszte $1$ przy dzieleniu przez $p$, sumuje sie z $P-1$ i wtedy można skrócić $p$ w mianowniku.

{{tag>[listy_zadan]}}