[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
The second most beautiful counting method in combinatorics:
Inclusion-Exclusion
[/ QUOTE ]
The first being?
[/ QUOTE ]
The method of double counting.
[/ QUOTE ]
What's the difference?
[/ QUOTE ]
Double counting means enumerating a set by counting the objects in the set in two different ways and then equating them to arrive at the answer.
[/ QUOTE ]
Example: Compute the sum S = 1 + 2 + 3 + ... + 100.
S = 100 + 99 + 98 + ... + 1
Adding the above two equations gives:
2S = 101 + 101 + 101 + ...(100 times)
2S = 101*100 = 10,100
S = 5,050
Example: Compute the sum S = 1 + 1/2 + 1/4 + 1/8 + ...
(1/2)*S = 1/2 + 1/4 + 1/8 + ...
Subtracting these gives:
(1/2)*S = 1
S = 2.
Example: S = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + ...
S = 1 + 1/S
S^2 = S + 1 = 0
S^2 - S - 1 = 0
S = 1/2 + sqrt(5)/2
Example: S = sqrt(1 + sqrt(1 + sqrt(1 + sqrt(1 + ...
S = sqrt(1 + S)
S^2 = 1 + S
S^2 - S - 1 = 0
S = 1/2 + sqrt(5)/2
A well-known mathematician once told me that there are 4 tricks used to derive everything in applied mathematics (or something like that):
1. Exchange the order of integration or summation.
2. Integrate by parts.
3. Add and subtract 1.
4. Induction.