Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)).

share|improve this question
    
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. –  Ninefingers Sep 21 '10 at 10:25
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Ninefingers Sep 21 '10 at 10:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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