# What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?

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?

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$$.)