## Partitioning numbers

A student asked me the other day the following rather homework-looking question: Given a natural number $n$, how many solutions $(x,y)$ does the equation

$n=x+2y$

have for $x$ and $y$ natural numbers?

The question has a very easy answer: Simply notice that $0\le 2y\le n$ and that any $y$ like this determines a unique $x$ such that $(x,y)$ is a solution. So, there are $\frac n2 +1$ solutions if $n$ is even (as $y$ can be any of $0,1,\dots,n/2$), and there are $\frac{n+1}2$ solutions if $n$ 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

$(1+t+t^2+t^3+\dots)(1+t^2+t^4+t^6+\dots),$

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 $S(t)$, and his question. If we denote by $a_n$ the number of solutions to the equation, the series $S(t)$ is the generating function of the sequence $a_0,a_1,\dots$, i.e.,

$S(t)=a_0+a_1t+a_2t^2+\dots$

To see this, notice that the coefficient of $t^n$ in $S(t)$ is precisely the number of ways we can write $t^n$ 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 $(a,b)$ with $a$ and $b$ natural numbers to the equation $t^a t^{2b}=t^n$ or, equivalently, $a+2b=n$. That is to say, the coefficient of $t^n$ in $S(t)$ is exactly $a_n$.

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 $S(t)$ are geometric series, so we have $\displaystyle S(t)=\frac1{1-t}\frac1{1-t^2}=\frac1{(1-t)^2(1+t)}.$

Using the method of partial fractions decomposition, we see that $\displaystyle S(t)=\frac{1/4}{1-t}+\frac{1/2}{(1-t)^2}+\frac{1/4}{1+t}.$ Notice that $\displaystyle \frac1{(1-t)^2}=\left(\frac1{1-t}\right)'$, so

$\displaystyle S(t)=\frac14\left[\sum_{n=0}^\infty t^n+2\sum_{n=0}^\infty (n+1)t^n+\sum_{n=0}^\infty(-1)^nt^n\right],$

or $S(t)=\frac14\sum_{n=0}^\infty (2n+3+(-1)^n) t^n$, that is,

$\displaystyle a_n=\frac{2n+3+(-1)^n}4,$

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 $\alpha_1,\dots,\alpha_k$, find for each $n$ the number of tuples $(x_1,\dots,x_k)$ of natural numbers such that

$\alpha_1 x_1+\dots+\alpha_k x_k=n.$

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 $S(t)$ to begin with.)

### 2 Responses to Partitioning numbers

1. Eliot I says:

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.

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