So there are numbers called pentagonal numbers. You may be familiar with the triangular numbers: 0 1 3 6 10 15 ..., with the formula n(n+1)/2, and the square numbers: 0 1 4 9 16 ..., with the formula n^2. In general, the k-gonal numbers begin with "0 1 k", and they are defined by a quadratic formula.
Incidentally, here's a fun little trick. If you have a sequence defined as the values of a polynomial at consecutive integers, then if you take the differences of consecutive terms of the sequence, you'll get a sequence that is the values of a polynomial with degree 1 less. For example, I'll think of a random quadratic. The sequence is:
We end up with a constant function. (And I guess taking differences on a constant function yields another constant.) Then, if we say that the sequence started at index 0 (i.e. f(0) = 3, f(1) = 12, and so on), then I can tell you, by looking at the leftmost elements of each row, that the polynomial was f(n) = 3·(n choose 0) + 9·(n choose 1) + 18·(n choose 2), which comes out to be 9n^2 + 3. [1] That is in fact the polynomial I picked. This method is what Martin Gardner called the "calculus of finite differences"; taking differences is an analogue of taking derivatives, and the result is an analogue of Taylor series.
Anyway, pentagonal numbers are defined like this [this is the only way that makes sense to me, anyway]:
0 1 5 ...
which gives us some differences:
0 1 5 ...
1 4 ...
3 ...
and we know that the bottom is a constant, because it's the second difference on a quadratic:
0 1 5 ...
1 4 ...
3 3 3 3 3 3 3
--> ;now the bottom row is the differences of the row above it
0 1 5 ...
1 4 7 10 13 16 19 22
3 3 3 3 3 3 3
--> ;and *that* is the differences of the top row
0 1 5 12 22 35 51 70 92
1 4 7 10 13 16 19 22
3 3 3 3 3 3 3
Incidentally, this is the method of calculating values of polynomials that Charles Babbage's Difference Engine was designed to do. It's nice and easy. Anyway, back to theory about pentagonal numbers. Using the pseudo-Taylor series method, we can read off "0·(n choose 0) + 1·(n choose 1) + 3·(n choose 2)" as our formula, which comes out to n(3n-1)/2. By the way, we can also plug negative numbers into this formula (or, equivalently, we could take the differences backward), which yields what are called the "generalized pentagonal numbers":
Now, we define P(n) to be the number of partitions of n, i.e. the number of distinct unordered ways to express n as the sum of positive integers. The first several terms look like this:
You could compute several more by hand. Then the recursive formula I originally described might occur to you, and you could make a computer calculate it, perhaps up into the thousands. Now, what if I told you this:
where that sequence "1 2 5 7 12 15" is the "generalized pentagonal numbers" I described above? How the hell are pentagonal numbers connected with partitions? That's what I mean by ridiculous. ... The Wikipedia article in the sister comment describes a proof of the connection. I still find it counterintuitive.
Thanks for the in-depth answer. This actually reminds me of Chebyshev polynomials, which I was obsessed with in a very simple way last spring. But I'm not advanced enough in maths to draw any concrete connection.
