TU Wien:Discrete Mathematics VO (Gittenberger)/Written Exam 2022-11-25

1) Compute the number of spanning trees of the given graph:

• G = (V,E)
• V = {1,..,8}
• E = {(1,2),(1,3),(2,4),(3,4),(5,8),(5,6),(6,8),(6,7),(7,8)}

2) Compute the value of $\mu (0,1)$ for the given Hasse diagram.

3) Solve the following recurrence relation using generating functions. (Something like this...)

$a_{n+3}-3a_{n+2}+3a_{n+1}+a_{n}=1$

,where: $a_{0}=1,a_{1}=3,a_{2}=0$

4) Show the identity:

$\sum _{k=0}^{n}{\binom {m+k}{k}}={\binom {n+m+1}{m+1}}$

using a combinatorial interpretation. Hint: Consider 0-1-sequences and group them according to the position of the last.