�

Lunds Universitet

Datavetenskapliga institutionen

DAT 401 – DM

Prov på delkurs Diskret Matematik

25 oktober 2001 kl 8–13 MA:10

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

This exercise considers undirected, simple graphs (no loops, no multiple edges). To make things easier, we assume that n is even.

In a balanced bipartite graph all edges are between the first n/2 vertices and the remaining n/2, for example:

G_{1} = [figure: 1; 2; 3; 4; 5; 6; 7; 8]

The maximum half-degree D(G) of such a graph is the largest degree among the first n/2 nodes. The above graph has D(G_{1}) = 3, because vertex 2 has degree 3. The minimum half-degree d(G) of such a graph is the smallest degree among the first n/2 nodes. The above graph has d(G_{1}) = 1, because vertex 3 has degree 1. Note that there is a vertex of smaller degree (namely, vertex 7), but that does not concern us: the half degrees are only interested in the bottom half of the vertices.

▶ a)[1] Find D(H) and d(H) for

H = [figure: 1; 2; 3; 4; 5; 6; 7; 8]

▶ b)[1] Draw a balanced bipartite graph G on 10 vertices with D(G) = 4 and d(G) = 0.

A random balanced bipartite (rbb) graph B(n, p) is defined like an ordinary random graph; it has an edge between vertex i and j with probability p, but of course only if i ≤ n/2 and j > n/2 (otherwise there can be no edge).

▶ c)[1] Find the probability that vertex 1 of an rbb graph has degree n/2. In symbols,

find p(d(v_{1}) = n/2). ▶ d)[1] Find the probability that vertex 1 of an rbb graph has degree m for 0 ≤ m ≤

n/2. In symbols, find p(d(v_{1}) = m). ▶ e)[2] Find the probability that an rbb graph has maximum half-degree n/2. In

symbols, find p(D(B(n, p)) = n/2). ▶ f)[3] Find the expected number of vertices (among the first n/2) of degree 1 in an

rbb graph. ▶ g)[1] (Harder) Find the probability that an rbb graph has the same maximum and

minimum half-degrees.

Exercise 2 (Combinatorics)

This exercise considers ways to distribute k identical candies among n children. Assume there are 3 children (Alice, Bob, and Chris) and 6 candies. We could

• give all 6 candies to Alice and no candies to Bob and Chris. Let’s write this as (6, 0, 0).

• give 4 candies to Alice and let Bob and Chris have one each: (4, 1, 1).

• be fair—every child receives 2 candies: (2,2,2)

• use many other combinations, here is a complete list

(6,0,0) (5,1,0) (5,0,1) (4,1,1) (4,2,0) (4,0,2) (3,3,0)
(3,2,1) (3,1,2) (3,0,3) (2,4,0) (2,3,1) (2,2,2) (2,1,3)
(2,0,4) (1,5,0) (1,4,1) (1,3,2) (1,2,3) (1,1,4) (1,0,5)
(0,6,0) (0,5,1) (0,4,2) (0,3,3) (0,2,4) (0,1,5) (0,0,6)

Note that there is no fairness: a single child may well receive all the candies, or no candies at all. However, all the candies must be distributed.^{1}

Thus we define the candy number \left[{n \atop k}\right] as the number of ways to distribute k candies among n children (n ≥ 1, k ≥ 0). We just showed that \left[{3 \atop 6}\right] = 28.

▶ a)[1] Show that \left[{2 \atop 5}\right] = 6 by listing all ways to distribute 5 candies among 2 children.

▶ b)[1] Find \left[{2 \atop 6}\right] and \left[{6 \atop 2}\right]. ▶ c)[1] Find a short formula for \left[{n \atop 1}\right]. ▶ d)[2] Find a short formula for \left[{n \atop 2}\right]. Explain. ▶ e)[3] This exercise asks you to give an argument for one of two identities. You can

choose which one you want to explain, and you will get points only for one of them (I’ll choose the best). Give a combinatorial argument for the identity

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

Alternatively, give a combinatorial argument for the identity

\left[{n \atop k}\right] = \left[{n − 1 \atop 0}\right] + \left[{n − 1 \atop 1}\right] + ⋯ + \left[{n − 1 \atop k}\right].

▶ f)[2] Prove

\left[{n \atop k}\right] = \frac{(n + k − 1)!}{(n − 1)!k!}

by induction in k, namely by showing that it satisfies the recurrence relation (1) from Question c and the formula for \left[{n \atop 1}\right] you found in Question e.

1You cannot choose to give 4 candies to Alice, 1 to Bob, and eat the remaining candy yourself.

Exercise 3 (Recursion and Recurrences)

The A-strings of length n are defined as follows:

• the A-strings of length 1 are ‘0’, ‘1’, and ‘A’.

• every bit string of length n is an A-string, and also every string that starts with an A and is followed by an A-string of length n − 1.

Here are all A-strings for small n:

n = 1 : 0, 1, A
n = 2 : 00, 01, 10, 11, A0, A1, AA
n = 3 : 000, 001, 010, 011, 100, 101, 110, 111, A00, A01, A10, A11, AA0, AA1, AAA.

▶ a)[1] Write all A-strings of length 4. ▶ b)[3] Let a_{n} be the number of A-strings of length n. Find a recurrence for a_{n}. ▶ c)[3] Solve the recurrence you found in the previous exercise. If you didn’t solve

the previous exercise, you can solve the following recurrence instead: a_{0} = 2, a_{n} = 2^{n} + a_{n−1} + n.

The B-strings of length n are defined as follows:

• the only B-string of length 1 is ‘1’.

• every bit string of length n is a B-string, unless it starts with 0 and the remaining n − 1 bits are a B-string of length n − 1.

Here are all B-strings for small n:

n = 1 : 1
n = 2 : 00, 10, 11
n = 3 : 001, 100, 101, 110, 111

Especially note that ‘01’ is not a B-string because it starts with 0 and ‘1’ is a B-string. Likewise, none of ‘000’, ‘010’, or ‘011’ are B-strings, because the start with 0 followed by B-strings of length 2.

▶ d)[1] Write all B-strings of length 4. ▶ e)[2] (Harder) Let b_{n} be the number of B-strings of length n. Find a recurrence for

b_{n} and solve it.