2
$\begingroup$

I'm looking for a way to calculate the number of combination of 10 choose 5 => $_5^{10}C$ while allowing any number repetitions and counting 12345 and 54321 only once (order isn't important, ie I count 11355 but not then 35115).

I think this number is majored by $10^5$, but how to remove ordering number ?

$\endgroup$
14
6
$\begingroup$

(Note: I'm using the notation $\binom{n}{k}$ here instead of $^n_kC$.)

A multiset is a collection of things that allows repetition but ignores order. The number of multisets of size $k$ with elements from a set of size $n$ is

$$\left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k! (n-1)!}.$$

In your case, you'll have $\left(\!\!\binom{10}{5}\!\!\right) = \binom{10+5-1}{5} = 2002$.

$\endgroup$
1
  • $\begingroup$ The answer $\binom{14}{5}$ is given by the standard "stars-and-bars" method. Arrange nine "bars" (separators) and five "stars" (placeholders for elements of multisets) in a line. Any items to the left of the first bar are counted as zeros; items between the ith and i+1st bar are counted as i's; items after the ninth bar are 9's. $\endgroup$ – hardmath Nov 23 '13 at 16:11
1
$\begingroup$

Since order doesn't matter, we can consider results as different if they differ after sorting. In other words, when order doesn't matter, generate the results with inherent sorting. If you build a table, 5 slots wide and 10 slots high, and trace all paths from bottom left to somewhere on the right edge, but only allow paths to go 1 step right and never go down, then a clear pattern emerges. The right hand side of this tabel contains 1,5,15,35.. or (n+3) choose 4. The sum at the right edge is 2002 or 14 ch 5. The diagonals are Pascal's triangle.

$\endgroup$

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.