| HN Mirror

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:

  3 12 39 84 147 228 327 444 579

And then the consecutive differences are:

  3 12  39  84  147  228  327   444   579
   9  27  45  63   81   99   117   135

You might notice that the second row is a straight-line function. If we take another set of differences...

  3 12  39  84  147  228  327   444   579
   9  27  45  63   81   99   117   135
    18  18  18   18   18   18    18

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":

  n       ... -6 -5 -4 -3 -2 -1 0 1 2  3  4  5  6 ...
  pent(n) ... 57 40 26 15  7  2 0 1 5 12 22 35 51 ...
  -->
  pent(n) sorted: 0 1 2 5 7 12 15 22 26 35 40 51 57 ...

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:

  P(0): 0 = <nothing> --> 1
  P(1): 1 = 1          --> 1
  P(2): 2 = 2, 1+1        --> 2
  P(3): 3 = 3, 2+1, 1+1+1     --> 3
  P(4): 4 = 4, 3+1, 2+2, 2+1+1, 1+1+1+1   --> 5
  P(5): 5 = 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1   --> 7
  P(6): 6 = 6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1,2+2+2,2+2+1+1,2+1+1+1+1,<six 1's> --> 11

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:

  P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + P(n-12) + P(n-15) - ...

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.

[1] "Choose": http://en.wikipedia.org/wiki/Binomial_coefficient