Q. The Carleton Computer Science Society has a Board of Directors consisting of one president, one vice-president, one secretary, one treasurer, and a three-person party committee (whose main responsibility is to buy beer for the other four board members). The entire board consists of seven distinct students. If there are n >= 7 students in Carleton's Computer Science program, how many ways are there to choose a Board of Directors? Justify your answer.
Q. Let A be a set of size m, let B be a set of size n, and assume that n > = m >= 1.
How many functions f : A à B are there that are not one-to-one? Justify your answer.
Q. : In a group of 20 people,
- 6 are blond,
- 7 have green eyes,
- 11 are not blond and do not have green eyes.
How many people are blond and have green eyes? Justify your answer.
Q. Let n _>=1 be an integer. Use the Pigeonhole Principle to prove that in any set of n + 1 integers from {1; 2; : : : ; 2n}, there are two integers that are consecutive (i.e., differ by one).
Q. Let n >= 1 be an integer and consider n boys and n girls. For each of the following three cases, determine how many ways there are to arrange these 2n people on a straight line:
- All boys stand next to each other and all girls stand next to each other.
- All girls stand next to each other.
- Boys and girls alternate. Justify your answer.
Q: Let m >= 1 and n >= 1 be integers. Consider a rectangle whose horizontal side has length m and whose vertical side has length n. A path from the bottom-left corner to the top-right corner is called valid, if in each step, it either goes one unit to the right or one unit upwards. In the example below, you see a valid path for the case when m = 5 and
n = 3.
How many valid paths are there? Justify your answer.
Q. Let n and k be integers with n >= k. How many solutions are there to the equation x1 + x2 + _ _ _ + xk = n;
where x1 >=1, x2 >=1, . . . , xk >= 1 are integers? Justify your answer.
Q. Let n >= 66 be an integer and consider the set S = {1; 2; : : : ; n}.
- Let k be an integer with 66 <= k <= n. How many 66-element subsets of S are there whose largest element is equal to k?
- Use the result in the first part to prove that
