Basic enumeration — continued

(a) How many possibilities are there to distribute k forints (Hungarian currency) among n people so that each receive at least one?

(b) Suppose that we do and insist that each person receives something. What will be the number of distributions in this case?

Hint (a)

Imagine k 1-forint coins in a row and suppose that the people come one by one and pick up forints as long as you allow them.

Hint (b)

Reduce to the previous case by borrowing 1 forint from each person.

Solution (a):

If we distribute the forints by the procedure described in the hint, we have to say “Next please” n-1 times. If we determine at which points (after which coins) we say this we uniquely determine the distribution. There are

k-1 possible points to switch and we have to choose n-1 out of these. Hence, the result is

{{k-1} \choose {n-1}}.

Solution (b):

Borrow one forint from each person. If we distribute the n+k forints, we then have in such a way that each person gets at least one, we should then have done the same as if we had distributed the k forints without this requirement. More precisely, distributions of n+k forints among persons so that each one gets at least one are in one to one correspondence with all distributions of n forints among k persons. Hence, the answer is

{{n+k-1} \choose {n-1}}.

More later,

Nalin Pithwa

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

%d bloggers like this: