MATH1081 Week 8
Question 1
A permutation of size k from a set of n distinct objects is any selection (without repetition) of those objects where the order of selection matters. The number of permtuations of size k from a set of n distinct objects is given by
Note that the Numbas syntax for P(n, k) is perm(n, k).
A combination of size k from a set of n distinct objects is any selection (without repetition) of those objects where the order of selection does not matter. The number of combinations of size k from a set of n distinct objects is given by
Note that the Numbas syntax for C(n, k) is comb(n,k).
a)
A student has 6 textbooks and wants to arrange 4 of them on a shelf. In how many ways can this happen?
b)
A student has 7 textbooks and needs to take 3 of them to class today. In how many ways can this happen?
c)
A student has 8 textbooks. They brought 5 of them to class, and then arranged 3 of these textbooks in a pile on their desk. In how many ways could this have happened?
Question 2
In the game of Scrabble, players arrange tiles with letters on them to create words. Each tile can only be used once in a word, but multiple tiles might show the same letter.
Recall that in combinatorics, a word is any string of letters (that does not necessarily have to mean anything in English).
a)
How many different 6-letter words can be made from the 10 tiles A, B, C, D, E, F, G, H, I, J?
b)
How many different 6-letter words can be made from the 10 tiles A, B, C, D, E, F, F, G, H, I?
c)
How many different 6-letter words can be made from the 10 tiles A, B, C, D, E, F, F, F, G, H?
Question 3
The number of ways to select k objects from n distinct types of object (with repetition allowed) where the order of selection matters is given by
The number of ways to select k objects from n distinct types of object (with repetition allowed) where the order of selection does not matter is given by
This latter formula comes from the "stars and bars" or "dots and lines" method of counting, where we are distributing k objects ("stars") amongst n -1 separating lines ("bars").
Recall that the Numbas syntax for C(n, k) is comb(n,k).
a)
A student must take 8 weekly quizzes, and in each quiz there are 7 different possible scores available. In how many ways can their individual quiz results appear in their gradebook?
b)
A student must take 8 courses to complete their degree, and they can be taken from 5 different faculties. In how many ways can the courses be distributed amongst the faculties?
Question 4
Often the main difficulty in solving a counting problem is identifying which counting techniques to apply. To see this, consider the following questions about counting different ways of distributing objects.
a)
9 distinct objects and 6 distinct containers are available. Exactly one object must be placed into each container. In how many ways can this be done?
b)
9 identical objects and 6 distinct containers are available. Exactly one object must be placed into each container. In how many ways can this be done?
c)
9 distinct objects and 6 identical containers are available. Exactly one object must be placed into each container. In how many ways can this be done?
d)
9 distinct objects and 6 distinct containers are available. Each object must be placed into a container. In how many ways can this be done?
e)
9 identical objects and 6 distinct containers are available. Each object must be placed into a container. In how many ways can this be done?
f)
5 distinct objects and 3 identical containers are available. Each object must be placed into a container. In how many ways can this be done?
Question 5
The number of solutions to the equation x1 + x2+…+ xn = k where x1, x2,..., xn ∈ N is given by
This can be deduced using the "stars and bars" method, which can be further modified to answer variations on this sort of question.
a)
How many solutions are there to the equation
where xi ∈ N for all i?
b)
How many solutions are there to the equation
where xi ∈ N and xi ≥ 4 for all i?
c)
How many solutions are there to the equation
where xi ∈ N and x, is even for all i?
d)
How many solutions are there to the equation
where xi ∈ N and xi ≤ 37 for all i?
Question 6
The pigeonhole principle states that given n objects to distribute amongst k containers, if k < n then at least one box contains at least 2 objects.
The generalised pigeonhole principle states that given n objects to distribute amongst k containers, at least one box contains at least objects.
Recall that for any real number z, its ceiling is the smallest integer greater than or equal to x.
a)
If 49 pigeons roost in 15 nests, then there must exist a nest with at least how many pigeons?
b)
Given that there are 9 nests, what is the smallest number of pigeons needed to guarantee that there are at least 3 pigeons roosting in at least one of the nests?
c)
Given that there are 33 pigeons, what is the largest possible number of nests needed to guarantee that there are at least 5 pigeons in at least one of the nests?
Question 7
A common style. of counting problem involves drawing from a deck of playing cards.
In a standard deck of playing cards, there are 52 different cards. Each card is one of 13 different values, and one of 4 different suits (of which there are 2 red suits and 2 black suits).
A hand of cards is a selection of cards from the deck, where the order they are selected in does not matter.
a)
How many 5-card hands contain cards of only one suit?
b)
How many 5-card hands contain four cards of the same value?
c)
How many 11-card hands contain four cards of the same value?
d)
A hand of 19 cards is selected from a standard deck of playing cards. At least one card value is guaranteed to appear at least how many times?