Permutations of the Fifteen Puzzle The Challenge
Consider the following diagram of the Fifteen Puzzle in its solved state:
_____________________
|    |    |    |    |
| 1  | 2  | 3  | 4  |
|____|____|____|____|
|    |    |    |    |
| 5  | 6  | 7  | 8  |
|____|____|____|____|
|    |    |    |    |
| 9  | 10 | 11 | 12 |
|____|____|____|____|
|    |    |    |    |
| 13 | 14 | 15 |    |
|____|____|____|____|

At every move, an excited puzzler has the opportunity to move one piece adjacent to the blank space into the blank space. For example, after 1 move, we have 2 possible scenarios (let 0 be a blank space):
1   2   3   4          1   2   3   4
5   6   7   8          5   6   7   8
9   10  11  12   and   9   10  11  0
13  14  0   15         13  14  15  12

After 2 moves, the puzzle has 5 different outcomes (Note that the two cases above are excluded, since they cannot be reached in 2 moves). One of these situations is the original solved state, and can be reached in two different ways.
Your task in this challenge is to produce the number of different outcomes that a certain number of moves can lead to. As input, take a number N &gt;= 0, and output the number of unique situations that may appear after N moves.
Rules

This is code-golf. Shortest code wins!
Standard loopholes are disallowed.
Your code should be able to compute the case for N = 10 within a few minutes. I will likely not test this rule unless an obvious abuse of time exists in an answer.

Test Cases
(Results generated from summations of OEIS A089484 (As Geobits described in chat), automated by Martin Büttner's script. Thanks for all the help!)
0 moves: 1
1 moves: 2
2 moves: 5
3 moves: 12
4 moves: 29
5 moves: 66
6 moves: 136
7 moves: 278
8 moves: 582
9 moves: 1224
10 moves: 2530
11 moves: 5162
12 moves: 10338
13 moves: 20706
14 moves: 41159
15 moves: 81548
16 moves: 160159
17 moves: 313392
18 moves: 607501
19 moves: 1173136
20 moves: 2244884
21 moves: 4271406
22 moves: 8047295
23 moves: 15055186
24 moves: 27873613
25 moves: 51197332
26 moves: 93009236
27 moves: 167435388
28 moves: 297909255
29 moves: 524507316
30 moves: 911835416
31 moves: 1566529356
Pyth, 36 bytes

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16


Demonstration. Test harness.

lu{smmXd,0@dk)fq1.a.DR4,Txd0UdGQ]U16

                 .a.DR4,Txd0            Find the Euclidean distance between the
                                        present location of 0 and a given location.
              fq1           Ud          Filter over all locations on that distance
                                        equaling 1.
     mXd,0@dk)                          Map each such location to the grid with 0
                                        and the value at that location swapped.
  {sm                         G         Map all unique grids possible after n-1
                                        steps to all unique grids after n steps.
 u                             Q]U16    Repeat &lt;input&gt; times, starting with the
                                        initial grid.
l                                       Print the length of the resulting set.