Next: Countable sets Up: Elementary combinatorics Previous: Surjections   Contents

## Combinations

Proposition 7.2.10   Let be a finite set such that . If , the number of subsets of such that is equal to the number defined by:

In particular, we have:
(i)
; there exists only one possibility to choose 0 element from a set (you don't choose anything!).
(ii)
; you have different choices for a single element.

Proposition 7.2.11   Let and be two natural numbers such that . Then we have:
1. ;
2. .

Proof.
1. We replace into the definition:

2. We begin from the right-hand side:

This last property has a nice presentation, called Pascal's triangle (note that it can be extended infinitely):

The colored arrows show three different examples, namely:

Theorem 7.2.12 (Newton's Binomial Formula)   For any and , the following holds:

This is te generalization of well known formulas:

and so on. Compare the coefficients of these developments (together with the coeeficients in and ) with the rows of Pascal's triangle).

Proof. By induction on .
• For , the equality is trivial.
• Assume that for some natural number , the equality holds. Then we have:

Corollary 7.2.13   Let be a finite set such that . Then .

Proof. We have:

Next: Countable sets Up: Elementary combinatorics Previous: Surjections   Contents
root 2002-06-10