Partial Derangements

Question

There are n people and n houses, such that every person owns exactly one distinct house. Out of these n people, k people are special (k<=n). You have to send every person to exactly one house such that no house has more than one person, and no special person goes to his own house. Let S(n,k) be the number of ways of doing this. Find the value of S(654321,123456). Give your answer mod 1000000007.

Answer 1

As suggested by @BrianM.Scott, I am assuming you are looking for a solution that can be computed using a computer program.

The first thing I would notice is the recurrence relation $$S(n,k)=(n-k) \cdot S(n-1,k-1)+(k-1) \cdot S(n-1,k-2).$$ A naive computation using this relation would take exponential time. But you can reduce it to $O(n^2)$ by working bottom-up: For each $i=1$ to $n-1$, use the values $S(i,0),S(i,1),\dots,S(i,i)$ to calculate $S(i+1,0),S(i+1,1),\dots,S(i+1,i+1)$ (all these $\mod 1000000007$). You don't need to remember all the previous values of $S$, just the ones from the latest loop. In this way you will need $O(n)$ memory instead of $O(n^2)$.

But even the above time complexity is probably not fast enough for your instance. So lets try another approach. For $i\in\{1,2,\dots,k\}$ let $A_i$ be the set of bijections from the set of $n$ people to the set of $n$ houses such that the $i$-th special person goes to his own house. Then

$$S(n,k)=\left|(A_1 \cup A_2 \cup \dots \cup A_k)^C \right| =n!-|A_1 \cup A_2 \cup \dots \cup A_k|.$$

Using the inclusion-exclusion principle you can see that $|A_1 \cup A_2 \cup \dots \cup A_k|$ is equal to

$$\sum_{1\leq i \leq k}|A_i|-\sum_{1\leq i < j \leq k}|A_i \cap A_j|+\dots+(-1)^{k-1} |A_1\cap A_2 \cap \dots \cap A_k|.$$

Note that $|A_{i_1}\cap A_{i_2} \cap \dots \cap A_{i_s}|=(n-s)!$ for $1\leq i_1 < i_2 < \dots < i_s \leq k$. So you have that

$$|A_1 \cup A_2 \cup \dots \cup A_k| = \sum_{i=1}^k(-1)^{i-1}\binom{k}{i} \cdot (n-i)! $$ $$ = \sum_{i=1}^k(-1)^{i-1}\cdot\frac{(n-i)!}{(k-i)!} \cdot \frac{k!}{i!} =\sum_{i=1}^k(-1)^{i-1} \cdot b_i \cdot c_i $$ where $$b_i := \frac{(n-i)!}{(k-i)!} = (n-i)(n-i-1)\dots(k-i+1)$$ and $$c_i := \frac{k!}{i!}=k(k-1)\dots(i+1).$$

You can compute this sum in linear time (e.g. by going downwards from $i=k$ to $i=1$) since for $1\leq i < k$ the following hold:

1. $c_i=c_{i+1}\cdot (i+1)$
2. $b_i=b_{i+1}\cdot (n-i)/(k-i)$
3. $1000000007$ is a prime number. That means that $\mathbb{Z}/1000000007\mathbb{Z}$ is a field, so $(k-i)$ has a modular multiplicative inverse (for small enough $k$) which you can calculate using the extended gcd algorithm, and then use it for (2).