2
$\begingroup$

This is a part of a bigger problem I was solving.

Problem: $N$ is a positive integer. There are $k$ number of other positive integers ($\le N$) In how many ways can you make $N$ by summing up any number of those $k$ integers. You can use any integer, any number of times.

For example: $N = 10$, $k=1: \{ 1 \}$

then there's only $1$ way of making $10$ using integers in braces: $1+1+1+1+\cdots+1 = 10$

another example: $N = 10$, $k = 2: \{ 1, 3\}$

number of ways $= 4$:

$1,1,1,1,1,1,1,1,1,1$
$1,1,1,1,1,1,1,3$
$1,1,1,1,3,3$
$1,3,3,3$

The question is to derive a generalized logic/formula to calculate the number of ways.

  • 0
    Related: http://mathworld.wolfram.com/PartitionFunctionP.html2011-11-06
  • 1
    Pretty simple to do in *Mathematica*: `subsetPartitions[n_Integer?Positive, vec_List] := Flatten[MapThread[ConstantArray, {vec, #}]] & /@ FrobeniusSolve[vec, n] /; VectorQ[vec, IntegerQ] && Apply[And, Thread[0 < vec <= n]]` does the job. Try `subsetPartitions[10, {1, 3}]`.2011-11-07
  • 2
    @J.M. Or, equivalently, using _Mathematica_'s built-in command `IntegerPartitions[10, All, {1, 3}]`.2011-11-07

4 Answers 4