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

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?

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.