Перечисление набора перестановок на основе условия

Question

Мне удалось решить следующую проблему с помощью std :: next_permutation (c ++) и т. Д., Но сейчас я подумываю об этом в более общем плане и очень хотел бы сформировать выражение, поскольку проблема такого типа кажетсякредитовать себя - хотя мне пока не везет.

Вот вопрос:

Учитывая бегущую гонку с N участниками, какова вероятность того, что именно M участников будутзакончить в положении, которое совпадает с номером на их рубашке.Где M <= N. </p>

Что я сделал до сих пор:

1. Там будет N!способы окончания гонки:

2. Я попытался поиграть с небольшим вариантом задачи, состоящим из 3 или 4 участников, с необходимым количеством людей, удовлетворяющих условию как 2.в обоих случаях для 2 человек, заканчивающих в определенном порядке, вероятность составляет 1/2

Я хотел бы знать, есть ли уже какое-то выражение, которое обрабатывает все случаи?

Какой-то код:

#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;
}

Обновление: Выражение называется частичным расстройством:

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

Примечание 1: Формула верна, если предположить, что полностью упорядоченная перестановка не учитывается.

Примечание 2: Я немного изменил вопрос, чтобы сделать его более понятным, поэтомутакже изменен на код - это должно согласовываться с комментариями, сделанными ShreevatsaR.

Answer 1

Количество перестановок набора с n элементами, содержащими m фиксированных точек, составляет

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

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

Следовательно, вероятность составляет D (n, m) / n !, т.е.

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

Answer 2

Есть два определения, которые необходимо решить в закрытой форме:

1. Количество способов перестановки N людей равно N! (N факториал), или N * N-1 * N-2 * ... * 1. Они называются перестановками .

2. Количество способов выбрать M людей из N называется (N выбирают M), и оно равно N! / (М! (Н-М)!) - это так называемые комбинации . (Если это плохо для вас, выполните поиск в Google по запросу «перестановки и комбинации».)

Я работаю над решением в закрытой форме ...