Question: Find the number of ways to choose $k$ objects from $n$ $(n\ge k)$ distinct objects with replacement, where order of arrangement of the objects chosen doesn't matter.

Solution: Let us try to think about this problem in terms of the stars and bars arrangement.

Observe that this problem is equivalent to finding the number of ways of placing $n-1$ stars and $k$ bars in $n+k-1$ places. Let us see how it is equivalent.

Firstly we consider that the $n$ stars correspond to the $n$ objects that are available to us and let the number of bars placed before a star correspond to the number of times the object corresponding to that star is selected in the process. Also note that since here the order of arrangement doesn't matter, therefore, we take all the stars to be non-distinct. Now in order to solve the problem we consider $n+k-1$ empty places followed by a $*$ placed at the end, which corresponds to some arbitrary object out of the given $n$ objects, $$\underbrace{---\cdots -}_{n+k-1}\hspace{0.2 cm}*.$$ Now placing the remaining $n-1$ stars and $k$ bars in the shown $n+k-1$ empty places, we will be done. And, the number of ways in which this can be done is $$\binom{n+k-1}{k}=\binom{n+k-1}{n-1}.$$ Hence, we are done.

Is this explanation understandable and correct?


The calculation is correct, but your explanation is not very clear and is definitely not the usual stars and bars analysis. In the usual stars and bars analysis of this problem we imagine that we have a row of $n$ empty containers, one for each of the distinct objects. Each time we choose an object, we put a stone in the container for that object. When we’re done, we’ve put a total of $k$ stones into the $n$ containers. We can represent each possible result as a row of $k$ stars, one for each stone, and $n-1$ bars separating the contents of the $n$ containers. Every arrangement of these $n-1+k$ symbols is possible, and each corresponds to exactly one unordered selection of $k$ objects, so there are $\binom{n-1+k}k=\binom{n-1+k}{n-1}$ ways to select the objects.

In your explanation you’ve interchanged the stars and bars: your stars correspond to the $n$ objects and your bars to the $k$ chosen objects. Your idea is to place one bar immediately in front of a star for each time the corresponding object is selected. That’s fairly clear, but then your explanation runs into problems. You say that we’ll take the stars not to be distinct, but this is clearly not true: they correspond to distinct objects, and we are clearly treating them as distinct, since we use their distinct identities to determine where the bars are to be placed. You’ve also failed to explain how $n$ stars and $k$ bars suddenly become $n+k-1$ empty places with an extra * at the end.

I think that I understand what you’re trying to do, but it’s not at all clear from your explanation. When you place your $k$ bars in front of the stars corresponding to the chosen objects, you will never place any bars at the end of the string of $n$ stars, after the last star. Thus, it’s only the first $n-1$ stars and the $k$ bars whose positions in the string can change depending on which objects you chose, and those $n-1+k$ symbols can occur in any order. Just as in the usual explanation, each order of the $n-1+k$ symbols corresponds to one possible choice of objects and vice versa, so there are $\binom{n-1+k}k=\binom{n-1+k}{n-1}$ ways to select the objects.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.