MAN 240 : Diskret matematik

Tentamen 040604

Lösningar

F.1 (i) Choose 1 keeper from 3, 4 defenders from 8, 4 midfielders from 8 and 2 forwards from 4. Applying MP, the answer is

( \begin{matrix}3 \\ 1 \end{matrix} ) · ( \begin{matrix}8 \\ 4 \end{matrix} ) · ( \begin{matrix}8 \\ 4 \end{matrix} ) · ( \begin{matrix}4 \\ 2 \end{matrix} ) .

(ii) 37 indistinguishable objects (the goals scored) are to be placed in 23 distinguishable cells (the players). The number of ways to do this is

( \begin{matrix}37 + 23 − 1 \\ 23 − 1 \end{matrix} ) = ( \begin{matrix}59 \\ 22 \end{matrix} ) .

F.2 (i) The graph has Hamilton cycles, for example

a → c_{1} → b → g → m_{1} → z → m_{2} → h → j → d → c_{2} → c_{3} → a.

(ii) χ(G^{∗}) ≥ 4 since, for example, the vertex c_{2} is surrounded by an odd cycle formed by a, c_{1}, b, d, c_{3}. On the other hand, if we apply the greedy algorithm to the nodes ordered left-to-right and top-to-bottom, then we get a 4-coloring, namely (the colors are 1, 2, 3, 4)

\begin{matrix}a & 1 & g & 2 \\ c_{1} & 2 & h & 3 \\ c_{2} & 3 & j & 1 \\ c_{3} & 2 & m_{1} & 1 \\ b & 1 & m_{2} & 2 \\ d & 4 & z & 3 \end{matrix}

Hence χ(G^{∗}) = 4.

(iii) Use BFS, starting, say, from the vertex a, to build up the following sequence of edges in a MST :

{a, c_{1}}, {c_{1}, c_{2}}, {c_{2}, b}, {c_{2}, c_{3}}, {c_{3}, d}, {b, g},
{g, m_{1}}, {m_{1}, m_{2}}, {m_{2}, j}, {j, h}, {m_{1}, z} (or {m_{2}, z}).

The total weight of this tree is 15+15+10+15+10+15+10+10+5+10+25 = 140.

(iv) Apply Dijkstra’s algorithm to build up the following tree

Step Choice of edge Labelling
1  ac_{1}  c_{1} := 15
2  ac_{2}  c_{2} := 20
3  ac_{3}  c_{3} := 25
4  c_{2}b  b := 30
5  c_{2}d/c_{3}d  d := 35
6  bg  g := 45
7  bh  h := 45
8  dj  j := 50
9  gm_{1}  m_{1} := 55
10  jm_{2}  m_{2} := 55
11  m_{1}z/m_{2}z  z := 80

Hence the shortest path from a to z has length 80. Depending on the choices you made in Steps 5 and 11, there are three possibilities for the shortest path, namely

a → c_{2} → b → g → m_{1} → z,
a → c_{2} → d → j → m_{2} → z,
a → c_{3} → d → j → m_{2} → z.

(v) Starting with the null flow f ≡ 0, one can find the following sequence of f-augmenting paths from a to z (these are not the only choices, of course) :

a − c_{1} − b − h − m_{1} − z, ϵ = 15,
a − c_{3} − c_{2} − d − h − m_{2} − z, ϵ = 15,
a − c_{2} − b − g − m_{1} − z, ϵ = 10,
a − c_{3} − d − j − m_{2} − z, ϵ = 5.

This yields the following maximal flow with |f| = 45

Edge Flow Edge Flow Edge Flow
(a, c_{1}) 15 (c_{3}, d) 5  (g, m_{1})  10
(a, c_{2}) 10 (d, b)  0  (h, m_{1})  15
(a, c_{3}) 20 (b, g) 10  (h, m_{2})  15
(c_{2}, c_{1}) 0  (b, h) 15  (j, m_{2})  5
(c_{3}, c_{2}) 15 (d, h) 15 (m_{2}, m_{1}) 0
(c_{1}, b) 15 (d, j)  5  (m_{1}, z)  25
(c_{2}, b) 10 (g, h)  0  (m_{2}, z)  20
(c_{2}, d) 15 (h, j)  0

The corresponding minimal cut is S = {a, c_{1}, c_{2}, c_{3}, b, d, g, h, j}, T = {m_{1}, m_{2}, z}. Its’ capacity is given by

c(S, T) = c(g, m_{1}) + c(h, m_{1}) + c(h, m_{2}) + c(j, m_{2}) = 10 + 15 + 15 + 5 = 45, v.s.v..

F.3 Theorem 10.4 (17.4) in Biggs.

F.4 Let X denote the set of all permutations of {1, ..., 100}. So |X| = 100!. To simplify notation, put a := π(1), b := π(2), c := π(3). We consider three subsets of X, namely

A := {π ∈ X : a is adjacent to b},
B := {π ∈ X : a is adjacent to c},
C := {π ∈ X : b is adjacent to c}.

Then the number we wish to compute is simply |X\(A ∪ B ∪ C)|. By the Inclusion-Exclusion principle,

|X\(A ∪ B ∪ C)| = |X| − |A| − |B| − |C|
+|A ∩ B| + |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C|.

Note that, by symmetry,

|A| = |B| = |C|

and, similarly,

|A ∩ B| = |A ∩ C| = |B ∩ C|.

First, |A| = 2 · 99!. For there are two choices for the ordering of a and b (either ab or ba). Then we consider these as a single ‘number’, which leaves us with 99 ‘numbers’ to permute freely. Second, |A ∩ B| = 2 · 98!. For there are two possibilities for the ordering of a, b and c (either bac or cab). Then we consider these as a single ‘number’, which leaves us with 98 ‘numbers’ to permute freely. Third, |A ∩ B ∩ C| = 0, since it is not possible to position the three letters a, b, c so that each is adjacent to every other.

Putting it all together, we get our answer, namely

100! − 6 · 99! + 6 · 98!

F.5 (i) Theorem 5.1 (12.1) in Biggs. (ii) See my extra lecture notes for Day 7. (iii) See my extra lecture notes for Day 3.

F.6 Let

F (x) = ∑_{n=0}^{∞} u_{n}x^{n}

denote the generating function of the sequence (u_{n}). Let’s rock !

(2 − 7x + 3x^{2})F (x) = 2(u_{0} + u_{1}x) − 7(u_{0}x) + ∑_{n=2}^{∞}(2u_{n} − 7u_{n−1} + 3u_{n−2})x^{n}

= 2(1 + x) − 7x + ∑_{n=2}^{∞} 3^{n}x^{n}

= 2 − 5x + \frac{9x^{2}}{1 − 3x}

= \frac{24x^{2} − 11x + 2}{1 − 3x}.

Since

2 − 7x + 3x^{2} = (2 − x)(1 − 3x),

we conclude that

F (x) = \frac{24x^{2} − 11x + 2}{(2 − x)(1 − 3x)^{2}} .

We seek a partial fraction decomposition

\frac{24x^{2} − 11x + 2}{(2 − x)(1 − 3x)^{2}} = \frac{A}{2 − x} + \frac{B}{1 − 3x} + \frac{C}{(1 − 3x)^{2}} .  (1)

Clearing denominators, we have

24x^{2} − 11x + 2 = A(1 − 3x)^{2} + B(2 − x)(1 − 3x) + C(2 − x).

Gathering coefficients, we get the following system of linear equations to solve

( \begin{matrix}1 & 2 & 2 \\ 6 & 7 & 1 \\ 9 & 3 & 0 \end{matrix} ) ( \begin{matrix}A \\ B \\ C \end{matrix} ) = ( \begin{matrix}2 \\ 11 \\ 24 \end{matrix} ) .

After the usual Gauβ elimination and back substitution (I omit the details), we get the solution

A = \frac{76}{25}, B = −\frac{28}{25}, C = \frac{3}{5}.

Substituting into (1) and using the relations

\frac{1}{1 − t} = ∑_{n=0}^{∞} t^{n},

\frac{1}{(1 − t)^{2}} = ∑_{n=0}^{∞}(n + 1)t^{n},

we conclude that

F (x) = \frac{38}{25} ∑_{n=0}^{∞}(x/2)^{n} − \frac{28}{25} ∑_{n=0}^{∞}(3x)^{n} + \frac{3}{5} ∑_{n=0}^{∞}(3x)^{n}.

It follows that

u_{n} = \frac{38}{25} · \frac{1}{2^{n}} − \frac{28}{25} · 3^{n} + \frac{3}{5} · (n + 1) · 3^{n}.