�

Lunds Universitet

Datavetenskapliga institutionen

DAT 401 – DM

Prov på delkurs Diskret Matematik

26 oktober kl 8-13 MA:10S

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 (Logic)

This exercise studies a new quantifier, ∃_{2}.

Let ∃_{2}x P (x) denote the quantification that there exist precisely two (no more, no less) x in the universe of discourse such that P (x) holds.

Determine the truth value of the following statements, where the universe of discourse is the integers. In each case, give a short reason for your answer (not a formal proof).

▶ a)[1] ∃_{2}x (x^{2} = 1) ▶ b)[1] ∃_{2}x (x = −x)

Determine the truth value of the following statements. In each case, give a short reason for your answer (not a formal proof).

▶ c)[1] ∃xP (x) → ∃_{2}xP (x) ▶ d)[1] (∃xP (x) ∧ ¬∀xP (x)) → ∃_{2}xP (x)

The following two questions are concerned with replacing the new quantifier ∃_{2} by the usual ones.

▶ e)[3] In this question (and only here) assume that the universe of discourse is {a, b, c}. Express the statement ∃_{2}xP (x) using only the logical operators negation, conjunction, and disjunction.

▶ f)[3] Express the statement ∃_{2}xP (x) using only ∀ and ∃ and the logical operators negation, conjunction, and disjunction.

Exercise 2 (Combinatorics)

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

The Stirling number of the second kind is written as \left\{{n \atop k}\right\}. It denotes the number of different ways to partition the set {1, 2, …, n} into k nonempty subsets.

For example, {1, 2, 3, 4} can be partitioned into 2 nonempty subsets in 7 ways:

{1, 2, 3} ∪ {4}, {1, 2, 4} ∪ {3}, {1, 3, 4} ∪ {2}, {2, 3, 4} ∪ {1},
{1, 2} ∪ {3, 4}, {1, 3} ∪ {2, 4}, {1, 4} ∪ {2, 3},

which shows that \left\{{4 \atop 2}\right\} = 7.

Things to note:

1. the partition {1, 2, 3, 4} ∪ ∅ is not on the list (we want nonempty subsets).

2. partitions like {1, 3, 2} ∪ {4} and {4} ∪ {1, 2, 3} are not on the list (they are considered the same as {1, 2, 3} ∪ {4}).

Also, to remove any doubts, we define \left\{{n \atop 0}\right\} = 0 and \left\{{n \atop n}\right\} = 1.

▶ a)[1] Find \left\{{4 \atop 3}\right\} by listing all ways to partition \{1, 2, 3, 4\} into 3 nonempty subsets.

▶ b)[1] Find \left\{{5 \atop 2}\right\}. ▶ c)[3] Find a formula for \left\{{n \atop 2}\right\} for n ≥ 2. ▶ d)[2] Give a combinatorial argument for the identity

\left\{{n \atop k}\right\} = k\left\{{n − 1 \atop k}\right\} + \left\{{n − 1 \atop k − 1}\right\},

when k > 0, n > 1. ▶ e)[3] (Difficult!) Prove by induction on n that if x > n is an integer then

∑_{k=0}^{n} \left\{{n \atop k}\right\} \frac{x!}{(x − k)!} = x^{n}.

Hint: There are many ways to solve solve this problem, but you may find the following manipulation (which is not hard to prove) useful:

x \frac{x!}{(x − k)!} = \frac{x!}{(x − k − 1)!} + k \frac{x!}{(x − k)!}

Exercise 3 (Recursion and Recurrences)

Recall that the n-clique K_{n} is the undirected graph with n nodes and all connecting edges, for example

K_{1} = ∘ K_{2} = \begin{matrix}∘ \\ ∘ \end{matrix} K_{3} = [figure: ∘; ∘; ∘] K_{4} = [figure: ∘; ∘; ∘; ∘]

Note that the number of edges in K_{n} is \binom{n}{2} = \frac{1}{2}n(n − 1).

This exercise studies a now family of graphs, which we will call cliquetree. The nth cliquetree T_{n} is defined recursively as follows.

1. T_{0} consists of a single vertex r, called the root, and nothing else.

2. T_{n} consists of a root r with two neighbours: r is connected to the root of T_{n−1} and to some vertex of K_{n}:

[figure: ∘; T_{n−1}; K_{n}]

Here are the first few cliquetrees:

T_{0} = ∘ T_{1} = [figure: ∘; ∘; ∘] T_{2} = [figure: ∘; ∘; ∘; ∘; ∘; ∘] T_{3} = [figure: ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘; ∘]

▶ a)[1] Draw T_{4} and T_{5} ▶ b)[2] Let v_{n} denote the number of vertices of T_{n}. Find a recurrence relation for v_{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} = 2a_{n−1} + n + 3 instead.)

▶ d)[1] Let e_{n} denote the number of edges of T_{n}. Find a recurrence relation for e_{n}. ▶ e)[3] Prove that e_{n} = \frac{1}{6} n^{3} + \frac{11}{6} n.