3.5 Counting
-
I need to buy 7 fruit, and I can only buy apples, oranges or bananas. I have to buy at least one apple, one orange, and one banana. How many ways are there to do that?
Instead of counting collections of 7 fruits with restrictions, we can count collections of 4 fruits without restrictions.
\((a, b, c)<(a_1, b_1, c_1)\)
If either:
- \(a < a_1\)
- \(a=a_{1}\), and \(b<b_{1}\)
- \(a = a_1\), \(b = b_1\), and \(c < c_1\)
All possible configurations:
\(A=A_{0}\cup A_{1}\cup A_{2}\cup A_{3}\cup A_{4}\)
\(A_i := \{(i, j, k) \mid i + j + k = 4\}\)
Then \(|A|=5+4+3+2+1=15\) since this is disjoint
Smallest possible configurations:
\((0, 0, 4)\) \((0, 1, 3)\) \((0, 2, 2)\) \((0, 3, 1)\) \((0, 4, 0)\)
\((1, 0, 3)\) \((1, 1, 2)\) \((1, 2, 1)\) \((1, 3, 0)\)
\((2, 0, 2)\) \((2, 1, 1)\) \((2, 2, 0)\)
\((3, 0, 1)\) \((3, 1, 0)\)
\((4, 0, 0)\)
-
How many English words (any combination of letters) have length of exactly 5?
We can let \(L\) be the set of alphabets
Then \(\underbrace{L\times...\times L}_{5}=\left\lbrace\left(x,x,x,x,x\right):x\in L\right \rbrace\), thus \(\left|\underbrace{L\times...\times L}_{5}\right|=26^{5}\)
\(26^5\)
-
How many English words (any combination of letters) have length from 5 to 7?
\(26^5+26^6+26^7\)
Use the addition principle
-
How many English words (any combinations of letters) have exactly 5 letters, of which at least one is B?
Use subtraction principle
\(A\) be set of words with exactly \(5\) letters
\(B\) be set of words with exactly \(5\) letters none of these letters is B
Thus \(|A|=26^5,|B|=25^5\), then since \(B\subseteq A\), then \(|A\setminus B|=26^{5}-25^{5}=26^{4}+26^{3}\cdot25+26^{2}\cdot25^{2}+26\cdot25^{3} +25^{4}\)
This also indicate another way to count: Categorize by exact amount of \(b\).
-
How many English words (any combinations of letters) have exactly 5 letters, of which exactly one is B?
\(25^4\times 5\)
-
How many English words (any combinations of letters) have exactly 5 letters, of which at least two are B?
\(26^5-25^5-25^4\times 5\)
-
A bank card PIN-code has 4 digits, and has at most two 4’s from which the PIN-code must start. Example of possible PIN-codes are: 0353, 4076, 4412. How many attempts do we need to guess the PIN-code?
\(A_{1}=\{(4,4,c,d):c,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{2}=\{(4,b,4,d):b,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{3}=\{(4,b,c,4):b,c=\{0,1,2,3,5,...,9\}\}\)
\(A_{4}=\{(a,4,4,d):a,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{5}=\{(a,4,c,4):a,c=\{0,1,2,3,5,...,9\}\}\)
\(A_{6}=\{(a,b,4,4):a,b=\{0,1,2,3,5,...,9\}\}\)
\(A_{7}=\{(4,b,c,d):b,c,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{8}=\{(a,4,c,d):a,c,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{9}=\{(a,b,4,d):a,b,d=\{0,1,2,3,5,...,9\}\}\)
\(A_{10}=\{(a,b,c,4):a,b,c=\{0,1,2,3,5,...,9\}\}\)
\(A_{10}=\{(a,b,c,4):a,b,c=\{0,1,2,3,5,...,9\}\}\)
Thus we have \(|A_{1}|+|A_{2}|+\ldots+\left|A_{10}\right|\)
-
Fifteen people in the class are taking a maths exam, a physics exam, or both. It turns out that exactly eight people are taking maths and exactly ten people are taking physics. How many people are taking both exams?
\(15\) students in total — \(S\)
\(M \subset S\) — subset of students who take the math exam. 8
\(P \subset S\) — subset of students who take the physics exam. 10Find \(\#(M \cap P)\), the number of students who take both math and physics.
-
Six different soda varieties are offered at the shop. How many ways are there to choose two sodas to bring to a party?
\(6\times5\div2=15=\binom62\)
-
Six different soda varieties are offered at the shop. How many ways are there to choose three sodas to bring to a party?
\(6\times5\times4\div3\div2=20=\binom63\)
-
Several families attended a children’s party. Among the children, 6 are the only children in their families, and 8 have one sibling each. How many families were invited?
\(F=F_1\cup F_2\) \(|F|=6+\frac{8}{2}=10\)