k^n fails because:
Take 3 shelves and 4 books
1. take the first book, you have 3 options.
2. For the second book, you don't have just 3 options. You have 3 ways to put it as the first book in any of the shelves OR to the right of the first book. 4 ways.
So for every book options varies like k, k+1, k+2 and so on.