MATH21: Counting(Lec1-3)
Experiment 1: How many people are there is the class room
Product rule
Ex: Mayan calender has Tones and 20 Solar signs. How many days are there in a year?
Ans: 13 * 20 = 260
formally, For any sets, A and B:
| $ | A \times B | = | A | B | $ (Rosen p.386) |
Ex: Kin = 1 day, Uinal = 20 kin, Tun = 18 Uinal, Katun = 20 Tun, Batun = 20 Katun. How many days are there in one Baktun?
Ans = 20 * 20 * 18 * 20
1 Baktun = 20 Katun = 20 * (20 Tun) = 20 * 20 (18 Uinal) = 20 * 20 * 18 * (20 kin )
Ex: Today is 13 Kin, 6 Uinal, 6 Tun, 0 Katun, 13 Baktun. How many days since the Mythical maya creation day?
Ans: ~ 3100 B.C.
13 Baktun = 13 * (20 * 20 * 18 * 20) Kin
6 Tun = 6 * (18 * 20) Kin
13 Kin
Just sum them up
Sum rule
Ex: Another calender has 20 names symbols and 19 month symbols. How many symbols are there?
Ans = 20 + 19
Formally,
For any disjoint set $A$ and $B$:
| $ | A+B | = | A | + | B | $ |
| $ | A \cup B | = | A | + | B | $ |
Speed up counting
To speed up counting, break a big group into disjoint sets, count them seperately. (That’s what they do in the experiment)
More practice
Ex: Making your own game avatar, there are 8 hair styles and 8 hair colors. How many possible styles are there?
Ans = 8 * 8
Ex: Other than 96 possible custom Miis, a player can choose one of 10 preset characters.
Ans = 96 + 10
Technique to count things
Count smaller subsets
Ex: A binary string of length string n. How many possible binary strings $BS(n)$?
Ans: 2 ^ n
- Count by small subset!
$BS(0)=1$
$BS(1)=2$
$BS(2)=4$
-
Now you find the pattern.
-
Prove the pattern
Product rule
Now we have n sets.
We are actually doing:
$ {0,1} \times {0,1} \times $ for $n$ times.
| Therefore we have $ | {0,1} | = 2$ |
Sum rule
Split into disjoint subset. 1 subset starts with 0 and the other 1.
Then select the second bit, the third….. until…
$B(n) = B(n-1) + B(n-1) = 2 \times B(n-1)$
$B(0) = 1$
Here we have the recursion. Do the induction!
More Exercise
Ex: We have 3 different ice-cream cones and 20 different flavors. How many kinds of ice-cream can we make?
Ans: Product rule = 3 * 20
Ex: Now we have complicated ice-cream shop. Instead of just having a single scoop, People can choose to covert them into a sundae with 1 of two different sauce, and whipped cream and cherries are options. How many kinds of possible desserts?
Ans: 320 + 32022*2
Ex: There are 5 vowels and 21 consonants in English. How do I build a 4-letter word with 1 vowel and 3 consonants?
Ans: $4 * 21 ^ 3 * 5$
When sum rule fails: Inclusion-Exclusion Principle
for 2 sets:
| $ | A \cup B | = | A | + | B | - | A \cap B | $ |
for three sets:
| $ | A \cup B \cup C | = | A | + | B | + | C | - |
| ( | A \cap B | + | B \cap C | + | C \cap A | ) |
-
A \cap B \cap C $
for $n$ sets:
Ex: How many length n bit strings are there that start with 1 or end with 00?
Ans:
- start with 1: $ 2^{n-1} $
- ends with 00: $ 2^{n-2} $
- both happens: $ 2^{n-3} $
- finally, $ 2^{n-1} + 2^{n-2} - 2^{n-3} $
Ex: How many 6-digit strings
- begin with an even number OR
- end in 0 OR
- only onsist of digits less than 5?
Ans:
-
$ 5 * 10^5 $
-
$ 10^5 $
-
$ 5^6 $
1 AND 2: $ 5 * 10 ^4 $
2 AND 3: $ 5^5 $
3 AND 1: $ 3 * 5^5 $
1 AND 2 AND 3: $3 * 5^4 $
Ex: How many 4-digit strings have at least one 0?
Ans:
All 4-digits: $10^4$
All 4-digits w/o 0: $9^4$
Finally, $10^4 - 9^4$
Why $4*10^3$ is not correct?
Ex: How many 4-digit string have at least two consecutive digitis that are the same?
all 4 digits: $10^4$
all 4 digits with no same neighbors = $10 * 9^3$
Permutation: ordering of n distinct objects
$ n! = n * (n-1)….1 $
r-Permutations(nPr): arrange r objects out of n distinct objects and order it
$P(n,r) = n(n-1)(n-2)…(n-r+1) = n!/(n-r)!$
Think of it as:
_ _ _ _ _ _having $r$ spots, $n$ different choices.
for spot 1, we can choose from $n$ choices
for spot 2, we can choose from $n-1$
…
all the way to spot r, we can choose from $n-r+1$
Or, we order all $n$ of them, there are $n!$ permutations.
But now the spots after $r$ is not important at all => need to remove these difference. These difference are $(n-r)!$
Ex: n different marbles, number of ways to order the top 5 marbles.
Ans: $P(n,5) = n(n-1)(n-2)(n-3)(n-4)$
Ex: Planning a trip to 7 different cities, how many ways the trip can be arranged with each city visited only once?
Ans: $7!$
Ex: if I only have money for 5 cities.
Ans: $P(7,5) = 7 * 6 * 5 * 4* 3$
Ex: what if I must start in New York and end in Seattle? (only have money for 5 cities)
Ans:
New York, _, _ , _, Seattle.
We can only choose 3 out of 5 and order them.
$P(5,3) = 543$
Ex: what if we must start in New York, and must end in Seattle. Plus must visit LA after SD? (visit all 7 cities, now I am rich)
Ans:
New York, _, _, _, _, _, Seattle.
But LA must go with SD –> NY, ,,_,__,Seattle.
$4!$
The travelling salesperson problem with distance matrix
Now we have a matrix of of distances between cities. How to we minimize the distance traveled?
- Exhaust all $7!$ ways: take so much time!
CSE101 has a better solution
Back to ice-cream again
Ex: n differen flavors. Make a 2-scoop icecream in which the two scoop must be of different flavor. (the order DOES matter)
Ans: _, _ for 2 scoops. $P(n,2) = (n)(n-1)$
Object symmetries
Ex: What it the order doesn’t matter any more?
Ans: $n(n-1)/2$ becuase for 2 different flavors, there are $2$possible orders (you count twice).
Ex: we have three sticks, red, orange and yellow. How many ways we can use them to create a triangle?
Ans:
$3!$ is not correct because red-orange-yellow is the same as yellow-red-orange (rotate the triangle)
red-orange-yellow is the same as red-yellow-orange (flip the triangle)
only $1$ ways.
where does that come from?
No. of theoretical object = $3!$
No. of symmetry = # of transformation = (3 rotate)(2 flips) = 6
finally, $3!/{3*2}$
Ex: Now we have 4 sticks of different colors, how many squares can we make?
Ans:
No. of theoretical objects: $4!$
No. of symmetry = (4 rotate)(2 flips)
Finally, $4!/{4*2} = 3$
Ex: How many different arrangements with a 333 rubik’s cube?
Ans:
There are $27$ cublets. But you can’t rearrange the cubes like that.
There are $8$ corners(3 colors), $12$ edges(2 colors), $6$ center(they don’t move). (and $1$ in the middle that doesn’t matter).
Corners always stays in the corner: $8!$ with $3^8$ color arrangements
edge always stays in the edge: $12!$ with $2^12$ color arrangements.
But not all of these are achievable. Need Group theory.
There are $12$ orbits (symmetries).
???? I don’t understand ????
Subsets
select k from n distinct objects. orders don’t matter.
Orders don’t matter –> a kind of symmetry.
Ex: select a subset of k from n distinct objects.
,,…, with k spots. n choices.
select and order = $P(n,k) = (n)(n-1)….(n-k+1)$
No. of symmetry = ordering of k objects = $k!$
Finally, ${P(n,k)}/{k!}$
Formally:
r-combination
r elements from a set of n distinct subject to form an unordered subset. n choose r.
$C(n,r) = {P(n,r)}/{r!} = {n!}/{(n-r)!(r!)}$
Ex: Picking 7 students from a class of 150 to go on to a field trip.
Ans:
$C(150,7) = {150!}/{7!*(150-7)!}$
r-combination and r-permutation are friends
$ P(n,k) = C(n,k) * (k!)$
You first select $C(n,k)$ and then order $k!$
The relation between subset and binary strings.
k element subset from n <–> binary string of length n with exactly k ones.
How?
It’s like “choose k spots from n and fill it with 1. The rest are 0”
No matter the order you choose.
Or, look it like this: (Bijection)
{1,2} <–> 1100
{1,3} <–> 1010
Binomial coefficient identities
identity = an equation that is always true.
To prove:
- Do algebraic manipulations of formulas
- Interpret each side as counting some collection of fixed density strings and then prove a statement about those sets.
Ex: Prove $C(n,k) = C(n,n-k)$
-
Use formula: $C(n,k) = {n!}/{n!(n-k)!} = C(n, n-k)$
-
Combinatorial proof:
LHS(left hand side counts the binary string of length n with k ones)
RHS counts the binary string with length n with n-k ones.
make a Bijection RHS also counts length n with n-k zeros. which is just like length n with k ones, which is LHS.
We can match up all combinations between two sets and thus the two sets are of same size BINGO.
** if we think of choosing k out of n:**
- it equal to choosing n-k to be left out
Ex: Pascal’s identity.
Prove: $C(n+1, k) = C(n, k-1) + C(n,k)$
Ans:
Here we see summation –> split into disjoint sets.
LHS = string of length n+1 with k zeros.
= (if the string starts with 0) + (if the string starts with 1)
= (the rest of k-1 zero in length n) + (the k zero in length n)
= $C(n,k-1) + C(n, k)$
= RHS
** Pascal Triangle can solve binomial coefficient. **
Find a pattern of sum of rows = $2^n$. Why?
All possible strings of length n =
(with no zero) + (with 1 zero) + …(with k zero) … + (with n zero)
= $C(n,0) + C(n,1) … C(n,k)…+C(n,n)$
= 0 or 1 in each spot
= $222….for n times = 2^n$
Fabonacci in Pascal
Why are they called binomial coefficients?
$(x+y)^n
= (x+y)(x+y) …(x+y)
= a{x^n} + b{x^{n-1}y}….z(y^n)$
-
it’s like choosing either $x$ or $y$ in each ()
-
the choosing makes up the coefficient $a,b,…z$.
For example,
-
to get $x^n$ you need to all choose n x–> $C(n,1)$ ways to do that.
-
to get $x^{n-k}y^{k} you need to choose k y –> $C(n,k) ways to do that –> this is the coefficient.
Another way to prove $\sum\limits_{k=0}^n C(n,k) = 2^n$
From binomial theorem we know:
$ (x+y)^n = \sum\limits_{k=0}^n C(n,l){x^n}{y^(n-k)}$
let’s make $x = 1$ and $y = 1$.
proved.
To prove $\sum\limits_{k=0}^n C(n,k){(-1)^k} = 0$
make $x = 1, y = -1$