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

Advertisements

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: