Number of ways to form $24$ using $7$,$3$ and $2$

Question

$\text{What is the number of ways to form }24\text{ using }7,2,\text{ and }3,\text{ zero or more times?}$

We can write $24$ as $7a+3b+2c$ . Since $\lfloor\frac{24}{7}\rfloor = 3,$ $\lfloor\frac{24}{3}\rfloor = 8$ and $\lfloor\frac{24}{2}\rfloor = 12$ ,We can say $0 \le a \le 3$ , $0 \le b \le 8$ and $0 \le c \le 12$.Then I put $a = 0,1,2,3$ and I got $11$ ways.

They are

$1. 7*3+ 2*0 +3*1$

$2. 7*2+ 2*5+ 3*0$

$3. 7*2+ 2*2 +3*2$

$4. 7*1 +2*7+ 3*1$

$ 5. 7*1 +2*4 +3*3$

$ 6. 7*1+ 2*1+ 3*5$

$ 7. 7*0+ 2*12 +3*0$

$8. 7*0 +2*9 +3*2$

$9. 7*0+ 2*6+ 3*4$

$10. 7*0 +2*3+ 3*6$

$11. 7*0 +2*0 +3*8$

Is there any efficient way of calculating this kind of problem??

Answer 1

As @user2661923 mentioned, we need to use generating functions. Take a look at this question first to get a grasp of the theory. In general, we need to construct a polynomial of sums, where the exponents correspond to the values our variables can take. For example, to calculate the number of non-negative solutions to your problem: $$7x_1 + 3x_2 + 2x_3 = 24$$ with constraints: $$0 \leq x_1 \leq 3$$ $$0 \leq x_2 \leq 8$$ $$0 \leq x_3 \leq 12,$$ we need to observe that this is the same, as the number of non-negative solutions to: $$y_1 + y_2 + y_3 = 24$$ with constraints $$y_1 \in \{0, 7, 14, 21\}$$ $$y_2 \in \{0, 3, \dots, 21, 24\}$$ $$y_3 \in \{0, 2, \dots, 22, 24\}.$$

Therefore, the corresponding generating function is $$ P(y) = (1 + y^7 + y^{14} + y^{21})(1+ y^3+\dots +y^{24})(1+y^2+\dots+y^{24})$$ Let us denote the factors as $p_7, p_3, p_2$ respectively, i.e. $P(y) = p_7 \cdot p_3 \cdot p_2$. Now, the number of the solutions is equal to the coefficient corresponding to $y^{24}$ in the extended form of $P(y)$ - we look at $y^{24}$, because we want our number to sum to $24$. In general, the way to do this is to expand the polynomial and check the coefficient. There are some tricks applicable to selected cases, but nothing that works for all of them. The coefficient corresponding to $y^{24}$ in $P(y)$ is equal to $11$, which confirms your result.

Answer 2

Note that once you've found $a$ and $b$, you can calculate $c$ directly:

$$c = \frac{24-7a-3b}{2}$$

This limits your search space to the 36 possible combinations of $(a, b)$ with $0 \le a \le 3$ and $0 \le b \le 8$.

Also, we need $c \ge 0$, which means that once we've set a value for $a$, we can constrain $7a + 3b \le 24$, or $b \le \frac{24 - 7a}{3}$. This reduces the number of valid $(a, b)$ combinations to 21.

For $c$ to be an integer, we must have $24 - 7a - 3b$ be even. This means that $a$ and $b$ must be either both even or both odd.

This gives us a reasonably efficient algorithm for enumerating the solutions.

for a = 0 to 3:
    for b = (a mod 2) to floor((24 - 7a) / 3) step 2:
        c = (24 - 7a - 3b) / 2
        print(a, b, c)

Where a mod 2 equals 0 if a is even, or 1 if a is odd, thus ensuring that b has the same parity as a.

This can straightforwardly be converted to a computer program, or even done manually.