4
$\begingroup$

The number of different ways to choose $k$ out of $n$ unique items:

  • Without repetition and without order-significance: $\binom{n}{k}=\frac{n!}{k!(n-k)!}$
  • Without repetition and with order-significance: $\binom{n}{k}\times k!=\frac{n!}{(n-k)!}$
  • With repetition and with order-significance: $n^k$
  • With repetition and without order-significance: $?$

Thank you!

$\endgroup$
5
$\begingroup$

Start by arranging all of your $n$ items in some canonical linear order. You then go through the line, picking some number of copies of each item. As you do this you say "move to the next item" $n-1$ times, and "take one of these" $k$ times. These instructions can be in any order, however, so there are $\binom{k+n-1}{k}$ ways to do this.

See also Stars and bars, in particular Theorem 2 on the linked page.

$\endgroup$
  • $\begingroup$ +1 I knew the answer, but I eally like the way you state it. ;-) $\endgroup$ – Jean-Claude Arbaut May 14 '14 at 15:42
  • $\begingroup$ Plain and simple. Thank you very much :) $\endgroup$ – barak manos May 14 '14 at 15:43

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.