1

If we choose $k$ objects from $n$ with replacement and we don't ignore the order of the choices(e.g if we choose $3$ objects of $A,B$ with replacement,the results $AAB$ and $ABA$ are considered as different ones),how many different choices exist?

Is it $\binom{n+k-1}{k}$ ?

evinda
  • 7,823

1 Answers1

3

Hint: We are forming $k$-letter "words."

The first letter can be chosen in $n$ ways. For each such choice, the second letter can be chosen in $n$ ways. Continue.

Remark: If we ignore the order, then we are in a "Stars and Bars" situation. Let $y_i$ be the number of Type $i$ objects we select ($i=1$ to $n$). We are looking for the number of solutions of the equation $y_1+y_2+\cdots +y_n=k$ in non-negative integers. In that case, the expression of the OP is correct. However, when $AAB$ and $ABA$ are considered different, the Stars and Bars analysis does not apply.

André Nicolas
  • 507,029
  • Why can the first letter be chosen in $n$ ways,and also the second one,and so on...I haven't understood it!!! – evinda Apr 25 '14 at 18:55
  • 1
    We are using replacement. Consider for example $3$-element sequences, say with $n=26$, the size of the English alphabet. The first letter can be any of the $26$. Whatever letter we choose as the first letter, we have $26$ choices for the second letter, for a total of $26^2$ two-letter words. Any two-letter word can be completed to a three-letter word in $26$ ways, for a total of $26^3$. – André Nicolas Apr 25 '14 at 19:05
  • So,when they are different from each other,the result is $n^k$,but if they would be cosidered as the same then it would be $\binom{n+k-1}{k}$ ??? – evinda Apr 25 '14 at 19:09
  • 1
    Yes, for the question you asked, which says that $AAB$ is not the same as $ABA$, the answer is $n^k$. If permutations are to be considered identical, then $\binom{n+k-1}{k}$ is correct. – André Nicolas Apr 25 '14 at 19:22
  • Nice,I understand...thank you very much!!! – evinda Apr 25 '14 at 19:45
  • 1
    You are welcome. – André Nicolas Apr 25 '14 at 19:45