Discrete Mathematics video

I watched video 11-15-00: Combinations and permutations. A lecture by Shai Simonson. A lecture in the Discrete Mathematics series on the ADUni.org website.

Topics:
Counting principles.
- Multiplication
- Addition
- Complement
- Counting double
- 'When are things the same'?
Permutation
Combination
n Choose k.
Binomial Theorem
Pascal Triangle
Proofs
- by formula
- by induction
- by combinatorial argument

Doing proofs by combinatorial argument is a powerful technique. The basic identity from the Pascal triangle
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
...
[n,k]=[n-1,k-1]+[n-1,k]
for example
[6,3]=[5,2]+[5,3]=20=10+10
can easily proven by a combinatorial argument.

Such an argument could be the following.
Let n be the number of employees of a small company with one director. We have to select a k-member team from all employees. The number of teams is [n,k]
Exclude the director from selection and select a k-member team. The number of teams is [n-1,k].
Now select a (k-1)-team, the number of teams is [n-1,k-1] and add the director to it which makes it a k-member team including the director.
Adding the number of k-member teams without a director and k-member teams with a director is the total number of k-member teams or [n-1,k] + [n-1, k-1].

This proves [n,k]=[n-1,k-1]+[n-1,k].