# Find the remainder

537 views
0

A soccer team has $22$ available players. A fixed set of $11$ players starts the game, while the other $11$ are available as substitutes. During the game, the coach may make as many as $3$ substitutions, where any one of the $11$ 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 $n$ be the number of ways the coach can make substitutions during the game ,including the possibility of making no substitutions. Find the remainder when $n$ is divided by $1000$

There are substitutions. The number of ways to sub any number of times must be multiplied by the previous number. This is defined recursively. The case for subs is , and the ways to reorganize after subs is the product of the number of new subs ( ) and the players that can be ejected ( ). The formula for subs is then with .
Summing from to gives . Notice that . Then, rearrange it into . When taking modulo , the last term goes away. What is left is 