Discrete Mathematics for Computer Scientists -- Exercises Week 8 - CombinatoricsDIT980, HT 2015
Home | Schedule | Assignments | Exercises | Exam | AboutFire | Forum | TimeEdit | Links | 2014
Exercises Week 8 - Combinatorics

Here are some answers for the exercises.

Exercises

1. For 2 dice, here are a total of 36 possibilities. The number of possibilities we are interested in is 30. So, 30/36=5/6.

For 3 dice, there are a total of 6x6x6=216 possibilities. The number of possibilities we are NOT interested in is 6x5x4=120 (when they are all different). The number of possibilities we are interested in is thus 6x6x6-6x5x4 = 96. The probability is thus 96/216 = 4/9.

This probability is 120/216 = 5/9.

For n <= 6, this probability is (T-B)/T. Here, T=6^n, and B=6!/(6-n)!. When n > 6, the probability is 1.

2. For each group, we have 23*23 + 10*10 possibilities (either two letters or two digits). The total number is then (23*23 + 10*10)^3, because we have 3 groups. The answer is 248858189.

3. The result is a fraction where we divide p! by (p-k)!k!. Here, both k and p-k are smaller than p. All prime factors of (p-k)!k! are therefore smaller than p. This means that there is no prime factor q of (p-k)!k! that divides p. Since p! is divisible by p, after dividing it by (p-k)!k! it is still divisible by p.

4. Consider a bar of chocolate with N pieces in a row. We would like to hack it up into 3 parts, with x, y, and z pieces each. In this way we know that x+y+z=N. We can hack the chocolate bar at N-1 possible places (one place between each piece). We have to hack 2 times to get three pieces (2 times, at two different places). Thus, the number of ways we can divide N into x,y, and z, is the same as the number of ways we can choose 2 hack positions out of N-1. The answer is thus:

 ( N-1 ) 2
If N=10 (as in the exercise), the answer is 36.

 ( n ) k
The reason is that constructing a strictly sorted list of length k is the same as picking k different elements (and then sorting them). Each different subset of k elements will give rise to a different sorted list. So, the answer is the same as the number of ways we can pick k elements from n elements.

When n=5 and k=3 (as in the exercise), the answer is 10.

6. The proof of the step case can be completed as follows. All congruences are (mod p).

 (k+1)p = kp + ...STUFF... + 1p [ by binomial expansion ] = kp + ...STUFF... + 1 [ basic arithmetic ] ≡ kp + 1 [ all the ...STUFF... is divisable by p ] ≡ k + 1 [ I.H. (see exercise text) ]

To see why all the ...STUFF... is divisable by p, consider exercise 3. Every term in the expansion is of the form:

 ( p )·kr r
where p is prime and 0 < r < p. According to exercise 3, these are all divisible by p.

To see the whole proof in text, Proof of Fermat's little theorem using the binomial theorem.

7.

 ( n ) + ( n ) k k+1

 = n! + n! [ definition of choose function ] k!(n-k)! (k+1)!(n-k-1)!

 = (k+1)n! + n!(n-k) [ multiply by (k+1) and (n-k), respectively ] (k+1)k!(n-k)! (k+1)!(n-k-1)!(n-k)

 = (k+1)n! + n!(n-k) [ (k+1)k! = (k+1)!, and (n-k-1)!(n-k) = (n-k)! ] (k+1)!(n-k)! (k+1)!(n-k)!

 = (k+1)n! + n!(n-k) [ bring together both fractions ] (k+1)!(n-k)!

 = n!((k+1) + (n-k)) [ break out n! ] (k+1)!(n-k)!

 = n!(n+1) [ simplification ] (k+1)!(n-k)!

 = (n+1)! [ n!(n+1) = (n+1)! ] (k+1)!(n-k)!

 = (n+1)! [ simple arithmetic ] (k+1)!((n+1)-(k+1))!

 = ( n+1 ) k+1

8. There are 54 spots to deal out, divided over 9 groups. Let us pick the first person that should get a spot: you. We pick a group for you, let us call that group G1. In G1, there are 5 more spots (there were 6 and you got 1). You would like your secret love to get one of those 5 spots. There are 53 (54-1) spots left in total to give out. The probability is thus 5/53: 5 possibilities out of a total of 53 are good.

9. Consider graphs with n nodes. How many possible edges can we draw? Well, an edge is a choice of 2 nodes (out of n), so there are

 ( n ) 2
possible edges to draw. Any graph with n nodes is going to choose a subset of these.

If we have a possible number of k edges, we can draw

2k
possible graphs, because every graph is characterized by a particular subset of edges it chooses to draw, and there are 2k such subsets.

Putting these two together, given n nodes, there are

 2 ( n ) 2
possible graphs we can draw.

Here is a little table.

 n #edges #graphs 1 0 1 2 1 2 3 3 6 4 6 64 5 10 1024 6 15 32768

10. We are talking about a directed graph where every node has one incoming edge. This means that there is no topological ordering (no node can be first in such an ordering). This means that there must be a cycle. So, the probability of a cycle is 1, or 100%.