Consider this question:
In how many ways can $5$ tourists be placed in $3$ different hotels, such that there is at least one tourist in each hotel?
To start working on this, I removed the lower bound on the number of tourists in a hotel. I reasoned that any tourist can be placed in any of the $3$ hotels, resulting in $5\times 3=15$ permutations.
However, the correct answer with the lower bound is $150$, which is more than $15$.
Obviously, I am undercounting by a large amount. How?
Best Answer
This is not correct. Without the lower bound you can assign one hotel to one by one the tourists. So, if you line up the tourists in a line and record the hotel you will get: $3$ possibilities for each one, giving you $3\times 3\times \cdots \times 3=3^5.$
Notice that this is the same as the number of functions from $[5]$ to $[3]$ (you are making a functional choice, i.e., you dont want to send one tourist to two different hotels).
Now, with the lower bound, you have to take away the times that you missed one of the hotels. The problem becomes in that you will be overcounting so you have to include and exclude. You will get $3^5-3\cdot 2^5+3,$ where the $2^5$ is choosing out of now $2$ hotels(you are missing one of the $3$ hotels). The last $3$ is because when you take out the hotels you are overcounting the choice in which you send all the tourist to the same hotel!
In fancy terms this is the number of surjective functions from $[5]$ to $[3]$ that can be established using the Stirling numbers of second kind as ${5\brace 3}\cdot 3!$