0
$\begingroup$

I am confused with how to choose the correct $k$ value in the,$\binom{n}{k}$ formula. By writing down all the possibilities I get $7$.

A $3$-digit word $(x_1,x_2,x_3)$ with $x_k \in \{0, 1, 2\}$ for $1 \leq k \leq 3$. How many $3$-digit words have a sum of $3$?

Number of words = $ \frac{n!}{k!(n-k)!} = \frac{3!}{2!(2-3)!} = 3$

$\endgroup$
2
  • $\begingroup$ Are you really interested in calculating a probability? The way you posed the question, you seem to be interested in the number of outcomes with sum $7$, in which case this is a combinatorics question rather than a probability question. $\endgroup$ Sep 20, 2017 at 23:36
  • $\begingroup$ Will edit question $\endgroup$ Sep 20, 2017 at 23:38

3 Answers 3

2
$\begingroup$

There is one way of selecting (1,1,1), and there are choose(3, 1) = 3 possible locations of a 0 in a word. There are two ways each of the remaining two positions could have a 1 and a 2, so the total number words using {0, 1, 2} that sum to 3 is: 1 + 2*3 = 1 + 6 = 7, as you found by brute force.

$\endgroup$
1
$\begingroup$

We want the number of solutions of the equation $$x_1 + x_2 + x_3 = 3 \tag{1}$$ in the nonnegative integers subject to the restrictions that $x_1, x_2, x_3 \leq 2$.

A particular solution of equation 1 corresponds to the placement of two addition signs in a row of three ones. For instance, $$1 + + 1 1$$ corresponds to the solution $x_1 = 1$, $x_2 = 0$, and $x_3 = 2$. The number of solutions of equation 1 is $$\binom{3 + 2}{2} = \binom{5}{2}$$ since we must choose which two of the five positions (for three ones and two addition signs) will be filled with addition signs.

From these, we must exclude those solutions in which one of the variables exceeds $2$. By inspection, there are three such solutions, namely $(3, 0, 0)$, $(0, 3, 0)$, and $(0, 0, 3)$.

Hence, the number of solutions is $$\binom{5}{2} - \binom{3}{1} = 10 - 3 = 7$$

$\endgroup$
4
  • $\begingroup$ Could I do this: $ \binom{3}{3} + \binom{3}{2} * (1 - \binom{3}{1})$ $\endgroup$ Sep 21, 2017 at 11:54
  • $\begingroup$ Your answer is negative. $$\binom{3}{3} + \binom{3}{1}\left[1 - \binom{3}{1}\right] = 1 + 3(1 - 3) = 1 + 3(-2) = 1 - 6 = -5$$ If you explain what the numbers in your calculation represent, I may be able to help you fix your attempt. $\endgroup$ Sep 21, 2017 at 12:02
  • 1
    $\begingroup$ You seem to be trying to reproduce @Rafael_Espericueta's solution using binomial coefficients. As Rafael observed, there are two possibilities: the sum of $3$ is obtained with three $1$s or it is obtained with one $0$, one $1$, and one $2$. With this approach, we must count distinguishable permutations of the sequences $(1, 1, 1)$ and $(0, 1, 2)$. There is one distinguishable permutation of the sequence $(1, 1, 1)$. There are $3! = 6$ permutations of the sequence $(0, 1, 2)$. Hence, there are a total of $1 + 6 = 7$ possible words. To type $\binom{n}{k}$, type \binom{n}{k} in math mode. $\endgroup$ Sep 21, 2017 at 14:10
  • 1
    $\begingroup$ It is possible to express @Rafael_Espericueta's solution using binomial coefficients. We can place a $1$ in all three positions in $\binom{3}{3}$ ways. We can place a $0$ in one of the three positions in $\binom{3}{1}$ ways, a $1$ in one of the two remaining positions in $\binom{2}{1}$ ways, and a $2$ in only the remaining position in $\binom{1}{1}$ ways. Therefore, the number of permissible ternary words is $$\binom{3}{3} + \binom{3}{1}\binom{2}{1}\binom{1}{1} = 1 + 3 \cdot 2 \cdot 1 = 1 + 6 = 7$$ $\endgroup$ Sep 21, 2017 at 14:42
0
$\begingroup$

Brute force may become cumbersome if the words are longer (for example, try counting 5 bit words with sum equal to 9). An easier way for these types of problems is the following:

The number of words that sum to 3 is the coefficient of $x^3$ in the product \begin{align*} (1+x+x^2)^3 &= \left(\frac{1-x^3}{1-x}\right)^3 \\ &= (1-x^3)^3(1-x)^{-3}\\ &= (1-3x^3+3x^6-x^9)\left(1+3x+\frac{3\cdot 4}{1\cdot 2} x^2 + \frac{3\cdot 4 \cdot 5}{1\cdot 2 \cdot 3}x^3 + \cdots\right)\\ \end{align*} and hence equals $$ \frac{3\cdot 4 \cdot 5}{1\cdot 2 \cdot 3} - 3 = 7$$

$\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.