Count permutations where some items should be deranged while rest can be placed anywhere (rank derangements)

Question

As the title says, I am looking for a way to count permutations of $n$ (permutations of the set $(0, 1,\dots, n-1)$) where $k, 0 \le k \le n$ items should not stay in same place (be deranged), while rest $n-k$ items may be placed anywhere (even stay in same place).

This is needed in an algorithm of mine to rank derangements in lexicographic order.

Initially I thought that $\text{count} = (n-k)! \cdot !k$, that is number of derangements of $k$ items multiplied by any permutation of the rest, but I am not so sure.

NOTE $k$ is known and fixed beforehand, we do not choose which $k$ out of $n$ should be deranged, but may not necessarily be the first $k$ items, may be any $k$ items out of $n$, but fixed.

Alternatively if an algorithm is known to rank derangements in lexicographic order (not in cycle notation), I am happy.

Answer 1

Organizing from comments:

We can approach the same way that we did when deriving a formula for derangements in the first place via inclusion-exclusion.

We start with $n!$ permutations. We remove those permutations which were "bad" where one specific element of our k was a fixed point. Choose which it was, it mapped to itself. For the remaining $n−1$ elements, pick where they map. We removed too much, namely those where two elements from our $k$ were fixed points... do the same for them, and then for three and so on...

This gives:

$$\sum\limits_{i=0}^k\binom{k}{i}(-1)^i(n-i)!$$

In the event that $k=n$, this is precisely the formula for derangements in wikipedia (where I prefer to organize the leading term of $n!$ as the initial term in the sum where $i=0$ rather than outside of the summation).

Similarly, when $k=0$, only the first term in the sum survives and it gives $n!$. Other edge cases and sanity checks can be performed and it will give the expected results.

Answer 2

There are $n$ items. We need to find all arrangements where $k$ or more items are deranged and $k$ of those deranged items are fixed.

We know $k$ items that are deranged in every arrangement. So we now choose $i$ items out of remaining $(n-k)$ items that are additionally deranged. Rest of $(n-k-i)$ items remain in their place. $i$ can be any number from $0$ to $(n-k)$. In other words we can choose any number of items from the remaining $(n-k)$ items to be deranged.

So we can write the total number of arrangements as,

$ \displaystyle \sum\limits_{i=0}^{n-k} {n-k \choose i} \ !(k+i)$

A few boundary conditions -

• when $k = 0$, this returns $n!$ as expected
• when $k = 1$, as you cannot have just one item deranged out of $n$, it will return all arrangements where $2$ or more items are deranged and that one particular item is in it.
• When $k = n$, this becomes $ \displaystyle \sum\limits_{i=0}^{0} {0 \choose i} !n$ and WolframAlpha does return $!n$ for it.