Problem:
A soccer team has available players. A fixed set of players starts the game, while the other are available as substitutes. During the game, the coach may make as many as substitutions, where any one of the players in the game is replaced by one of the substitutes. No player removed from the game may reenter the game, although a substitute entering the game may be replaced later. No two substitutions can happen at the same time. The players involved and the order of the substitutions matter. Let be the number of ways the coach can make substitutions during the game (including the possibility of making no substitutions). Find the remainder when is divided by .
Solution:
There is 1 way of making no substitutions to the starting lineup. If the coach makes exactly 1 substitution, this can be done in ways. Two substitutions can happen in ways. Similarly, three substitutions can happen in ways. The total number of possibilities is . .
The problems on this page are the property of the MAA's American Mathematics Competitions