TU Wien:Diskrete Mathematik für Informatik VO (Drmota)/Prüfung 2015-11-27

1 Generating functions

a) A(z) is the OGF of $a_{n}$. Compute the OGF of $b_{n}$ und $c_{n}$

$b_{n}=\Sigma _{k=0}^{n}a_{k}$

Solution: Either by building difference of b_n and b_n+1, or applying convolution formula

$c_{n}=n*a_{n}$

Solution: Differentiate formula for (a_n) = 1, multiply z

b) D(z)

$d_{0}=1$ and

$d_{n}=\Sigma _{k=0}^{n}d_{k}\cdot (n-k)$ for $n\geq 1$

Solution: Compute difference of d_(n+1) and d_(n), simplify, build the difference again, plug in OGF formula

2 Möbius function

a) Calculate Möbiusfunction

Solution: -1 IIRC

b) Relations (c,b) and (d,a) removed, what is the new $\mu (0,1)$

Solution: 1 IIRC

3 Maximal Flow

a) Compute the maximal flow of

Solution: Use Edmond Karp Algo (=Ford Fulkerson with shortest path)

b) Does the maximal flow change if edge $(a,d)$ is capped.

Solution: No, same flow can be pushed over other edges if (a,d) is missing

4 Irreducible Polynoms / System of Congruences

Irreducible Polynoms over Z3

$f(x)=x^{2}+x+1$

$g(x)=x^{2}+2x+1$

Solution: Plug in all $x\in Z_{3}$, irreducible if there are no roots

System of Congruences

$y^{3}\equiv 1\mod 3$

$12y\equiv 9\mod 15$

Solution: Fermat's little theorem for the y^3 part, then Chinese Remainder Theorem