0
$\begingroup$

Given a set $X$ of $m$ distinct positive integers $X = \{x_1,x_2,\dots,x_m\}$ and a positive integer $N$, in how many ways can $N$ be expressed as a sum $N = \sum_i y_i$ with $y_i\in X$? The order of the sum does not matter.

$\endgroup$
  • $\begingroup$ Seems like more information on the $x_i$ would be needed. Did you make any progress on this? $\endgroup$ – Joffan Jun 15 '18 at 23:56
  • $\begingroup$ That is a partition of $N$, with parts belonging to the set $X$, and in general does not have a close form. $\endgroup$ – G Cab Jun 16 '18 at 0:02
  • $\begingroup$ You might be interested in the "subset sum problem". en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$ – awkward Jun 16 '18 at 15:05
0
$\begingroup$

Without further information on the nature of the $x_i$, I can only offer $$\sum_{S\subseteq X}\large\delta_{(\sum_S s_i)(N)}$$ where $\delta_{ij}$ is the Kronecker delta. Basically though this is just re-stating the problem.

There might be more scope for useful description for special forms like $X=\{1,2,3,\ldots,m\}$ but even then because the number of elements in the subset is variable, there's no clean transformation to another partition.

$\endgroup$
0
$\begingroup$

A recursive definition of a function which returns the number of those partitions might look like this: $$ \begin{align} f(N, X) &= 0 \quad (N \le 0) \\ f(N, \emptyset) &= 0 \\ f(N, \{ x \} \cup X) &= \delta[N–x] + f(N-x, X) + f(N, X) \end{align} $$ where I used the Dirac delta in discrete / DSP notation: $$ \delta[n] = \begin{cases} 1 & \text{if } n=0 \\ 0 & \text{if } n\in \mathbb{Z}\setminus\{0\} \end{cases} $$ Update: I assumed the elements of $X$ being used only once in the sum.

$\endgroup$
  • $\begingroup$ Note that a member $x\in X$ can appear multiple times in the sum. But writing a recursion is seems like a good idea. The choice can be whether $x$ is chosen at least once, or not. This leads to: $f(N, X\cup \{x\}) = f(N - x, X\cup \{x\}) + f(N, X)$ $\endgroup$ – becko Jun 16 '18 at 9:37
  • $\begingroup$ Also you can define $f(0, X) = 1$ instead of 0. Since the empty set is a subset of $X$. $\endgroup$ – becko Jun 16 '18 at 9:41
  • $\begingroup$ Maybe the recursion can be solved for special cases of $X$? $\endgroup$ – becko Jun 16 '18 at 9:41
  • $\begingroup$ I have to rethink the problem for multiple use in the sum. $\endgroup$ – mvw Jun 16 '18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.