CS计算机代考程序代写 discrete mathematics School of Mathematics and Statistics

School of Mathematics and Statistics

MAST30012 Discrete Mathematics 2021

Assignment 1 – Solutions

Q1: We first state an equivalent counting problem and then give the answer.

(a) This is equivalent to choosing a subset of size 5 (the people given apples ) from
a set of size 12. The answer is: (

12

5

)
=

12!

7! 5!
.

(b) This is like distributing 16 balls (people) into 3 boxes (oranges, pears and
bananas) with 7 balls in box 1, 4 balls in box 2, and 5 balls in box 3. The
answer is (

16

7, 4, 5

)
=

16!

7! 4! 5!
.

(c) The distribution of each type of fruit (oranges or apples) is independent.

The distribution of a particular type of fruit is the problem of sampling with
replacement (think of people as labelled boxes and fruit as identical balls) so
the oranges can be distributed in:(

20 + 6− 1
6

)
=

(
25

6

)
ways, while the apples can be distributed in(

20 + 12− 1
12

)
=

(
31

12

)
ways. By the multiplication principle the oranges and apples can then be
distributed in (

25

6

)(
31

12

)
ways.

(d) Each integer can be represented as an n-tuple or as a word of length n with
entries from {0, 1, . . . , 9}. In the case n = 3 we would have 7 = (0, 0, 7), 389 =
(3, 8, 9), 1000 = (0, 0, 0) etc. with the entries being the coefficients in the base
10 expansion of the integer. There are 10n tuples and in each position (column)
of the n-tuples there will be 10n−1 occurrences of the digit 3. Since there are
n positions we would write down the digit 3 a total n10n−1 times.

Q2: In each case we make use of the probability axiom. Let T be the set of possible
outcomes and F the set of favourable outcomes. Assuming each outcome is equally
likely, the probability of F is:

Pr(F ) =
number of favourable outcomes

total number of outcomes
=
|F |
|T |

.

Now each roll of five dice can be represented as a five tuple (we distinguish between
the dice) with entries 1, 2, 3, 4, 5 or 6. Hence |T | = 65 = 7776.

(a) Five of a kind can be achieved in 6 ways. Hence

Pr(Five of a kind) =
6

65
=

1

64
≈ 0.0771%.

(b) The required dice values can appear in any order. Hence |F | = 5! is the
number of permutations of 2, 3, 4, 5, 6, and

Pr(A large straight) =
5!

65
≈ 1.543%.

(c) The number of different full-houses is 6× 5 = 30 (6 choices for three of a kind
and 5 for two of a kind). The three dice of the same value can be placed in(
5
3

)
= 10 positions. Hence

Pr(Full-house) =
300

65
≈ 3.858%.

(d) We partition F into 4 cases: Five of a kind, Four of kind and one other, Full-
house, and Three of a kind and two distinct other dice.

Four of kind and one other can occur in 6×5×5 = 150 ways (30 combinations
of dice and 5 configuration in each case).

Three of kind and two distinct other dice can occur in 6× 5× 4×
(
5
3

)
= 1200

ways.

Hence |F | = 6 + 150 + 300 + 1200 = 1656 and

Pr(Three of a kind) =
1656

65
≈ 21.296%.

(e) The only way two of a kind cannot occur is that all dice show distinct values.
This can happen in (6)5 = 6! ways. So |F | = 65−6! = 7056 by the complement
principle and hence

Pr(Two of a kind) =
7056

65
≈ 90.74%.

Alternative Solution: Two of a kind obviously appear in any configuration
with three of a kind. There are two further cases two pairs and a distinct third
(as in 22445) or two of a kind and three distinct others as in (55136).

Two pairs and a distinct third: 6× 5× 4/2 possible combinations (divide by 2
to avoid counting combinations of pairs twice) and for each combination

(
5
2

)(
3
2

)
configurations. In total there are 1800 possibilities.

Two of a kind and three distinct others: 6×5×4×3 possible combinations and
for each combination

(
5
2

)
configurations (note configurations of the distinct 3

are already counted via the combinations). In total there are 3600 possibilities.

Adding it all up we get 1656 + 1800 + 3600 = 7056 as before.

Note that had we not already done the hard work with three of a kind the
complement way is so much easier.

Q3: A configuration of leaders is an m-tuple with n possible distinct ‘values’ (students)
per entry.

(a) With no constraint there are nm ways of choosing the leaders.

(b) There are (n−k)m ways of choosing the leaders if a group a size k are excluded
from leading.

(c) Let L = {1, 2, . . . , n} denote the set of possible leaders and Lj = L\{j} the set
of leaders with student j excluded. The set of configurations in which every
student gets to lead at least once is the complement of Lm with

⋃n
j=1 L

m
j since

Lmj is the set of configurations where student j never gets to lead on any of the
m days. So

S(m,n) = |Lm| −

∣∣∣∣∣
n⋃

j=1

Lmj

∣∣∣∣∣
Use the inclusion-exclusion theorem

= nm −
n∑

k=1

(−1)k−1

{s1,…,sk}⊂{1,2,…,n}

|Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk |

Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk is a set with k students s1, s2, . . . , sk excluded so

|Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk | = (n− k)

m and there are

(
n

k

)
such subsets.

= nm −
n∑

k=1

(−1)k−1
(
n

k

)
(n− k)m

=
n∑

k=0

(−1)k
(
n

k

)
(n− k)m.

(d) You didn’t try to show this using the formula, did you? Combinatorially, this
is easy!

If there are fewer days than students, then clearly it is impossible to have a
configuration in which every students leads at least once. Hence S(m,n) =
0, m < n. When m = n there are n days and n students. Every permutation of the students is a valid configuration and hence S(n, n) = n!. Note: This is a famous result since S(m,n) counts the number of onto functions from a set of size m to a set of size n. Q4: (a) Given a group of 33 students choose a committee of size 12 with a subcommittee of size 6 and from these six an executive committee of size 3. LHS: Choose the 12 students for the committee in ( 33 12 ) ways. From the com- mittee of 12 choose a subcommittee of size 6 in ( 12 6 ) , and finally choose the executive committee of size 3 in ( 6 3 ) ways. The choices at each step are inde- pendent and the result follows. RHS: Choose the executive committee of size 3 from all students in ( 33 3 ) ways. Then choose the remaining 3 members of the subcommittee from the remaining 30 students in ( 30 3 ) ways. Finally, choose the remaining 6 members of the committee in ( 27 6 ) ways. Note how you can now derive endless lists of binomial identities such as in this case ( 33 12 )( 12 6 )( 6 3 ) = ( 33 6 )( 27 6 )( 6 3 ) = ( 33 9 )( 9 3 )( 24 3 ) = · · · (b) This is a generalisation of the ‘Vandermonde at the ice cream parlour’ example from lectures. An ice cream parlour serves n flavours. How many different ice cream platters are there with k scoops of ice cream. LHS: (( n k )) by definition using sampling with replacement or multi-choice. RHS: We partition on the number m ≤ k of distinct flavours. The m flavours can be chosen in ( n m ) ways and we take one scoop of each. Then we multi- choose the remaining k −m scoops from the m flavours in (( m k−m )) ways. We then sum over the number of chosen flavours while appealing to the addition and multiplication principles. Alternatively: Distribute k oranges to n children with no constraint on how many oranges a child may get. LHS: (( n k )) by definition. RHS: Condition on the number, m, of children who gets at least one orange. We choose m children in ( n m ) ways and give each child an orange. Next dis- tribute the remaining k −m oranges among the m children in any way. Sum over the number of chosen children. (c) Choose subsets of size k + 1 from the set {1, 2, . . . , n, n + 1}. LHS: By definition, ( n+1 k+1 ) is the number of subsets. RHS: Condition on the largest number m + 1 in the subset. The remaining k elements can be chosen in ( m k ) ways from {1, 2, . . . ,m}. Now m + 1 can range from k + 1 to n + 1 and the result follows by the addition principle.