CODEWITHSUNDEEP
c++mathpermutation
Matthieu N.
Matthieu N.

Reputation:

Enumerating a set of permutations based on a condition

I've been able to solve the following problem using std::next_permutation (c++) etc, but I'm now thinking about it in a more general and would very much like to form an expression as this type of problem seems to lend itself - though I'm not having any luck as of yet.

Here is the question:

Given a running race with N contestants, what is the probability that exactly M contestants will finish in a position that is the same as the number on their shirt. Where M <= N.

What I've done so far:

  1. There will be N! ways the race can end,

  2. I've tried fiddling with a small variant of the problem consisting of either 3 or 4 contestants with the required number of people meeting the condition as being 2. in both cases for 2 people finishing in the particular order the probability is 1/2

I'd like to know if there's already some kind of expression that handles all the cases?

Some code:

#include <cstdio>
#include <algorithm>
#include <vector>

int main(int argc, char* argv[]) {
   if (argc != 3) return 1;

   int n = atoi(argv[1]);
   int m = atoi(argv[2]);

   if (m > n) return 1;

   std::vector<int> lst(n);

   for (int i = 0; i < n; ++i) lst[i] = i;

   unsigned int total = 0;
   unsigned int perm_count = 0;

   do {
      int cnt = 0;
      for (int i = 0; i < n; ++i) if (lst[i] == i) ++cnt;
      if (cnt == m) 
         ++total;
      ++perm_count;
   }
   while (std::next_permutation(lst.begin(),lst.end()));

   printf("Probability of (%d,%d) = %8.7f\n",n,m,(1.0 * total / perm_count));

   return 0;
}

Update: The expression is called a Partial Derangement:

http://mathworld.wolfram.com/PartialDerangement.html

Note1: The formula is correct, if one assumes that the fully ordered permutation does not count.

Note2: I've changed the question slightly to make it more clear, hence also changed to code - this should reconsile with comments made by ShreevatsaR.

Upvotes: 4

Views: 556

Answers (2)

Maxim Razin
Maxim Razin

Reputation: 9466

The number of permutations of a set with n elements containing m fixed points is

D(n,m) = \frac{n!}{m!}\sum_{k=0}^{n-m}\frac{(-1)^k}{k!} http://bit.ly/aaKqUq

(see http://en.wikipedia.org/wiki/Random_permutation_statistics#Number_of_permutations_that_are_derangements)

Therefore, the probability is D(n,m)/n!, i.e.

d(n,m) = \frac{1}{m!}\sum_{k=0}^{n-m}\frac{(-1)^k}{k!} http://bit.ly/aVqSkA

Upvotes: 2

dmazzoni
dmazzoni

Reputation: 13256

There are two definitions you need to solve this in closed form:

  1. The number of ways to permute N people is N! (N factorial), or N * N-1 * N-2 * ... * 1. These are called permutations.

  2. The number of ways to choose M people from N is called (N choose M), and it equals N! / (M! (N-M)!) - these are called combinations. (If this is new to you, do a Google search for "permutations and combinations".)

I'm working on a closed-form solution...

Upvotes: 0

Related Questions