CSE2133 - Discrete Mathematics¶

Counting¶

Q7(a): Prove the generalized Pigeonhole principle.
Q7(b): What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?
Q7(c): Suppose that either a member of the mathematics faculty or a student who is mathematics major is chosen as a representative to a university committee. How many different choices are there for this representative, if there are 37 members of the mathematics faculty and 83 mathematics majors and no one is both a faculty member and a student?
Q7(d): Let X denote a digit that can take any of the values 0 through 9, let N denote a digit that can take any of the values 2 through 7, and let Y denote a digit that must be 0 to 2. The formats of the area code, office code, and station code are NYX, NNX, and XXXX. How many different North American telephone numbers are possible under the plan?

Q3(a) [5]: Using Pascal's Triangle find the value of \((a-b)^6\).
Q3(b) [5]: A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag if two must be white and two red.
Q3(c) [4]: Using the Pigeon hole principle solve the following problem: Find the minimum number of students needed to guarantee that five of them belong to the same class (Freshman, Sophomore, Junior, Senior).
Q4(c) [5]: Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or digit. Each password must contain at least one digit. How many possible passwords are there?
Q4(d) [3]: A sequence of 10 bits is randomly generated. What is the probability that at least one of these bit is 0?

Q4(a): A class contains 10 students with 6 men and 4 women. Find the number of ways to: (i) Select a 4-member committee from the students. (ii) Select a 4-member committee with 2 men and 2 women. (iii) Elect a president, vice president, and treasurer.

Q3(c) [7]: Suppose A and B are playing a tennis tournament such that the first person to win two games consecutively or who wins a total of three games wins the tournament. Find the number of ways the tournament can proceed (use rooted tree).
Q4(a) [5]: Using Pascal's Triangle find the value of \((a+b)^6\).
Q4(b) [5]: A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag if two must be white and two red.
Q7(b) [6]: Using the Pigeon hole principle solve the following problem: Find the minimum number of students needed to guarantee that five of them belong to the same class (Freshman, Sophomore, Junior, Senior).

Q4(b): Using the Pigeon hole principle solve the following problem: (i) Find the minimum number of students in a class to be sure that three of them are born in the same month. (ii) Find the minimum number of students needed to guarantee that five of them belong to the same class (Freshman, Sophomore, Junior, Senior).
Q4(c): A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag, if two must be white and two red.