Partial Derangement

As part of a bigger problem, I wanted to solve what I decided to call "Partial Derangement". This may be part of standard course material on Combinatorics, but I couldn't quickly find anything similar. So I gave it a try on my own. I may be reinventing a wheel here, but it was a fun challenge.

The problem is similar in nature to "derangement". In the derangement problem, we want to find out all such arrangements, which do not have any object in its correct place. Here the restriction is placed on only a few items. Say you want to find out arrangements of letters [A B X Y] such that A cannot be in first place, and B cannot be in second place. There is no restriction on X and Y .

For example, [B X Y A] is a valid arrangement. But [X B A Y] is not. Because here B is in its natural second place.

Let's modify the problem we looked at, while discussing "derangement".

Say M men and W women went to a party. Each was given a name tag. Assume they all had different names. To play a fun guessing game, all the men deliberately put on a wrong name tag on their shirts. No man had the right name tag. The women, on the other hand can put the right name tag if they want. In how many ways can they do it ?

Note how this is quite different from simple derangement discussed before. Here a man can put a woman's name tag to satisfy the requirement of the game. For every man, there are (M-1) * W valid choices. Whereas in a simple derangement, every man would have had only M-1 choices. In other words, this is NOT a derangement only within a subset. Hence the answer cannot be D(M) * W! where D(M) is number of derangements of a set of M objects.

This problem is a bit harder than derangement. But very similar logic can be applied to solve it. First, let's define what we want to solve for.

Let's define, PD (N, K) as the number of arrangements of N items, out of which particular K predefined objects cannot be in their correct place. Note that there are specific K objects, already identified to be deranged.

Think of N numbered balls (from 1..K..N) to be put in N numbered bins (from 1..K..N) . The task is to arrange N balls so that no ball numbered (1..K) is in the bin with the same number.

We will solve it using the similar reasoning style for derangement.

Pick a ball, numbered between (1..K) This ball i can either

A : Be put in any unrestricted bin, which is numbered (K+1..N) In this case, any bin can be used, there is no restriction. There are N-K choices for such a bin.

OR

B : Be put in a restricted bin from (1..K) There are K-1 choices here, as ball i cannot be put in bin i .

Let's examine each case in more detail now.

A : When the ball i is put in an unrestricted bin, we lose one unrestricted bin, of course. But now the corresponding bin i for this ball becomes unrestricted, as any ball can be put there without violating the rule. Meaning the number of unrestricted bins remains same, and the number of restricted bins is now one less. So after this placement, we have N-1 balls, with K-1 restricted bins. This is same as PD(N-1, K-1) . And since there are N-K choices for choosing an unrestricted bin, the sub-total of these arrangements is (N-K) * PD(N-1, K-1) .

B : This is where I am copying the logic used in finding derangement. Here ball i was placed in a restricted bin, from (1..K) . Since it cannot be placed in its own bin, there are K-1 choices for this. Let's say it was placed in bin j . Now let's decide a place for the ball j corresponding to that bin. There are 2 choices - it is either placed in bin i or it isn't.

B1 : It is placed in bin i . This effectively removes the pair i and j from the set. We are left with N-2 balls, to be placed in N-2 bins, out of which K-2 are restricted bins. This is same as PD(N-2, K-2) .

B2 : If ball j is not be placed in bin i, let's represent that restriction by simply renaming bin i to bin j. This leaves us with exactly the same problem, with one less ball. That is, we have N-1 balls, with K-1 restricted bins. This is nothing but PD(N-1, K-1) .

Since B1 and B2 are mutually exclusive, for every choice of bin for ball i we have 

PD(N-2, K-2) + PD(N-1, K-1) 

arrangements. Since there are K-1 choices for bins, the subtotal here is 

(K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) ) .

Since, A and B are mutually exclusive, let's add them to get the final answer.

PD(N, K)
= (N-K) * PD(N-1, K-1)
+ (K-1) * ( PD(N-2, K-2) + PD(N-1, K-1) )
Note the term PD(N-1, K-1)is common in both. So after simplifying, we get a nice elegant formula
PD(N, K) = (N-1) * PD(N-1, K-1) + (K-1) * PD(N-2, K-2)

To use this formula, we have to have certain definitions, to avoid negative values. This is similar to saying 0! = 1 by definition, to terminate the recursion of formula  N! = N * (N-1)!

PD(0, 0) = 1 (by definition)
PD(N, 0) = N! (No restricted bins, so all arrangements are valid)

We require one last definition, and it needs some explanation.

PD(N, 1) = (N-1) * (N-1)!

Here we want to know how many arrangements are there, in which one specific ball is not in its corresponding bin. The total arrangements are of course N!. How many invalid arrangements are there ? To find out put the ball in its corresponding bin and arrange the rest of the N-1 balls. This is nothing but (N-1)!. So we have

PD(N, 1)
= N! - (N-1)!
= N*(N-1)! - (N-1)!
= (N-1) * (N-1)!

Let's do a couple of quick checks.

PD(1, 1) = (1-1) * 0! = 0
Obviously, there is no way to arrange just 1 ball with our restriction.
And
PD(2, 1) = (2-1) * 1! = 1
Correct, as there is only 1 way to arrange 2 balls with out restriction.

Let's also check if we are in agreement with full derangement.

PD(N, N) is full derangement - no ball in its corresponding bin, so this should be equal to D(N) .

Let's see. Using our formula,

PD(N, N) = (N-1) * PD(N-1, N-1) + (N-1) * PD(N-2, N-2)
= (N-1) * ( PD(N-1, N-1) + PD(N-2, N-2) )
= (N-1) * ( D(N-1) + D(N-2) ) (using induction)
= D(N)

This was definitely harder than derangement, but it was also much more fun to prove a more general result.