ways of expressing T as the sum of four elements of S. [closed]

Question

In this task you will give a sequence of numbers $S$ of length $N$. Every element will be greater than or equal to 1. We write $S[i]$ to refer to the $i$-th element of the sequence. For example $S = (1, 2, 3, 4, 5, 4)$ is of length $6$ and $S[2] = 2, S[6] = 4$ and so on. You will also be given a number $T$, called the target.

We would like to find four elements of the sequence $S$ whose sum is $T$. More precisely, we would like to find four numbers $i, j, k, \ell$, with $1 ≤ i < j < k < \ell ≤ N$ such that $$T = S[i] + S[j] + S[k] + S[\ell].$$

If $T = 16$ then there is a unique way to do this which is to take $i = 3, j = 4$, $k = 5$ and $\ell = 6$. Finally, $T = 9$ cannot be written as the sum of $4$ elements of the sequence $S$ and thus the number of ways in this case is $0$.

For the following $S$ and $T$ find the number of ways of expressing $T$ as the sum of four elements of $S$.
(a) $S = (2, 1, 1, 1, 2, 1, 2, 2, 1)$ and $T = 6$
(b) $S = (2, 1, 2, 1, 3, 3, 1, 2, 1)$ and $T = 9$
(c) $S = (1, 3, 2, 1, 1, 3, 4, 2, 2)$ and $T = 8$

Is there any mathematical way of finding the number of ways, because counting manually will take a long time.
Ans:- (a) 60 (b) 14 (c) 30

Answer 1

(a) With four summands and only $1$'s and $2$'s, the only way is to pick two $2$'s and two $1$'s. Hence: ${4\choose 2}{5\choose 2}$

(b) If we use none of the $3$'s, we cannot reach $9$ with four $1$'s or $2$'s. If we use one of the $3$'s, we need to reach $6$ with three $1$'s or $2'$s, i.e., with three $2$'s. If we use both $3$'s, we need to reach $3$ with two $1$'s or $2$'s, i.e., one each. Hence: ${2\choose 1}{3\choose 3}+{2\choose 2}{3\choose 1}{4\choose 1}$.

(c) can be used similarly, though we need yet another level to handle the $4$ ...

Answer 2

Any sequence $S$ with length $\ell$ can be associated to a bivariate polynomial $$ p_S(x,y)=\prod_{k=1}^{\ell}\left(1+ y x^{S[k]}\right),$$ then the answer is given by the coefficient of $y^4 x^T$ in $p_S(x,y)$.