Is this textbook's combinatorial reasoning for $n \times n! / (b!(n - b)!)$ incorrect?

Question

I recently asked this question on cs.stackexchange.

---

I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following:

Another type of grid world is the sokoban puzzle, in which the agent's goal is to push a number of boxes, scattered about the grid, to designated storage locations. There can be at most one box per cell. When an agent moves forward into a cell containing a box and there is an empty cell on the other side of the box, then both the box and the agent move forward. The agent can't push a box into another box or a wall. For a world with $n$ non-obstacle cells and $b$ boxes, there are $n \times n! / (b!(n - b)!)$ states; for example on an $8 \times 8$ grid with a dozen boxes, there are over 200 trillion states.

I understand the combinatorial reasoning for why we get $n! / (b!(n - b)!)$ (the binomial coefficient), since we are looking for the number of ways we can choose (with replacement) $b$ boxes from a world with $n$ non-obstacle cells. But I don't understand where the $n$ factor in $n \times n! / (b!(n - b)!)$ comes from. What is the combinatorial reasoning for this $n$ factor?

---

Tanner Swett gave the following answer:

Part of the state of the world is the location of the agent. Since there are $n$ cells, this variable has $n$ possible values, producing the factor of $n$.

Actually, there may be a mistake in Russell and Norvig's formula. After we have chosen the location of the agent, there are only $n - 1$ possible locations for the $b$ boxes, giving us $(n - 1)! / (b! (n - b - 1)!)$ choices for where to put all of the boxes. So, the number of states is $n \times (n - 1)!/(b!(n - b - 1)!)$, which simplifies to $n! / (b! (n - b - 1)!)$. (This is the trinomial coefficient $n \choose 1, b$.)

I wanted to ask here, since the users of this website are more mathematically-focused: Is Tanner Swett's analysis of this correct? Is this an error in the textbook?

Answer 1

I agree with Tanner that the factor of $n$ is intended to be for the location of the agent and that the stated formula is not quite correct, assuming that the agent can't occupy the same cell as a box which seems like a reasonable assumption to me. An equivalent way to count it is to place the boxes first (which can be done in ${n \choose b}$ ways) and then notice that this leaves $n-b$ unoccupied cells to place the agent. So the true count is

$$(n-b) {n \choose b}$$

which is equivalent to Tanner's count; this actually gives a bijective proof that $(n-b) {n \choose b} = n {n-1 \choose b}$. But this doesn't make a big difference as far as the order-of-magnitude of the number of possible states goes.