�

Lunds Universitet

Datavetenskapliga institutionen

DAT 401 – DM

Prov på delkurs Diskret Matematik

23 november kl 8–13 MA:8

Tillåtna hjälpmedel: Litteratur, egna anteckningar

Tentamen består av 3 uppgifter, varje uppgift kan ge 10 poäng. Deluppgifternas poäng anges inom [hakparenteser]. Observera att poänggivningen inte nödvändigtvis avspeglar deluppgiftens svårhetsgrad. Uppgifterna kan besvaras på svenska eller engelska.

Behandla högst en uppgift per papper (det går bra att behandla deluppgifter på samma papper). Skriv bara på ena sidan och markera varje sida med dina initialer. Skriv läsligt.

▶ a)[0] Hur många uppgifter får man behandla per papper? ▶ b)[0] Får man skriva på baksidan?

Det går bra att referera till kursboken av Rosen eller Husfeldts anteckningar. Referenser måste ha formen [R: något] eller [H: något], där något är ett avsnittsnummer, en kodbit, en räknad uppgift, etc. Skriv till exempel “genom att använda Lemma [R:7.4]”.

Exercise 1 (Functions and Relations)

Let F be the set of functions from the set of integers to the set of real numbers. Define the relation R ⊆ F × F by

(f, g) ∈ R if and only if f(n) is O(g(n)).

For example, we have (2x^{2} + 5, x^{2}) ∈ R because 2x^{2} + 5 is O(x^{2}).

▶ a)[1] Is it true that (2n, n) ∈ R? ▶ b)[1] Is it true that (4^{n}, 2^{n}) ∈ R? ▶ c)[3] Prove that ((n^{2} + 6)/(n + 2), n) ∈ R by showing that (n^{2} + 6)/(n + 2) is O(n).

Use Definition 1.8.1 for this; remember to find the constants C and k. ▶ d)[1] Is R reflexive? If yes, give a brief explanation (not a formal proof). If no,

give a counterexample. ▶ e)[1] Is R transitive? If yes, give a brief explanation (not a formal proof). If no,

give a counterexample.

Define the relation S ⊆ F × F by (f, g) ∈ S if and only if (2^{f}, 2^{g}) ∈ R.

▶ f)[3] Prove or disprove: R ⊆ S.

Exercise 2 (Combinatorics)

In this exercise k and n are integers with n > 1 and 1 ≤ k ≤ n.

We consider the different ways to arrange numbers on cycles. Here are five number on a cycle in three different ways:

[figure: 1; 2; 3; 4; 5; 1; 3; 2; 4; 5; 1; 3; 5; 4; 2]

For typographic reasons We write such a cycle in clockwise ordering in square bracktes, so the three examples are [1, 5, 4, 3, 2], [1, 5, 4, 2, 3], and [1, 2, 4, 5, 3]. Note that it does not matter where we start, so

[1, 5, 4, 3, 2] = [5, 4, 3, 2, 1] = [4, 3, 2, 1, 5] = [3, 2, 1, 5, 4] = [2, 1, 5, 4, 3].

On the other hand, the orientation does matter, so [5, 4, 3, 2, 1] ≠ [1, 2, 3, 4, 5]. Just to make sure: a single element can form a cycle by itself, like [1]. There is only one cycle with two elements, namely [1, 2] = [2, 1]. There are two different cycles with three elements, [1, 2, 3] and [1, 3, 2].

There are 11 different ways to make 2 cycles out of 4 elements:

[1, 2, 3][4]  [1, 2, 4][3]  [1, 3, 4][2]  [2, 3, 4][1]
[1, 3, 2][4]  [1, 4, 2][3]  [1, 4, 3][2]  [2, 4, 3][1]
[1, 2][3, 4]  [1, 3][2, 4]  [1, 4][2, 3]

In general, the number of different ways to make k cycles out of n elements is denoted \left[{n \atop k}\right], called the Stirling number of the first kind. Our example just showed \left[{4 \atop 2}\right] = 11. We also saw that \left[{1 \atop 1}\right] = 1, \left[{2 \atop 1}\right] = 1, and \left[{3 \atop 1}\right] = 2.

▶ a)[1] Show that \left[{4 \atop 3}\right] = 6 by listing all ways to partition \{1, 2, 3, 4\} into three cycles.

▶ b)[1] Find \left[{4 \atop 1}\right]. ▶ c)[2] Find a short formula for \left[{n \atop 1}\right] for n ≥ 2. ▶ d)[2] Is it true that the Stirling number of the first kind is symmetric around the

middle, i.e.,

\left[{n \atop k}\right] = \left[{n \atop n − k}\right]? (1 ≤ k ≤ n)

If yes, give proof. If no, give a counterexample. ▶ e)[2] Give a combinatorial argument for the identity

\left[{n \atop k}\right] = (n − 1)\left[{n − 1 \atop k}\right] + \left[{n − 1 \atop k − 1}\right], (k > 1, n > 2).

▶ f)[2] (Difficult.) Find a short formula (two symbols) for

∑_{k=1}^{n} \left[{n \atop k}\right].

Explain your answer (don’t give a formal proof).

Exercise 3 (Recursion and Recurrences)

In this exercise we let b(n) denote the binary expansion of n ≥ 0. For example

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ⋯ \\ b(n) & 0 & 1 & 10 & 11 & 100 & 101 & 110 & 111 & 1000 & ⋯ \end{matrix}

It can be shown that b(n) has length ⌈log_{2}(n + 1)⌉.

We define a family of strings s_{n} over {0, 1, ∗} as follows:

1. s_{0} is a zero followed by a star: s_{0} = 0∗,

2. for n > 0, we construct s_{n} by concatenating s_{n−1} with the binary expansion of n and n + 1 stars:

s_{n} = s_{n−1} b(n) \underbrace{⋆⋆⋆⋆ ⋯ ⋆}_{n + 1 stars}

For example,

s_{0} = 0⋆,
s_{1} = 0⋆1⋆⋆,
s_{2} = 0⋆1⋆⋆10⋆⋆⋆,
s_{3} = 0⋆1⋆⋆10⋆⋆⋆11⋆⋆⋆⋆
s_{4} = 0⋆1⋆⋆10⋆⋆⋆11⋆⋆⋆⋆100⋆⋆⋆⋆⋆

▶ a)[1] Write s_{5}. ▶ b)[2] Let a_{n} denote the number stars in s_{n}. Find a recurrence relation for a_{n}. ▶ c)[3] Solve the recurrence relation that you found in the previous question. (If

you don’t have an answer for the previous question, you can solve a_{0} = 1, a_{n} = a_{n−1} + 2n + 2 instead.)

▶ d)[1] Let l_{n} denote the length of s_{n}. (So l_{0} = 2 and l_{2} = 10, for example). Find a

recurrence relation for l_{n}. ▶ e)[3] Prove that l_{n} ≤ \frac{1}{2} n^{2} + n log n + 3n + 2 for n ≥ 3.