JA3. Combinatorics¶
Question 1¶
Imagine you received a scholarship that would cover only 3 courses out of the 11 courses related to your field of study at your university.
- How many ways will you have to choose the three courses
To choose k=3 courses out of n=11 courses, we are going to use the combinations formula as the order in which the courses are selected does not matter and the courses are not replaced after being selected.
Answer: C(11,3) = 165 ways.
- How many ways can you choose for the remaining two courses if one course- English (out of the 11 courses) is mandatory to take?
One course is mandatory to take with the scholarship, so we have to choose k=2 courses out of n=10 remaining courses. Per the reasoning in the previous question, we are going to use the combinations formula.
Answer: C(10,2) = 45 ways.
Question 2¶
Consider two sets A and B having cardinality of your choice. Explain how many injective and bijective functions are possible from set A to set B. Please avoid the examples given in textbooks or online resources and come up with your own unique example.
Let’s consider two sets A = {1,2,3} and B = {4,5,6}.
An injective function is a function between two sets, that is, every element from the first set (the domain) have exactly one element in the second set (the range). A surjective function is a function between two sets, that is, every element in the second set (the range) is mapped to by at least one element in the first set (the domain); in other words, no element in the second set is left unmapped. A bijective functions is a function that is both injective and surjective.
According to (Levin, 2021, p.82), the number of injective functions is n! where n is the cardinality of the domain set. In our case, the cardinality of the domain set is 3, so the number of injective functions is 3! = 6.
According to (Levin, 2021, p.83), the number of bijective functions is P(n,n) = n! where n is the cardinality of the domain set. In our case, the cardinality of the domain set is 3, so the number of bijective functions is 3! = 6.
Answer: 6 injective functions and 6 bijective functions.
Question 3¶
Find the coefficient of \(x^{7}\) in the expansion of \(x^{3} (x+2)^{10} + (x+5)^{7}\)
We are going to use the binomial theorem to find the coefficient of \(x^7\) in the expansion of \((x+2)^(10)\) and \((x+5)^7\) separately and then sum the results.
Answer: 13440 * x^3 + x^7
Question 4¶
A newly constructed apartment has 30 club members. The club has planned to create a sports committee consisting of 7 club members.
How many different sports committees are possible?
Since the ordering does not matter, we use combinations formula to find the number of different sports committees possible.
Answer: C(30,7) = 2035800.
How many committees are possible if it is mandatory to have the selected treasurer of the club members in the sports committee?
If one of the club members is mandatory to be in the sports committee, we have to choose k=6 members out of n=29 remaining members.
Answer: C(29,6) = 475020.
Question 5¶
i. Explain bit string in your own words.
A bit string is a sequence of 1s and 0s that represents a binary number. For example, the bit string 101 represents the binary number 5. A bit string has length which is the number of bits in the string, and weight which is the number of 1s in the string.
ii. Give an example of a bit string with any length and weight and explain how combinations help find the number of bit strings possible for the example.
Let’s consider a bit string of length n=5 and weight k=3. The number of bit strings with length n and weight k is C(n,k) = C(5,3) = 10.
iii. Choose a 3-digit number example and explain the number of derangements that can be formed from it.
Let’s consider the number 123. The number of derangements that can be formed from it is D(3) = 2, which are 213 and 321.
A Derangement is a permutation of the elements of a set, such that no element appears in its original position.
iv. To create a 4 digit- password for your Android phone, a. How many ways are there to crack the password if no digit repeats?
If no digit repeats, and the order does not matter, we are going to use the combinations formula to choose k=4 digits out of n=10 digits which is C(10,4) = 210.
Answer: 210 ways.
b. If the digits can be repeated, how many ways are there to crack the password?
If the digits can be repeated, and the order does not matter, we are going to use the n-multicombinations formula to choose k=4 digits out of n=10 digits which is 10*10*10*10 = 10^4 = 10000.
Answer: 10000 ways.
References¶
- Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. https://discretemath.org/ads/chapter_7.html
- Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0.