Énumération d'un ensemble de permutations basées sur une condition

Question

J'ai été capable de résoudre le problème suivant en utilisant std :: next_permutation (C++) etc, mais je suis maintenant en train d'y penser de façon plus générale et j'aimerais beaucoup pour former une expression comme ce type de problème semble se prêter - même si je n'ai pas de chance pour le moment.

Voici la question:

Étant donné une course à pied avec les participants N, quelle est la probabilité que les candidats exactement M se terminera dans une position qui est le même que le numéro sur leur chemise. Où M < = N.

Ce que je l'ai fait jusqu'à présent:

1. Il y aura N! J'ai essayé de jouer avec une petite variante du problème consistant en 3 ou 4 participants avec le nombre requis de personnes remplissant la condition comme étant 2. dans les deux cas pour 2 personnes finissant dans l'ordre particulier la probabilité est de 1/2

Je voudrais savoir s'il existe déjà une sorte d'expression qui gère tous les cas?

Certains 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: L'expression est appelé Derangement partielle:

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

Note 1: La formule est correcte, si l'on suppose que le pleinement La permutation ordonnée ne compte pas.

Note2: J'ai légèrement changé la question pour la rendre plus claire, donc aussi changé en code - cela devrait être reconsidéré avec les commentaires faits par ShreevatsaR.

Answer 1

Il y a deux définitions que vous devez résoudre ce sous forme fermée:

1. Le nombre de façons de permute personnes N est N! (N factoriel), ou N * N-1 * N-2 * ... * 1. Ceux-ci sont appelés permutations.

2. Le nombre de façons de choisir M personnes de N est appelé (N choisir M), et il est égal à N!/(M! (N-M)!) - ceux-ci sont appelés combinaisons. (Si cela est nouveau pour vous, faire une recherche Google pour « permutations et combinaisons ».)

Je travaille sur une solution sous forme fermée ...

Answer 2

Le nombre de permutations d'un ensemble de n éléments contenant m points fixes est

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

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

Par conséquent, la probabilité est D (n, m)/n !, c'est-à-dire

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