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].

Stephen Hawking RIP

3 days ago

## No comments:

## Post a Comment