Whats the most insightful probability post ever posted on here?

["spaceman"Bryce]

it would be interesting to see....

[elitegimp]

I really liked BruceZ's inclusion-exlusion post... It might not be the most insightful, but I hope that by mentioning it he'll appear like a magic genie and post a link /images/graemlins/smile.gif (I'm too lazy to search, and too lazy to PM him, so I guess if I never see the post again it'll be my own damn fault)

[jason_t]

[ QUOTE ]
I really liked BruceZ's inclusion-exlusion post... It might not be the most insightful, but I hope that by mentioning it he'll appear like a magic genie and post a link /images/graemlins/smile.gif (I'm too lazy to search, and too lazy to PM him, so I guess if I never see the post again it'll be my own damn fault)

[/ QUOTE ]

The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[gaming_mouse]

[ QUOTE ]


The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ QUOTE ]

The first being?

[elitegimp]

[ QUOTE ]
[ QUOTE ]
I really liked BruceZ's inclusion-exlusion post... It might not be the most insightful, but I hope that by mentioning it he'll appear like a magic genie and post a link /images/graemlins/smile.gif (I'm too lazy to search, and too lazy to PM him, so I guess if I never see the post again it'll be my own damn fault)

[/ QUOTE ]

The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ QUOTE ]

Awesome dude, thanks!

[jason_t]

[ QUOTE ]
[ QUOTE ]


The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ QUOTE ]

The first being?

[/ QUOTE ]

The method of double counting.

[gaming_mouse]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]


The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ QUOTE ]

The first being?

[/ QUOTE ]

The method of double counting.

[/ QUOTE ]

What's the difference?

[PygmyHero]

You lost me. Could we maybe have a link or thread for that too? Thanks!

[jason_t]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]


The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ 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.

Inclusion-exclusion is the method of enumerating a set by overcounting and undercounting repeatedly to arrive at the answer.

[BruceZ]

[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]
[ QUOTE ]


The second most beautiful counting method in combinatorics: Inclusion-Exclusion (http://archiveserver.twoplustwo.com/showthreaded.php?Cat=&Board=&Number=417383&page=&v iew=&sb=5&o=&fpart=)

[/ 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.

[gaming_mouse]

Bruce,

Very cool. Can you explain why

S^2 = S + 1 = 0

I just don't get why it is equal to 0. I get the S + 1 part. From example 3.

[jason_t]

[ QUOTE ]
Bruce,

Very cool. Can you explain why

S^2 = S + 1 = 0

I just don't get why it is equal to 0. I get the S + 1 part. From example 3.

[/ QUOTE ]

The "= 0" should not be there. It should just be

S = 1 + 1/S
S^2 = S + 1
S^2 - S - 1 = 0
S = 1/2 + sqrt(5)/2.

[BruceZ]

[ QUOTE ]
Example: S = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + ...

S = 1 + 1/S

S^2 = S + 1 = 0

[/ QUOTE ]

Of course the "=0" should not be there.

Were these the kinds of examples you had in mind Jason?

[gaming_mouse]

[ QUOTE ]
[ QUOTE ]
Bruce,

Very cool. Can you explain why

S^2 = S + 1 = 0

I just don't get why it is equal to 0. I get the S + 1 part. From example 3.

[/ QUOTE ]

The "= 0" should not be there. It should just be

S = 1 + 1/S
S^2 = S + 1
S^2 - S - 1 = 0
S = 1/2 + sqrt(5)/2.

[/ QUOTE ]

ok. that makes sense. thanks.

[jason_t]

[ QUOTE ]
Were these the kinds of examples you had in mind Jason?

[/ QUOTE ]

The first example certainly is although the rest aren't however they demonstrate a related idea.

Here is an incredible example of double counting.

Let k be any natural number and let d(k) be the number of natural numbers between 1 and k inclusive that divide k. So

d(1) = 1
d(2) = 2
d(3) = 2
d(4) = 3
d(5) = 2
d(6) = 4
d(7) = 2
d(8) = 4
d(9) = 3
d(10) = 4

etc. It seems that d(k) behaves pretty wildly. For primes p we have d(p) = 2 whereas for powers of two we have d(2^k) = k+1. It's a general phenomenon in mathematics that averaging is a smoothing process. Let's ask the following question: what is the average value of d(k)? So let's try and compute

http://i3.photobucket.com/albums/y73/jason_t712/dc1.jpg

via the method of double counting.

Form an n x n matrix and put a 1 in entry (i,j) if i divides j and put a 0 otherwise. For example, if n = 8 the matrix is

http://i3.photobucket.com/albums/y73/jason_t712/dc2.jpg

where I did not write down the zeros to make the matrix easier on the eyes. Let's count the number of ones in the matrix. There are two ways to do this. If you count the number of ones in column j you end up with the number of divisors of j, namely d(j). Summing over j you get the number of ones in the matrix. If you cound the number of ones in row i you end up counting the number of multiples of i up to n. How many such multiples are there? Well, those multiples are i, 2i, ... up to floor(n/i) * i. Summing over i you end up with the number of ones in the matrix. These two different ways of counting the ones in the matrix must produce the same answer. So

http://i3.photobucket.com/albums/y73/jason_t712/dc3.jpg

is true. This is the double counting.

Now divide both sides by n to obtain

http://i3.photobucket.com/albums/y73/jason_t712/dc4.jpg

where the error each of the time we approximated a sum is at most one. Hence f(n) is approximately log n with an error of at most two. That is the average number of divisors of the natural numbers 1,...,n is roughly log n.

[gaming_mouse]

very, very pretty.