TU Wien:Discrete Mathematics VO (Gittenberger)/Written exam 2024-10-04

Exercise 1

1. How many multisets of $\{a,b,c\}$ are there of size 12?
2. How many multisets which are subsets of $M=\{a,a,a,a,b,b,b,b,b,b,c,c,c,c,c\}$ are there of size 12? Answer this question by
   1. Determining the number of multisets which are not subsets of $M$ because they contain too many a's;
   2. Using the principle of inclusion-exclusion.

Exercise 2

Let $R$ be an integral domain, and $a\in R$. Prove that $(a)=\{ar~|~r\in R\}$.

Exercise 3

Let $G=(V,E)$ be a simple, undirected graph of $n=|V|$ vertices and $m=|E|$ edges. Also let $A\in \{0,1\}^{n\times n}$ be the adjacency matrix, $B\in \{0,1\}^{n\times m}$ the incidence matrix and $D$ the degree matrix of $G$, where $a_{ij}=1\iff (v_{i},v_{j})\in E$ and $b_{ij}=1\iff v_{i}{\text{ incident to }}e_{j}$. Prove that $A+D=BB^{T}$.

Exercise 4

Solve the following two systems of linear congruences or prove that there is no solution:

1. ${\textstyle {\begin{cases}2x&\equiv _{8}4\\5x&\equiv _{11}2\\4x&\equiv _{15}5\end{cases}}}$,
2. ${\begin{cases}4x&\equiv _{8}2\\5x&\equiv _{11}2\\4x&\equiv _{15}5\end{cases}}$.