[Home]

Table of contents


Bar-star argument

"Bar-star argument" is a fancy name given to a commonly used technique in combinatorics. The problem is to find out the total number of ways you can distribute $n$ identical objects among $k$ boys (of course distinct) such that each boy gets at least one object.

Let's warm up with an example. Suppose that we have 10 objects and three boys. We can show one possible way of distributing the apples like this:
***|*|******
Here each * (star) is one object and the |'s (bars) show the boundaries. Thus here the first boy gets 3 objects, the second gets 1, the third gets the remaining 6.

The answer may now be obtained like this: So, by the multiplication principle, the answer is $1\times{9\choose 2} = {9\choose 2}.$

First version

Generalising the above argument for $n$ objects and $k$ boys, the answer is $$ {n-1\choose k-1}. $$

Second version

Here we allow one or more boys to go empty-handed. Thus the following is allowed:
|***|*******
where the first boy gets nothing. Another possibility is
***||*******
where the second boy has nothing.

Here it is just like arranging 10 identical starts and 2 identical bars in a row. Notice that the bars are identical, though the boys are not! Imagine that there are a total of $10+2=12$ places, of which you can pick any 2 for the bars. So the answer is ${12 choose 2}.$

In general, for $n$ objects and $k$ apples, the answer is $$ {n+k-1\choose k-1}. $$