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

1 Erzeugende Funktionen

a) A(z) ist bekannt, bestimme die erzeugende Funktionen für $b_n$ und $c_n$

$b_n={\Sigma }_{k=0}^n{a}_k$

$c_n=n\ast a_n$

b) D(z)

$d_n={\Sigma }_{k=0}^n{d}_k\cdot (n-k)$

2 Möbiusfunction

a) Calculate Möbiusfunction

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

3 Maximal Flow

a) Maximal Flow with Ford-Fulkerson algorithm

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

4 Irreducible Polynoms / System of Congruences

Irreducible Polynoms over Z3

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

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

System of Congruences

$y^3\equiv 1mod3$

$12y\equiv 9mod15$