Permutations of the Fifteen Puzzle
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.