    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