Two simple questions

In how many ways can you distribute {n} distinct objects into {k} different bins?

Of course, for each object, there are {k} possible bins, so the total number of ways is {k^n}.

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 {n} to each bin so that the sum of all {k} assigned numbers is exactly {n}. If we completely ignore the fact that the sum must be {n}, then we get that the total number of ways of assigning numbers is {(n+1)^k}.

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 {n} and the second one is polynomial in {n}. That’s a huge difference. Just making the objects distinct changes the total search space from polynomial to exponential.

Advertisements

3 thoughts on “Two simple questions

  1. chillu says:

    If the objects aren’t distinct then the problem is the same as finding the number of non-negative integer solutions to x_1 + x_2 + \dots + x_k = n. This problem can again be reduced to a choosing problem to give \choose{n+k-1,n}.

    If you continue varying the possibilities of such problems you notice that you essentially have three parameters: distinctness of bins, distinctness of balls, restrictions on the number of balls in a bin. The first two parameters can take two values, while the last parameter can take one of three values: i) at least one ball, ii) at most one ball, iii) no restriction. Finding the solution of each combinatorial problem will lead you to the twelvefold way (in your post, you found two entries in that table).

    • Vinayak says:

      The aim, obviously, was not to enumerate entries from that table. The aim was to point out that there is an exponential gap between two of the entries.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s