Enumerate a set of permutations based on a condition

Question

I was able to solve the following problem using std :: next_permutation (C ++) etc. but now I think about it more generally and would really like to create how this type of problem seems to be lent, although so far I have no luck.

Here is the question:

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

What i have done so far:

• Will be N! the ways in which the race may end

• I tried to play with a small version of the problem, consisting of 3 or 4 participants with the required number of people satisfying the condition, equal to 2. In both cases, for two people ending in a certain order, the probability is 1/2

I would like to know if there is some kind of expression that handles all cases?

Some codes:

#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 partial binding:

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

Note1: The formula is correct assuming that a fully ordered permutation is not taken into account.

Note2: I slightly modified the question to make it more clear, therefore, also changed to code - this should revise the comments made by ShreevatsaR.

Answer 1

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

D (n, m) = \ frac {n!} {M!} \ Sum_ {k = 0} ^ {nm} \ 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} ^ {nm} \ frac {(-1) ^ k} {k!} http://bit.ly/aVqSkA

Answer 2

There are two definitions that need to be addressed in closed form:

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

• The number of ways to select M people from N is called (N chooses M), and it is N! / (M! (NM)!) - they are called combinations. (If this is new to you, do a Google search for “permutations and combinations.”)

I am working on a closed form solution ...