CISC102 Winter 2024
Quiz 3: Counting Reminders
。Answer each question to the best of your abilities, and show all of your work
。You may use your notes from class but are prohibited from using external resources.
。You must handwrite your solutions. Electronic solutions will automatically receive a 0
Insufficient justification will result in a loss of marks.
Questions
1. (2 marks) Summarize the different counting methods in the chart below by indicating the correct formula when selecting k items out of n total items given the properties indicated (order, repetition).
2. (2 marks) Give a scenario for something you can count that would yield the following count:
3. (3 marks) There are 51 houses on a street. Each house has an address between 1000 and 1099, inclusive. Show that at least two houses have addresses that are consecutive integers.
4. (4 marks) Determine the counts for the following data structures in the described scenarios [Hint: Use summations where appropriate]:
(a) The number of LISTS of all possible lengths between 0 and k, where the elements are chosen from a selection of n > k objects.
(b) A Python dictionary {‘key’:‘value’} is stored as an unordered collection of key- value pairs, where the key’s cannot be repeated, but the values may be repeated. How many dictionaries with 10 entries can we make, if there are 15 possible keys and 12 possible values?
5. (3 marks) What is the coefficient on the term in the binomial expansion of (you do not need to expand your answer):
6. (4 marks) Prove the following equality algebraically using the factorial definition of choose:
7. (6 marks) How many anagrams (ignoring spaces) are there of
COMPSA IS A COOL CLUB
that contain “MAPS” in any order?
8. (6 marks) How many lattice paths are there between A and B that pass through C but avoid D and E?
9. (6 marks) In a bag of marbles you have 15 red marbles, 9 green marbles, and 12 blue marbles. How many ways can you select 9 marbles so that: at least 3 are blue?