1

Question:

We want to choose three numbers from $\{0,1,2,3,4,5,6,7,8,9\}$ with replacement. The order doesn't matter, so $\{1,1,2\} = \{2,1,1\}$ count as same. How many outcomes in total?

What I've tried so far: I tried to get the result using an online calculator.

But I'm really not sure whether the following answer is correct. (Could anyone correct me if it's wrong?)

And I really don't understand what's the meaning behind of these formulas.

$$CR(n,r) = CR(10,3) = \frac{(10+3−1)!}{3!(10−1)!} = 220$$

Refer: https://www.calculatorsoup.com/calculators/discretemathematics/combinationsreplacement.php

Combinations with replacement, also called multichoose, for $$CR(n,r) = C(n+r-1,r) = \frac{(n+r-1)!}{r!(n+r-1 - r)!} = \frac{(n+r-1)!}{r! (n - 1)!}$$ for $n \geq 0$ and $r \geq 0$. If $n = r = 0$, then $CR(n,r) = 1$.

N. F. Taussig
  • 76,571
Olivia
  • 27
  • Also, if the order doesn't matter, then it isn't a permutation... it's a combination. – Franklin Pezzuti Dyer Jul 05 '17 at 17:01
  • See Section 2.7 here ("subset'' means "combination''): [https://books.google.com/books?id=PS8lQQ8AOHYC&printsec=frontcover&dq=sadovsky+discrete+mathematics&hl=en&sa=X&ved=0ahUKEwiO77rfz_LUAhUFyT4KHatiC1wQuwUIKzAA#v=onepage&q=sadovsky%20discrete%20mathematics&f=false] – avs Jul 05 '17 at 17:04
  • Thanks for your kind reminder. I've updated the question and add some reference to it. – Olivia Jul 05 '17 at 17:05
  • 2
    See stars-and-bars(combinatorics) on wikipedia. Indeed, the result will be as you say (after fixing typos such as missing division symbols) $\binom{3+10-1}{10-1}=220$. The general idea behind the derivation of the formula being that we can describe each way of choosing with a sequence of (in this case) 3 stars and 9 bars and there are $\binom{12}{3}$ such sequences. – JMoravitz Jul 05 '17 at 17:10
  • 2
    You say "I don't understand what's the meaning behind these formulae", if you wish for more information, you'll have to be more specific. Do you not know about factorials and binomial coefficients? Those would be a better starting point for reading if so, otherwise you'll have to be more specific. – JMoravitz Jul 05 '17 at 17:13

1 Answers1

1

The answer you found is correct.

We wish to determine the number of ways a total of three numbers can be selected with replacement from the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$. Let $x_k$ denote the number of times the number $k$ is selected, with $0 \leq k \leq 9$. Then the number of ways three numbers can be selected with replacement from the given set is the number of solutions in the nonnegative integers of the equation $$x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 = 3$$ A particular solution corresponds to the placement of nine addition signs in a row with three ones. For instance, $$1 1 1 + + + + + + + + +$$ corresponds to the solution $x_0 = 3$, $x_1 = x_2 = x_3 = x_4 = x_5 = x_6 = x_7 = x_8 = x_9 = 0$, while $$+ + 1 + + 1 + + + + 1 +$$ corresponds to the solution $x_2 = x_4 = x_8 = 1$, $x_0 = x_1 = x_3 = x_5 = x_6 = x_7 = x_9 = 0$. The number of solutions is the number of ways we can choose which nine of the twelve positions (for three ones and nine addition signs) will be filled with addition signs, which is $$\binom{3 + 9}{9} = \binom{12}{9}$$

The number of ways $n$ objects can be selected with replacement from a set with $k$ elements is the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_k = n$$ in the nonnegative integers. A particular solution corresponds to the placement of $k - 1$ addition signs in a row of $n$ ones. The number of such solutions is $$\binom{n + k - 1}{k - 1}$$ since we must choose which $k - 1$ of the $n + k - 1$ positions (for $n$ ones and $k - 1$ addition signs) will be filled with addition signs. This is also the number of ways $n$ objects can be selected from $k$ types of objects if there are at least $n$ objects of each type. See combinations with repetition.

N. F. Taussig
  • 76,571