How to find all the solutions to $a+2b+3c+\cdots+9i=45$

Question

I want to find all the solutions to the equation $a+2b+3c+4d+5e+6f+7g+8h+9i=45$ where all of the variables can only be of $3$ values: $0,1,2$

I know there are a few solutions for example, set all of them to be $1$, or $a=1, b=2, c=0, d=1, e=0, f=2, g=1, h=1, i=1$.

I tried to turn them all into mod $3$ and I got:

$a+2b+d+2e+g+2h\equiv 0 \pmod 3$ but I don't know what to do after that.

I understand that there may be ~$7\times 10^{20}$ solutions

Answer 1

Since all variables may assume one of $3$ values, the candidate space is only $3^9$ and a one-liner brute-force Python program will count the solutions for us:

from itertools import product
print(len([c for c in product((0,1,2), repeat=9) if sum(a*b for (a,b) in enumerate(c,1)) == 45]))

The answer is $547$. There is no simple general way to count solutions to partition problems like this where the variables have multiplicative coefficients behind them.

Answer 2

As @robjohn mentioned , you can find the number of all solutions using generating functions. If the possible values for the variables are $0,1,2$ ,we can say that

• $a:0,1,2$ . Hence , its generating function is $$x^0+x^1+x^2 = \frac{1-x^3}{1-x}$$

• If "b" can take the values of $0,1,2$ , then $2b:0,1,4$ . Hence , its generating function is $$x^0+x^2+x^4 = \frac{1-x^6}{1-x^2}$$

• If "c" can take the values of $0,1,2$ , then $3c:0,3,6$ . Hence , its generating function is $$x^0+x^3+x^6 = \frac{1-x^9}{1-x^3}$$

• If "d" can take the values of $0,1,2$ , then $4d:0,4,8$ . Hence , its generating function is $$x^0+x^4+x^8 = \frac{1-x^{12}}{1-x^4}$$

• If "e" can take the values of $0,1,2$ , then $5e:0,5,10$ . Hence , its generating function is $$x^0+x^5+x^{10} = \frac{1-x^{15}}{1-x^5}$$

• If "f" can take the values of $0,1,2$ , then $6f:0,6,12$ . Hence , its generating function is $$x^0+x^6+x^{12} = \frac{1-x^{18}}{1-x^6}$$

• If "g" can take the values of $0,1,2$ , then $7g:0,7,14$ . Hence , its generating function is $$x^0+x^7+x^{14} = \frac{1-x^{21}}{1-x^7}$$

• If "h" can take the values of $0,1,2$ , then $8h:0,8,16$ . Hence , its generating function is $$x^0+x^8+x^{16} = \frac{1-x^{24}}{1-x^8}$$

• If "i" can take the values of $0,1,2$ , then $9i:0,9,18$ . Hence , its generating function is $$x^0+x^9+x^{18} = \frac{1-x^{27}}{1-x^9}$$

Now , find the coefficient of $x^{45}$ in the expansion of $$\bigg(\frac{1-x^{3}}{1-x}\bigg)\bigg(\frac{1-x^{6}}{1-x^2}\bigg)\bigg(\frac{1-x^{9}}{1-x^3}\bigg)\bigg(\frac{1-x^{12}}{1-x^4}\bigg)\bigg(\frac{1-x^{15}}{1-x^5}\bigg)\bigg(\frac{1-x^{18}}{1-x^6}\bigg)\bigg(\frac{1-x^{21}}{1-x^7}\bigg)\bigg(\frac{1-x^{24}}{1-x^8}\bigg)\bigg(\frac{1-x^{27}}{1-x^9}\bigg)$$

NOTE: You can use sofwares such as SageMath to find the coefficent of $x^{45}$ in the expansion , i generally use wolfram alpha but this expansion was long for wolfram

Answer 3

Here's a dynamic programming strategy. Slightly more generally, suppose the problem is to find the solutions to $\sum_{i=1}^m c_i x_i = b$ where $x_i \in \{0,1,2\}$, and $A(m,b)$ is the set of solutions to this.

Note that $A(m,b)$ is empty if $b < 0$ or $b > 2 \sum_{i=1}^m c_i$. Otherwise we consider the three possibilities $x_m = 0, 1, 2$, corresponding to the partial solution sets $A(m-1,b)$, $A(m-1,b-c_m)$ and $A(m-1,b-2 c_m)$. Evaluate these recursively. The partial solution sets should be remembered when they are computed, because the same ones may be needed again.

Here is Maple code:

C:= [1,2,3,4,5,6,7,8,9]:
M:= 2*ListTools:-PartialSums(C):
A:= proc(m,b) option remember; local t,i;
      if m = 0 then if b = 0 then return {[]} else return {} fi fi;
      if b < 0 or b > M[m] then return {} fi;
      `union`(seq(map(t -> {x[m]= i, op(t)}, A(m-1,b-C[m]*i)),i=0..2))
end proc:
Solutions:= A(9,45):

It takes 0.016 seconds on my computer.