How many different combinations of $X$ sweaters can we buy if we have $Y$ colors to choose from?
According to my teacher the right way to think about this problem is to think of partitioning $X$ identical objects (sweaters) into $Y$ different categories (colors).
Well,this idea however yields the right answer but I just couldn't convince my self about this way to thinking,to be precise I couldn't link the wording of the problem to this approach,could any body throw some more light on this?
On
The classical solution to this problem is as follows:
Order the $Y$ colors. Write $n_1$ zeroes if there are $n_1$ sweater of the first color. Write a single one. Write $n_2$ zeroes where $n_2$ is the number of sweaters of the second color. Write a single one, and so on.
You get a string of length $X+Y-1$ that has exactly $X$ zeroes and $Y-1$ ones. The map that I have described above is a 1-1 correspondence between number of different combinations of $X$ sweaters with $Y$ colors and the set of such binary strings. Now, each string is uniquely determined by the positions of the ones in the string. How many ways are there to place $Y-1$ ones in an array of length $X+Y-1$?
Does this help?
Edit: With my reasoning, you arrive exactly at Brian Scott's formula. He uses bars where I have ones and stars where I have zeroes.
On
How many different combinations of $X$ sweaters can we buy if we have $Y$ colors to choose from?
To help build some intuition, how about a simple example?
Say we walk into a store to buy three sweaters. The store stocks two colors of sweater, red ($R$) and blue ($B$). In this case $X=3$ and $Y=2$. What possible selections of colors can we make for the set of three sweaters?
The first thing to note is that order does not matter. It doesn't matter if we chose Sweater 1 to be red and Sweaters 2 and 3 to be blue ($RBB$), or Sweaters 1 and 2 to be blue and Sweater 3 to be red ($BBR$). So a selection of $RBB$ will be the same as $BBR$.
Very well, how then will we find a systematic way of listing and counting all the possible selections we can make?
The method Stefan posted is the "usual" way of doing this; I will use essentially the same method, but perhaps explain it slightly differently.
We will want to have $X=3$ sweaters when we eventually walk out of the store. Let's represent them by $3\ O$'s:
$$OOO$$
Now what is meant by "partitioning" is this:
We have $Y=2$ colors to choose from. We will thus divide our line of $3$ $O$'s into $2$ distinct groups by putting a bar $|$ in between them, so that any $O$'s to the left of the bar will be red, and those on the right will be blue. So for example, the selection $RBB$ given earlier will be represented by $$O|OO.$$
As another example, the selection of $3$ red sweaters would be represented as $$ OOO|$$ (all $3$ $O$'s are on the left of the bar, and there are none on the right.)
So we can represent each of our selections with this combination of $3$ $O$'s and $1$ $|$. Try representing the selection $RBR$. (Answer below):
Remember that order does not matter, so we just put the two red ones on the left of the bar, and the blue one on the right, like so: $$OO|O$$
This is what is meant by partitioning $X$ objects into $Y$ categories. The $X$ objects are represented by a string of $X$ $O$'s $$ \underbrace{OO\cdots O}_X,$$ into which we insert $(Y-1)$ $|$'s so that we divide the list of $O$'s into $Y$ different categories $$ \underbrace{O\cdots O}_{1st\ category} \stackrel{1st}{|} \underbrace{O\cdots O}_{2nd\ category} \stackrel{2nd}{|} \cdots \stackrel{(Y-1)th}{|} \underbrace{O\cdots O}_{Yth\ category}. $$
Note that a category may not be filled, for example if we had three colors red, blue and green, we could still choose the selection $RBB$, which would be represented by $3$ $O$'s and $2$ $|$'s like so: $$O|OO|$$ as explained by the diagram below: $$ \underbrace{O}_{red}|\underbrace{OO}_{blue}|\underbrace{}_{green} $$
Hopefully the idea of partitioning $X$ objects into $Y$ categories is now clear. Back to the example, how many ways can we do this if $X=3,\ Y=2$?
Well, we want to permute $3$ $O$'s and $1$ bar (remember that if we have $Y$ categories we will need $(Y-1)$ bars), so hopefully you've done enough basic combinatorics to know how to do this?
Think of it this way. You go into the shop to buy $X$ sweaters, all identical except for their colors. You know that they come in $Y$ different colors, and you hate to mix colors, so you bring $Y$ shopping bags with you, one for each possible color. Now you pick out your $X$ sweaters and put each one into the bag reserved for its color. You end up with $Y$ shopping bags containing a total of $X$ sweaters, though some of the bags may be empty.
Now suppose that instead of labelling each bag with a color, you label it with a number from $1$ to $Y$. Let $x_1$ be the number of sweaters in bag $1$, $x_2$ the number of sweaters in bag $2$, and so on up to $x_Y$, the number of sweaters in bag $Y$. Then $$x_1 + x_2 + \dots + x_Y = X,\tag{1}$$ and each $x_k$ ($k=1,\dots,Y$) is a non-negative integers. Counting the different ways to choose the sweaters is the same as counting the solutions to $(1)$ in non-negative integers.
Another version of the same problem goes like this: how many ways are there to distribute $X$ identical marbles amongst $Y$ numbered boxes? If $x_k$ is the number of marbles in Box $k$, we are again just counting solutions to $(1)$ in non-negative integers.
This kind of problem is often called a stars and bars problem. Let me explain the solution in terms of the marbles and boxes. Suppose, for the sake of illustration, that $Y=5$ and $X=10$. One possible distribution of the marbles puts $0$ in the first box, $3$ in the second box, $0$ in the third box, $2$ in the fourth box, and $5$ in the fifth box. I can represent this arrangement by a line of ‘stars and bars’: $$|***||**|*****$$
The empty space before the first | represents the empty first box; the three *’s between the first and second |’s represent the three marbles in the second box; and so on. Every possible distribution of the $10$ marbles in the $5$ boxes can be uniquely represented by such a string of $10$ stars and $4$ bars, and each string of $10$ stars and $4$ bars corresponds to a unique distribution of the marbles. Thus, the number of distributions is the number of strings of $10$ stars and $4$ bars. Once you know where the bars are, everything else is a star, so the answer is $\binom{10}{4}$. This of course is also the number of ways of picking out $10$ sweaters of $5$ possible colors and the number of solutions in non-negative integers of $(1)$ when $Y=5$ and $X=10$.
More generally, $Y$ boxes will require $Y-1$ bars to separate them from one another, so you’ll have a string of $X$ stars and $Y-1$ bars, and there are $$\binom{X+Y-1}{Y-1} = \binom{X+Y-1}{X}$$ of these.