So, I woke up at 6:00 this morning and, as one does, I ended up passing the time by thinking about how many possible crafting recipes one could make using any number of an item in the standard Minecraft 3×3 crafting grid… I know, right. Don’t worry, it gets better.
I thought, OK, 9 ways to put 1 item in, 1 way to put 9 in… I got up to “36 ways to put 2 in” before I decided it was probably going to be a lot of work counting all the possible combinations in a 9 cell grid, so I thought, why not come up with a formula for it to save myself some trouble?
I started out with a 1 cell grid; easy. There was only 1 possible combination, of course. Then I moved up to 2 cells: 3 combinations. 3 cells: 7 combinations. 4 cells: 15 combinations.
By this point I decided that lying in bed, doing it all in my head, I could only get so far; so I got up and started writing it down. Still waking up, I hadn’t noticed the fairly obvious pattern yet, but some latent high-school maths came back to me and I realised that I was just calculating the sum of C(n,k) for k≥1 (the upper bound is effectively n, since any k>n will yield 0), which quickly gave me my result for n=5: 31.
Having written these sums down for n=1 to n=5 (and having some fun with triangular, tetrahedral and “pentatope” numbers along the way), the pattern was very obvious. But I still made sure to calculate the results for n=6 up to n=9, just to be sure.
And, as expected, n=6 gave 63; n=7: 127; n=8: 255; and n=9: 511.
So I had my answer: in a 3×3 crafting grid, there are 511 possible recipes using any number of an item. But my interest was piqued now and there was no way I could leave it at that.
I had my formula: for an n-cell crafting grid, there are 2^n – 1 recipes, but I didn’t at all like that “- 1″ bit. How could I get rid of it?
Well, trivially, there was going to be one way to arrange zero of an item in a grid of any size, so I could add a k=0 row with the value of 1 for every n. It was moving away from the original idea, since crafting something from nothing doesn’t really make sense (unlike floating trees and carrying hundreds of cubic metres of rock), but not only did it get rid of the minus one, leaving me with my much-coveted powers of two, it also gave my table a beautiful symmetry.
I wrote “cool!” on my page next to that. I didn’t just say “cool!”, I wrote it down. That’s how cool I thought it was.
And that’s where I ended it, with one big question: why is the nth power of two equal to the sum of C(n,k) for 0≤k≤∞? I don’t know the answer. Maybe no-one knows. More likely, I’m just missing something very obvious to the more mathematically minded.
Whatever the case, I hope you’ve enjoyed reading this post, and if you know the reason for my “cool!” result, please let me know in the comments section.
- Ben xoxo