Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and the elements of $S$ lie within the range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number of partitions of n using only the elements from $S$ as summands (over all such possible sets).

For example, If $S$ is $\{1, 1, 2, 2\}$, there are $3$ ways in which $n=4$ may be partitioned using elements from S:

$2+2$

$1+1+2$

$1+1+2$

The sequence $1+1+2$ has repeated because we treat each element in $S$ as different. With $1+1$, We can either take 2 at the 3rd position or $2$ at the $4th$ position in S above. Another $S$ may be $\{1,1,1,1\}$ in which case there is only one partition of $n=4$ given by $1+1+1+1$.

There are $2^n$ subsets of S. But since only a few subsets might sum to n, I expect the bound to be asymptotically lower than $O(2^n)$.

Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and each of the elements of $S$ lie within the range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number of partitions of $n$ using only the elements from $S$ as summands (over all such possible sets).

For example, If $S$ is $\{1, 1, 2, 2\}$, there are $3$ ways in which $n=4$ may be partitioned using elements from $S$:

$2+2$

$1+1+2$

$1+1+2$

The sequence $1+1+2$ has repeated because we treat each element in $S$ as different. With $1+1$, We can either take $2$ at the 3rd position or $2$ at the $4th$ position in $S$ above. Another $S$ may be $\{1,1,1,1\}$ in which case there is only one partition of $n=4$ given by $1+1+1+1$.

There are $2^n$ subsets of $S$. But since only a few subsets might sum to $n$, I expect the bound to be asymptotically lower than $O(2^n)$.

Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and the elements of $S$ lie within range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number of partitions of n using only the elements from $S$ as summands (over all such possible sets).

For example, If $S$ is $\{1, 1, 2, 2\}$, there are $3$ ways in which $n=4$ may be partitioned using elements from S:

$2+2$

$1+1+2$

$1+1+2$

The sequence $1+1+2$ has repeated because we treat each element in $S$ as different. With $1+1$, We can either take 2 at 3rd position or $2$ at $4th$ position in S above. Another $S$ may be $\{1,1,1,1\}$ in which case there is only one partition of $n=4$ given by $1+1+1+1$.

There are $2^n$ subsets of S. But since only a few subsets might sum to n, I expect the bound to be asymptotically lower than $O(2^n)$.

Given a multiset $S$ of integers and an integer $n$. The size of $S$ is $n$ and the elements of $S$ lie within the range $1$ to $n-1$. Give a tight upper bound (in terms of $n$) on the number of partitions of n using only the elements from $S$ as summands (over all such possible sets).

For example, If $S$ is $\{1, 1, 2, 2\}$, there are $3$ ways in which $n=4$ may be partitioned using elements from S:

$2+2$

$1+1+2$

$1+1+2$

The sequence $1+1+2$ has repeated because we treat each element in $S$ as different. With $1+1$, We can either take 2 at the 3rd position or $2$ at the $4th$ position in S above. Another $S$ may be $\{1,1,1,1\}$ in which case there is only one partition of $n=4$ given by $1+1+1+1$.

There are $2^n$ subsets of S. But since only a few subsets might sum to n, I expect the bound to be asymptotically lower than $O(2^n)$.