Thanksgiving PIE?
by shiningsunnyday, Nov 28, 2016, 10:22 AM
Combo 3 homework (Hard) wrote:
Let 
Prove that 
Prove that 
We have a PIE-esque summation involving terms of the form 
so it's natural to think of it as first taking away 
elements of 
and then each of 
people each choosing a (not necessarily distinct) nonempty subset of the remaining 
elements.
If we let
be the set of all such choosings by the m people such that element k is not picked by anyone, so by PIE we have 
In other words, the RHS counts the number of choosings by the people such that at least one element is not picked.
Changing perspectives, think of each of the
elements as 'going' to a nonempty set of the people. Let 
be the set of choosings such that element goes to an empty subset of the people, which is equivalent to 
the set of choosings such that element is chosen by no one. It's not hard to see that 
and etcetera, and the conclusion follows since 
so it's natural to think of it as first taking away 
elements of 
and then each of 
people each choosing a (not necessarily distinct) nonempty subset of the remaining 
elements.If we let
be the set of all such choosings by the m people such that element k is not picked by anyone, so by PIE we have 
In other words, the RHS counts the number of choosings by the
people such that at least one element is not picked.Changing perspectives, think of each of the
elements as 'going' to a nonempty set of the people. Let 
be the set of choosings such that element goes to an empty subset of the people, which is equivalent to 
the set of choosings such that element is chosen by no one. It's not hard to see that 
and etcetera, and the conclusion follows since 
Tidbit
FML I'VE BEEN BINGE-COMBO3ING DUE TO TOO MUCH SCHOOL STRESS.
ALSO CANADIAN SENIOR MATH CONTEST TOMORROW PLEASE NO SILLY.
ALSO CANADIAN SENIOR MATH CONTEST TOMORROW PLEASE NO SILLY.
May 2017
April 2017