Question: You have 9 presents to give to your 4 kids. How many ways can this be done if:
The presents are unique and each kid gets at least one present?
I know the solution is by using Principle of Inclusion and Exclusion.
$4^9 - [{4 \choose 1}3^9 - {4 \choose 2}2^9 + {4 \choose 3}1^9] = 186480$ <-- Correct Solution
But, initially, when I approach this problem, my thought is this:
1.) First, make sure every kid has at least one present by finding the permutation $P(9,4)$.
$9 * 8 * 7 * 6 = 3,024$
2.) We are now left with 5 presents, since each present can be match to 4 different kids.
$4^5 = 1024$
3.) Each permutation in 1.) can be combined with each permutation in 2.) to form unique permutation.
$3024 * 1024 = 3,096,576$
Need help in figuring out how the thought is wrong because until now I still can't brain what's wrong with it.
You count part of the distributions multiple times.
Say David gets a ball and a doll. He can get the ball in step 1 and the doll in step 2 or the other way around. In the second method, you count this giveaway as two different ones, instead of one.