In how many ways can you distribute distinct objects into different bins?

Of course, for each object, there are possible bins, so the total number of ways is .

Now, consider the same question, except, the objects are not distinct any more. Thus all that matters is how many of them go into each bin and not which ones in particular.

The answer to this can be slightly complicated to calculate, but if we simplify things a bit and look for a loose upper bound, we can argue as follows. The problem is equivalent to assigning one number between 0 and to each bin so that the sum of all assigned numbers is exactly . If we completely ignore the fact that the sum must be , then we get that the total number of ways of assigning numbers is .

I am certain that I knew both these things back in high school, but it was quite recently that I realized that the first one is exponential in and the second one is polynomial in . That’s a huge difference. Just making the objects distinct changes the total search space from polynomial to exponential.