Number of ways of expressing n as a s... Log Out | Topics | Search Moderators | Register | Edit Profile

 Ask NRICH » Onwards and Upwards » Number of ways of expressing n as a sum of positive integers « Previous Next »

Author Message
Oliver Bel
Regular poster

Post Number: 57
 Posted on Wednesday, 06 November, 2013 - 06:57 pm:

I've managed part (a) fairly easily. Any hints for part (b)? I've been trying to find a formula for hours.. but can't see any nice pattern.
Daniel Fretwell
Veteran poster

Post Number: 2013
 Posted on Thursday, 07 November, 2013 - 10:40 am:

I think the key word at the end is "try".

There is currently no known answer for this question...well no closed form formula in terms of just $n$. What recursion did you find?

What you are studying here is the so called partitions of $n$, i.e. ways of breaking $n$ up into sums of positive integers (without caring about order).

These things are quite difficult to study.

http://en.wikipedia.org/wiki/Partition_(number_theory)

The reason this part is harder than a) is because of the overcounting you achieve by solving a). The recursion you got there was easy to solve whereas any recursion you might find in b) will not be so easy to solve.
Oliver Bel
Regular poster

Post Number: 59
 Posted on Thursday, 07 November, 2013 - 02:14 pm:

Ah, a trick question, well I haven't been able to express the nth term in terms of earlier terms either. Any hints?
Daniel Fretwell
Veteran poster

Post Number: 2018
 Posted on Thursday, 07 November, 2013 - 06:12 pm:

There are a few different recursions on the Wikipedia page but none of them are simple to get. I can't think what the intended answer should be.
Oliver Bel
Regular poster

Post Number: 60
 Posted on Thursday, 07 November, 2013 - 11:46 pm:

I looked at the Wiki article and probably wouldn't have figured the recursion stuff out myself. I understand $\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)$ since it's just $(1 + x + x^2 + x^3 + ...)(1 + x^2 + x^4 + x^6 + ...)(1 + x^3 + x^6 + x^9 + ...) ....$ and intuitively the coefficient of $x^n$ will be all the partitions of $n$.

Though I'm not sure why $(1-x)(1-x^2)(1-x^3) \dots = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} + \dots.$ where the powers are the pentagonal numbers. How can this be proved?
Daniel Fretwell
Veteran poster

Post Number: 2021
 Posted on Thursday, 07 November, 2013 - 11:58 pm:

I think you were supposed to get the recursion found here at equn 15:

http://mathworld.wolfram.com/Partition.html

This involves the function in part a).

As for your new question, again this is something quite famous called Euler's pentagonal number formula.

It is proved here:

http://www.math.uiuc.edu/~reznick/2690367.pdf
Oliver Bel
Regular poster

Post Number: 61
 Posted on Friday, 08 November, 2013 - 12:08 am:

What do you mean by equation 15? I can't find it on that page.
Daniel Fretwell
Veteran poster

Post Number: 2022
 Posted on Friday, 08 November, 2013 - 09:22 am:

Oh I sent the wrong link:

http://mathworld.wolfram.com/PartitionFunctionP.html
Oliver Bel
Regular poster

Post Number: 62
 Posted on Friday, 08 November, 2013 - 09:38 am:

But that recursion refers to the partition function Q, which is only concerned with the number of ways a number can be partitioned into distinct or odd parts, which the question isn't asking about.

I can only imagine I was expected to come up with $p(k) = p(k -1) + p(k - 2)- p(k - 5) - p(k - 7) + p(k - 12) + p(k - 15) - p(k - 22)...$ but I don't understand why it's true and I can't find a proof.
Daniel Fretwell
Veteran poster

Post Number: 2023
 Posted on Friday, 08 November, 2013 - 10:07 am:

Oh sorry, I didn't read the article properly. It is very hard to prove these recursions. I doubt the question is asking you to develop the entire theory behind Euler's pentagonal number theorem by yourself.

I can't find a simple recursion so I can only think that this part of the question is not meant to be easy/solvable either. Where did this question appear?
Oliver Bel
Regular poster

Post Number: 63
 Posted on Friday, 08 November, 2013 - 11:22 am:

It's from 'The Mathematical Olympiad Handbook' by Anthony Gardner.
Daniel Fretwell
Veteran poster

Post Number: 2032
 Posted on Thursday, 14 November, 2013 - 07:57 pm:

Read the paragraph under this problem, it discusses how tough the second problem is compared to the first.