I should have been a bit more careful I suppose, but in practice you can't increase k indefinitely without also increasing n anyway. In particular n >= k, so at worst it would be something like k^k / k!.

Really not sure why the state space would only grow as n^k / k!. As well as what n and k are in this case. Adding more tiles or more actors would both dramatically increase the size of the state space for that input.