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\ast 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\ge 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 1mod3$

$12y\equiv 9mod15$

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