A student asked me the other day the following rather homework-looking question: Given a natural number , how many solutions does the equation
have for and natural numbers?
The question has a very easy answer: Simply notice that and that any like this determines a unique such that is a solution. So, there are solutions if is even (as can be any of ), and there are solutions if is odd.
I didn’t tell the student what the answer is, but I asked what he had tried so far. Among what he showed me there was a piece of paper in which somebody else had scribbled
which caught my interest, and is the reason for this posting.
I don’t think the student had seen the connection between this product of two series, let’s call it , and his question. If we denote by the number of solutions to the equation, the series is the generating function of the sequence , i.e.,
To see this, notice that the coefficient of in is precisely the number of ways we can write as a product of a term from the first series and a term from the second one, i.e., it is the number of solutions with and natural numbers to the equation or, equivalently, . That is to say, the coefficient of in is exactly .
This gives us a purely algebraic (analytic?) way of solving the question, even if there is no understanding of how to approach it from a combinatorial point of view.
Both series on the product that makes up are geometric series, so we have
Using the method of partial fractions decomposition, we see that Notice that , so
or , that is,
that of course coincides with the formula we obtained earlier by combinatorial considerations.
The question the student had is a very simple example of a problem about integer partitions, a beautiful area of mathematics that I hope I am not misconstruing by thinking of it as a branch of combinatorial number theory. The technique of generating functions is a very useful and powerful combinatorial tool that I have always found quite nice although, granted, its use is a bit of an overkill for the question at hand. At the same time, this technique provides us with a (standard) method for solving any problem of the same kind: For fixed natural numbers , find for each the number of tuples of natural numbers such that
One can then go further to study the much subtler partition function and its relatives.
(And I still don’t know the name of the student, who didn’t bother to introduce himself, and I have no idea who suggested to him to look at to begin with.)