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

This entry was posted on Wednesday, October 22nd, 2008 at 11:08 pm and is filed under 175: Calculus II, 306: Number theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to Partitioning numbers

Eliot I says:

October 23, 2008 at 12:35 pm

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.

Reply
andrescaicedo says:

October 23, 2008 at 3:02 pm

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.

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

A kind of library