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

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

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.

(1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (2009g:91038). Given a finite set $S$ of points in the plane $\mathbb R^2$, consider the following game between two players Maker and Breaker. The players alternat […]

Yes. This is a consequence of the Davis-Matiyasevich-Putnam-Robinson work on Hilbert's 10th problem, and some standard number theory. A number of papers have details of the $\Pi^0_1$ sentence. To begin with, take a look at the relevant paper in Mathematical developments arising from Hilbert's problems (Proc. Sympos. Pure Math., Northern Illinois Un […]

I am looking for references discussing two inequalities that come up in the study of the dynamics of Newton's method on real-valued polynomials (in one variable). The inequalities are fairly different, but it seems to make sense to ask about both of them in the same post. Most of the details below are fairly elementary, they are mostly included for comp […]

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

First of all, $f(z)+e^z\ne 0$ by the first inequality. It follows that $e^z/(f(z)+e^z)$ is entire, and bounded above. You should be able to conclude from that.

Yes. The standard way of defining these sequences goes by assigning in an explicit fashion to each limit ordinal $\alpha$, for as long as possible, an increasing sequence $\alpha_n$ that converges to $\alpha$. Once this is done, we can define $f_\alpha$ by diagonalizing, so $f_\alpha(n)=f_{\alpha_n}(n)$ for all $n$. Of course there are many possible choices […]

I disagree with the advice of sending a paper to a journal before searching the relevant literature. It is almost guaranteed that a paper on the fundamental theorem of algebra (a very classical and well-studied topic) will be rejected if you do not include mention on previous proofs, and comparisons, explaining how your proof differs from them, etc. It is no […]

No, the rank of a set $x$ is the least $\alpha$ such that $x\in V_{\alpha+1}$. Note that if $\alpha$ is limit, any $x\in V_\alpha$ belongs to some $V_\beta$ with $\beta

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.

Hi Eliot,

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.