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".

SayMmen andWwomen 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 ofNitems, out of which particularKpredefined objects cannot be in their correct place. Note that there are specificKobjects, 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*can either***ball i***Be put in any*

__A :__*bin, which is numbered*

**unrestricted****(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

*Be put in a*

__B :__*bin from*

**restricted****(1..K)**There are

**K-1**choices here, as

*cannot be put in*

**ball i***.*

**bin i**Let's examine each case in more detail now.

*When the*

__A :__*is put in an*

**ball i***bin, we lose one*

**unrestricted***bin, of course. But now the corresponding*

**unrestricted***for this ball becomes*

**bin i***, as any ball can be put there without violating the rule. Meaning the number of*

**unrestricted***bins remains same, and the number of*

**unrestricted***bins is now one less. So after this placement, we have*

**restricted****N-1**balls, with

**K-1**

*bins. This is same as*

**restricted****PD(N-1, K-1)**. And since there are

**N-K**choices for choosing an

*bin, the sub-total of these arrangements is*

**unrestricted****(N-K) * PD(N-1, K-1)**.

*This is where I am copying the logic used in finding derangement. Here ball i was placed in a*

__B :__*bin, from*

**restricted****(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

*. Now let's decide a place for the*

**bin j***corresponding to that bin. There are 2 choices - it is either placed in*

**ball j***or it isn't.*

**bin i***It is placed in*

__B1 :__**. This effectively removes the pair**

*bin i**and*

**i***from the set. We are left with*

**j****N-2**balls, to be placed in

**N-2**bins, out of which

**K-2**are

*bins. This is same as*

**restricted****PD(N-2, K-2)**.

*If*

__B2 :__*is not be placed in*

**ball j***, let's represent that restriction by simply renaming*

**bin i***to*

**bin i***. This leaves us with exactly the same problem, with one less ball. That is, we have*

**bin j****N-1**balls, with

**K-1**

*bins. This is nothing but*

**restricted****PD(N-1, K-1)**.

Since

*and*__B1__*are mutually exclusive, for every choice of bin for*__B2__*we have***ball i****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,

*and*__A__*are mutually exclusive, let's add them to get the final answer.*__B__PD(N, K)

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

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

Note the termPD(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!(Nobins, so all arrangements are valid)restricted

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 havePD(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)(using induction)

= (N-1) * ( PD(N-1, N-1) + PD(N-2, N-2) )

= (N-1) * ( D(N-1) + D(N-2) )

= D(N)

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

## No comments:

## Post a Comment