Difference between revisions of "Combinatorics"
IntrepidMath (talk | contribs) |
Quantum leap (talk | contribs) (→Introductory combinatorics) |
||
| Line 5: | Line 5: | ||
The two most basic and fundamental ideas are that of [[permutations]] and [[combinations]]. | The two most basic and fundamental ideas are that of [[permutations]] and [[combinations]]. | ||
In essentials, the permutation is the number of ways to create a subset of a larger set if order matters (i.e. A, B, C is different from A, C, B). | In essentials, the permutation is the number of ways to create a subset of a larger set if order matters (i.e. A, B, C is different from A, C, B). | ||
| − | Similarly, the combination is the number of ways to create a subset of a larger set if order does NOT matter (i.e. A, B, C is the same as A, C, B). | + | Similarly, the combination is the number of ways to create a subset of a larger set if order does NOT matter (i.e. A, B, C is the same as A, C, B). |
| + | |||
| + | '''Factorials''' | ||
| + | <math>n!=n(n-1)(n-2)\cdots(2)(1)</math> | ||
| + | |||
| + | A '''permutation''' of a set of r objects is any rearrangement of the r objects ''with regard to order''. To find how many ways we can do this, note that for the first of the r elements, we have n different objects we can choose from. For the second element there are (n-1) objects we can choose, (n-2) for the third and so on. In general, the number of ways to permute r objects from a set of n is given by | ||
| + | <math>P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}</math> (by the [[Fundamental Counting Principle]] | ||
| + | |||
| + | The number of '''combinations''' of r objects from a set of n total is the number of ways the r objects can be arranged ''with regard to order.'' | ||
== Intermediate combinatorics == | == Intermediate combinatorics == | ||
An important result of counting techniques is the formulation of the [[Principle of Inclusion-Exclusion]] (PIE). | An important result of counting techniques is the formulation of the [[Principle of Inclusion-Exclusion]] (PIE). | ||
Revision as of 21:52, 17 June 2006
Combinatorics is the study of counting.
Introductory combinatorics
The two most basic and fundamental ideas are that of permutations and combinations. In essentials, the permutation is the number of ways to create a subset of a larger set if order matters (i.e. A, B, C is different from A, C, B). Similarly, the combination is the number of ways to create a subset of a larger set if order does NOT matter (i.e. A, B, C is the same as A, C, B).
Factorials
A permutation of a set of r objects is any rearrangement of the r objects with regard to order. To find how many ways we can do this, note that for the first of the r elements, we have n different objects we can choose from. For the second element there are (n-1) objects we can choose, (n-2) for the third and so on. In general, the number of ways to permute r objects from a set of n is given by
(by the Fundamental Counting Principle
The number of combinations of r objects from a set of n total is the number of ways the r objects can be arranged with regard to order.
Intermediate combinatorics
An important result of counting techniques is the formulation of the Principle of Inclusion-Exclusion (PIE).
