Exercise. Determine the number of sequences $(a_1,a_2,a_3,a_4,a_5)\in \{0,1,2\}^5$, such that $\sum_{i=1}^{k}a_i\ne3,\forall k\in\{1,2,...,5\}$.

Attempt. The total number of sequences is $3^5$. If we find the set of all the solutions to the indefinite equation $$a_1+a_2+a_3+a_4+a_5=3,\forall j\in\{1,2,...,5\}:a_j\in\{0,1,2\}.$$

Then, we shall get the result by subtracting the number of solutions from the total number of sequences since each of the above restrictions is counted precisely once. There are $7 \choose 3$ solutions to the indefinite equation. But we have to eliminate $5$ of them when some $a_j=3$. Thus, the answer is:$$3^5-{7\choose3}+5=213.$$

Is my solution correct?

Any help is appreciated.

  • 2
    $\begingroup$ Yes, this looks good. For phrasing: it's a little confusing to use the same variables $\{a_i\}$ for both the original sequence and for the abstract sequence you used for counting. It confused me, for example, when you considered the case $a_j=3$ which, of course, is impossible for the first equation, but allowed by the second. Consider using different variables to avoid confusion. $\endgroup$
    – lulu
    Jul 22, 2022 at 8:06
  • 1
    $\begingroup$ Note my remark on notation. Doesn't change the content of your argument, but might avoid some ambiguity. $\endgroup$
    – lulu
    Jul 22, 2022 at 8:09
  • 2
    $\begingroup$ Maybe I misunderstood the question, but you need to count the number of sequences such that $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, $a_1+a_2+a_3+a_4$ and $a_1+a_2+a_3+a_4+a_5$ are all different from $3$. Alternatively, you need to eliminate the cases where one of the sums is $3$, not only $a_1+a_2+a_3+a_4+a_5$. $\endgroup$
    – Taladris
    Jul 22, 2022 at 10:57

1 Answer 1


No, this is not correct.

Spelled out, $\forall k\in\{1,2,...,5\}:\sum_{i=1}^{k}a_i\ne3$ is the condition that $a_1\neq 3$, $a_1+a_2\neq 3$, $a_1+a_2+a_3\neq 3$, $a_1+a_2+a_3+a_4\neq 3$, $a_1+a_2+a_3+a_4+a_5\neq 3$.

You have only considered $a_1+a_2+a_3+a_4+a_5\neq 3$ (or, its negation).

As the possibilities are small ($3^5=243$), I'm going to argue by cases:

$a_1\in \{0,1,2\}$ so we have no issue satisfying $a_1\neq 3$.

$a_1+a_2\neq 3$ leaves us with $(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)$ as options. We only care about $a_1+a_2$ for further reasoning, so we can treat the three instances of $a_1+a_2=2$ ($(1,1),(2,0),(0,2)$ identically, and the two instances of $a_1+a_2=1$ ($(0,1),(1,0)$) identically.

As $a_i\ge 0$, starting with $(2,2)$ gives $3^3=27$ valid combinations for $a_3,a_4,a_5$.

For $a_1+a_2=2$, if $a_3=2$ then we can choose any $a_4,a_5$ for $3^2=9$ valid combinations. If $a_3=0,a_4=2$ then any $a_5$ is valid, for $3$ solutions. If $a_3=0,a_4=0$ then $a_5=0$ or $a_5=2$ work, for $2$ solutions. We have $9+3+2=14$ options for $(a_3,a_4,a_5)$. And there were $3$ ways of getting $a_1+a_2=2$, so that's $42$ solutions total.

For $a_1+a_2=1$, the combinations for $(a_3,a_4,a_5)$ are: $(1, 2, a_5),(1, 0, 2),(1, 0, 0),(0, 1, 2),(0, 1, 0),(0, 0, 1),(0, 0, 0)$. This is $9$ options. There are two options for $a_1+a_2=1$ so that gives us $18$ solutions total.

For $(0,0)$, we repeat our logic from before to find that $(a_3,a_4)\in \{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)\}$. We can have (for $(a_3,a_4,a_5)$) $(0,0,a_5),(0,1,0/1),(1,0,0/1),(0,2,0/2),(1,1,0/2),(2,0,0/2)(2,2,a_5)$ for $16$ solutions.

Thus, we've found $27+42+18+16=103$ solutions out of the $243$ possible combinations. Some quick and dirty Python code tells me that this is true.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .