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 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.)
I’m the student asked the question 😉
Well, I got the partial solution finally, here is the question that I tried to solve by the equation x + 2y = n, x,y,n > 0
Let n be a positive integer. Harry’s school year has n school days. Harry has budget of exactly $n for buying exactly one snack per day at school. There are only two types of snacks available: M&M for $1. 00 per packet, or a pair of bananas at $2.00 per pair. The following restrictions must apply to Harry.
(1) Harry must spend all $n on snacks during the school year.
(2) Harry does not have to buy a snack each school day.
At the end of the school year, Harry must report how many times he bought M&M, and how many times he bought bananas. How many different reports are possible?
Anyway, thank you for your posting 🙂 It helps me to understand the solution better.
I’m glad this helped. Marion mentioned to me the `M&Ms problem’ the other day, I figured this was the same question without distractions.