Difference between revisions of "Combinatorics"
(→Intermediate Combinatorics: added "geometric probability") |
m (reorganized) |
||
| Line 3: | Line 3: | ||
== Introductory combinatorics == | == Introductory combinatorics == | ||
| + | === Lists -- the beginning === | ||
| + | Consider the task of counting the number of integers between 14 and 103 inclusive. We could simply list those [[integers]] and count them. However, we can renumber those integers so that they correspond to the [[counting numbers]] (positive integers), starting with 1. In this [[correspondence]], 14 corresponds to 1 (for the 1st integer in the list), 15 with 2, 16 with 3, etc. The relationship between the members of each pair is that the second is 13 less than the first. So, we we know that 103 corresponds to the 103 - 13 = 90th integer in the list. Thus the list is 90 integers long. | ||
| + | |||
| + | Note that <math>13 = 14 - 1</math>, or 1 less than the first integer in the list. If we start our list with n and end with <math>m</math>, the number of integers in the list is | ||
| + | |||
| + | <math>\displaystyle m - (n -1) = m - n + 1.</math> | ||
| + | |||
| + | |||
| + | === Introductory Topics === | ||
The following topics help shape an introduction to counting techniques: | The following topics help shape an introduction to counting techniques: | ||
* [[Venn diagram]] | * [[Venn diagram]] | ||
| Line 15: | Line 24: | ||
* [[Combinatorial identities]] | * [[Combinatorial identities]] | ||
* [[Binomial theorem]] | * [[Binomial theorem]] | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| Line 34: | Line 36: | ||
* [[Partitions]] | * [[Partitions]] | ||
* [[Geometric probability]] | * [[Geometric probability]] | ||
| + | |||
== See also == | == See also == | ||
* [[Probability]] | * [[Probability]] | ||
Revision as of 11:57, 21 June 2006
Combinatorics is the study of counting. Different kinds of counting problems can be approached by a variety of techniques.
Contents
Introductory combinatorics
Lists -- the beginning
Consider the task of counting the number of integers between 14 and 103 inclusive. We could simply list those integers and count them. However, we can renumber those integers so that they correspond to the counting numbers (positive integers), starting with 1. In this correspondence, 14 corresponds to 1 (for the 1st integer in the list), 15 with 2, 16 with 3, etc. The relationship between the members of each pair is that the second is 13 less than the first. So, we we know that 103 corresponds to the 103 - 13 = 90th integer in the list. Thus the list is 90 integers long.
Note that 
, or 1 less than the first integer in the list. If we start our list with n and end with 
, the number of integers in the list is
Introductory Topics
The following topics help shape an introduction to counting techniques:
- Venn diagram
- Combinations
- Permutations
- Overcounting
- Complementary counting
- Casework
- Constructive counting
- Committee forming
- Pascal's triangle
- Combinatorial identities
- Binomial theorem
Intermediate Combinatorics
- Principle of Inclusion-Exclusion
- Conditional Probability
- Recursion
- Correspondence
- Generating functions
- Partitions
- Geometric probability
