# Partitioning Integers using only elements from a specific set

I know how to partition given $p(x)$ using a generating function as my textbook on discrete mathematics explains it in detail. However, I want to know if it is possible to restrict the source elements of the partition? So, given I want to find the partition of $x$ is it possible to do it using only elements from $S={y_1, y_2, y_3, ..., y_p : y_i \in \mathbb{Z} \forall i}$.

An example might be partition any number using only 4 and 9.

If so, how?

This is a homework question of sorts but this is not the actual homework question (because I can solve that - I just can't find a general answer for it yet and this is a way I think I can generalise (possibly)).

-
Just a recommendation: If you're interested in these things, you will surely love the wonderful little book "Integer partitions" by George Andrews & Kimmo Eriksson. amazon.com/Integer-Partitions-George-E-Andrews/dp/0521600901 – Hans Lundmark Sep 20 '10 at 20:24
@Hans thanks very much. When they finally let me back in the library I'll see if we've got it. – user892 Sep 21 '10 at 10:25

## 1 Answer

It's the same generating function method. If $p_S(n)$ denotes the number of partitions of $n$ using only positive integers in some set $S \subset \mathbb{N}$, then

$$\sum_{n \ge 0} p_S(n) x^n = \prod_{s \in S} \frac{1}{1 - x^s}.$$

A popular choice is $S = \{ 1, 5, 10, 25 \}$ (the problem of making change). When $S$ is finite the above function is rational and it is possible to give a closed form for $p_S$.

If the question is about whether such a partition exists at all, for sufficiently large $n$ this is possible if and only if the greatest common divisor of the elements of $S$ divides $n$. For small $n$ there are greater difficulties; see the Wikipedia article on the Frobenius problem. When $|S| = 2$ (say $S = \{ a, b \}$) and the elements of $S$ are relatively prime, the largest $n$ for which no such partition exists is known to be $ab - a - b$. When $a = 4, b = 9$ this gives $23$, so for any $n \ge 24$ such a partition always exists.

-
Thanks Qiaochu, I did wonder if it would be similar to the existing formula but it was late and I couldn't think it through. +1 and the answer I needed. – user892 Sep 21 '10 at 10:24