Thanksgiving PIE?
by shiningsunnyday, Nov 28, 2016, 10:22 AM
Combo 3 homework (Hard) wrote:
Let
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 





If we let


In other words, the RHS counts the number of choosings by the

Changing perspectives, think of each of the









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.