TU Wien:Discrete Mathematics VO (Gittenberger)/Written Exam 2022-05-06

1. Give A = {a,b,c}.

(a) What is the number of multisets of cardinality 12 built up from A?

How many of these sets are subsets of B={...} (where B was a specific multiset) Answer by ...

(b) restraining the number multisets found in (a)?

(c) using the principle of inclusion-exclusion (some more hints were given)

2. Let R be an integral domain. Prove that (a) = {ra | r € R}

3. Given an undirected Graph G. Let D be the degree matrix and A the adjacency matrix. Define B the incidence matrix with nodes as rows and edges as columns and B[i][e] = 1 iff node i is incident to edge e and B[i][e] = 0 otherwise. Prove that A+D=B * B^T where B^T is the transpose of B.

4. Given the following two systems of congruences. Either give the solutions using CRT or prove that there is none:

(a) 2x=2 (8) ...

(b) 4x=2 (8) ...