In how many different ways can r elements be picked from a set of n elements if repetition is allowed and order of picking does not matter?

Question

My approach gives me $\frac{n^r}{r!}$ but the answer given is $\frac{(n+r-1)!}{r!(n-1)!}$. Where am I wrong?

Answer 1

Imagine that you are allowed to choose a total of $r$ candies from $n$ types of candies.

For each of the $n$ types, go on saying yes until you don't want any more, and then say no and move on to the next type.

Of course, you may say no straight away to any type if you don't want it, and you don't need to say no after the $n{th}$ because there is no next type.

So there will be $r$ of yes and $(n-1)$ of no whichever way you choose, and the only decision you need to take is where to place the yes's in the sequence of $n-1 +r$ elements,

thus # of choices $=\dbinom{n+r-1}{r} = \dfrac{(n+r-1)!}{r!(n-1)!}$

---

This method is called "stars and bars", and in the usual "stars and bars" explanation:

$\Large\ast\ast|\ast\ast\ast|\ast\ast\ast\ast\ast|\ast\ast\ast|\ast\ast\ast\ast\ast$

The "stars" stand for the $r$ yes's, and the "bars" for the $n-1$ no's

Answer 2

The number of permutations $r!$ is not correct for all selections of $r$ elements, because permuting identical elements does not make a difference.

HINT :-

Think about number of solutions of:- $$x_1+x_2+...+x_n=r,\space x_1,x_2,...,x_n\in\Bbb{N}\cup\{0\}$$

Since the order does not matter, all you have to worry about is no. of times an element is choosed. You choose first element $x_1$ times, second $x_2$ times and so on. You need to choose $r$ times in total. So their sum is $r$. You may never select a particular element, hence $x_i$ may be zero as well.

How to solve this further:- Quora