# 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\}$

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.

• 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.
– lulu
Jul 22, 2022 at 8:06
• Note my remark on notation. Doesn't change the content of your argument, but might avoid some ambiguity.
– lulu
Jul 22, 2022 at 8:09
• 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$. Jul 22, 2022 at 10:57

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.