<commit_before>---
layout: page
permalink: /2014/egzamin/1/
---

## 2014 Pierwszy termin

###Zadanie 1
Udowodnij tożsamość

$$\sum_{k}{ n\brack k}{k\brace m} = {n\choose m}\frac{(n-1)!}{(m-1)!}$$

dla \\(n, m > 0\\)

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
    <p>
      <b>LEWA:</b> Dzielimy \(n\) elementów na \(k\) cykli, a następnie cykle dzielimy na
      zbiory tak, że żaden zbiór nie może być pusty.
    </p>
    <p>
      <b>PRAWA:</b> Wybieramy \(m\) elementów, które będą początkami słów. Wyróżniamy jeden z nich
      i stawiamy go na pierwszym miejscu, a następnie permutujemy pozostałe \(n-1\) elementów.
      Następnie rozcinamy ten \(n\)-elementowy ciąg przed każdym z wybranych elementów i
      otrzymujemy ciąg \(m\) słów. Podzielenie przez \(m!\) przekształca ten ciąg w zbiór \(m\) słów.
      $${n\choose m}m\frac{(n-1)!}{m!} = {n\choose m}\frac{(n-1)!}{(m-1)!}$$
    </p>
    <p>
      Żeby udowodnić tę równość wskażę bijekcje pomiędzy obiema stronami. Jeżeli mamy już dany jakiś
      podział na cykle i ich zbiory, to popatrzmy na jeden ze zbiórów. Ustalmy że zapisujemy cykle tak,
      że zawsze pierwszy element cyklu jest najmniejszy ze wszystkich, które do niego należą (tak jak w zapisie kanonicznym),
      a w ramach całego zbioru ustawiamy je w kolejności malejącej względem pierwszego elementu.
      Starcie wszystkich nawiasów wyznacza bijekcje między zbiorem cykli, a słowem.
      $$(6)(358)(24) \mapsto 635824$$
      W drugą stronę, jeżeli mamy dane jakieś słowo, to możemy odzyskać zbiór cykli w następujący sposób:
      weźmy pierwszy element słowa i do jego cyklu dopisujmy po kolei następne elementy tak długo, aż
      któryś z nich nie będzie większy niż pierwszy element. Kiedy napotkamy taki, to w tym momencie kończymy cykl
      i powtarzamy procedurę zaczynając od napotkanego elementu.
      $$635824 \mapsto (6)35824 \mapsto (6)(358)24 \mapsto (6)(358)(24)$$
    </p>
</div>
</div>
###Zadanie 2
Znajdź liczbę 6-literowych słów złożonych z liter A, B, C, D, E w
których: każda z liter A, B występuje _co najwyżej raz_, a każda z liter
C, D - _co najmniej raz_.

###Zadanie 3
Wierzchołki grafu \\(G\_n\\) to wszystkie liczby złożone ze zbioru
{1,...,n} a para {i,j} jest krawędzią wtedy i tylko wtedy gdy
\\(i\perp j\\). Rozstrzygnij czy graf \\(G\_{1000}\\) jest:

a) planarny

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
     Nie, następujące względnie pierwsze liczby: 4, 9, 25, 36, 49
     (kwadraty kolejnych liczb pierwszych)
     tworzą klikę \(K_5\) co z tw.
     Kuratowskiego oznacza że nie jest planarny.

  </div><commit_msg>Czerwiec 2014 zadanie 2 - pierwsza część<commit_after>---
layout: page
permalink: /2014/egzamin/1/
---

## 2014 Pierwszy termin

###Zadanie 1
Udowodnij tożsamość

$$\sum_{k}{ n\brack k}{k\brace m} = {n\choose m}\frac{(n-1)!}{(m-1)!}$$

dla \\(n, m > 0\\)

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
    <p>
      <b>LEWA:</b> Dzielimy \(n\) elementów na \(k\) cykli, a następnie cykle dzielimy na
      zbiory tak, że żaden zbiór nie może być pusty.
    </p>
    <p>
      <b>PRAWA:</b> Wybieramy \(m\) elementów, które będą początkami słów. Wyróżniamy jeden z nich
      i stawiamy go na pierwszym miejscu, a następnie permutujemy pozostałe \(n-1\) elementów.
      Następnie rozcinamy ten \(n\)-elementowy ciąg przed każdym z wybranych elementów i
      otrzymujemy ciąg \(m\) słów. Podzielenie przez \(m!\) przekształca ten ciąg w zbiór \(m\) słów.
      $${n\choose m}m\frac{(n-1)!}{m!} = {n\choose m}\frac{(n-1)!}{(m-1)!}$$
    </p>
    <p>
      Żeby udowodnić tę równość wskażę bijekcje pomiędzy obiema stronami. Jeżeli mamy już dany jakiś
      podział na cykle i ich zbiory, to popatrzmy na jeden ze zbiórów. Ustalmy że zapisujemy cykle tak,
      że zawsze pierwszy element cyklu jest najmniejszy ze wszystkich, które do niego należą (tak jak w zapisie kanonicznym),
      a w ramach całego zbioru ustawiamy je w kolejności malejącej względem pierwszego elementu.
      Starcie wszystkich nawiasów wyznacza bijekcje między zbiorem cykli, a słowem.
      $$(6)(358)(24) \mapsto 635824$$
      W drugą stronę, jeżeli mamy dane jakieś słowo, to możemy odzyskać zbiór cykli w następujący sposób:
      weźmy pierwszy element słowa i do jego cyklu dopisujmy po kolei następne elementy tak długo, aż
      któryś z nich nie będzie większy niż pierwszy element. Kiedy napotkamy taki, to w tym momencie kończymy cykl
      i powtarzamy procedurę zaczynając od napotkanego elementu.
      $$635824 \mapsto (6)35824 \mapsto (6)(358)24 \mapsto (6)(358)(24)$$
    </p>
</div>
</div>
###Zadanie 2
Znajdź liczbę 6-literowych słów złożonych z liter A, B, C, D, E w
których: każda z liter A, B występuje _co najwyżej raz_, a każda z liter
C, D - _co najmniej raz_.

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
     <p>Użyjemy wykładniczych funkcji tworzących. Na początku policzymy WFT dla
     słów złożonych tylko jednej litery a potem je spleciemy i odczytamy tak otrzymany 
     wynik.</p>
     <p>Dla litery A istnieje dokładnie jedno słowo długości zero zawierające co
     najwyżej raz literę A, podobnie dla słowa długości 1. Słowa o długości większej
     niż 1 i składające się wyłącznie z liter A nie istnieją. Zapiszmy enumerator:
     \(\sum^{\infty}_{n=0}([n=0]+[n=1])\frac{z^n}{n!} = z + 1\). Taki sam enumerator
     wyjdzie dla B.</p>
     <p>W przypadku gdy rozpatrujemy słowa długości \(n\) złożone tylko z litery C
     to będzie istniało tylko jedno słowo o ile \(n \ne 0\). Enumerator wygląda tak:
     \(\sum^{\infty}_{n=0}[n\ne 0]\frac{z^n}{n!} = \sum^{\infty}_{n=0}\frac{z^n}{n!} - 1 = e^z - 1\). To samo dla litery D.</p>
     <p>Na literę E nie nakładamy żadnych ograniczeń zatem enumeratorem jest 
     \(\sum^{\infty}_{n=0}\frac{z^n}{n!} = e^z\).</p>
     <p>Teraz należy to wszystko ze sobą spleść: \((z+1)^2(e^z-1)^2e^z\), wymnożyć
     i otrzymany enumerator zamienić w szereg a następnie odczytać współczynnik
     przy \(z^6\) który będzie wynikiem.</p>
  </div>
</div>

###Zadanie 3
Wierzchołki grafu \\(G\_n\\) to wszystkie liczby złożone ze zbioru
{1,...,n} a para {i,j} jest krawędzią wtedy i tylko wtedy gdy
\\(i\perp j\\). Rozstrzygnij czy graf \\(G\_{1000}\\) jest:

a) planarny

<div data-collapse>
  <h4 class="collapsible">Rozwiązanie</h4>
  <div class="solution">
     Nie, następujące względnie pierwsze liczby: 4, 9, 25, 36, 49
     (kwadraty kolejnych liczb pierwszych)
     tworzą klikę \(K_5\) co z tw.
     Kuratowskiego oznacza że nie jest planarny.

  </div>
{'fraction_non_alphanumeric': 0.12324049116501946, 'fraction_numerical': 0.02590595986822402, 'mean_word_length': 3.311814073595868, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2469816', 'n_tokens_mistral': 3036, 'n_tokens_neox': 3042, 'n_words': 848}