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.
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}
\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)
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.
Nasze karty to kwadraty 3x3. 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\}.
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.