|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 23 Sep 2002 21:07:28
To : Sergey Rezvanov
Subject : среднее значение средней длины циклов в перестановках длины n
--------------------------------------------------------------------------------
Replying to a message of Sergey Rezvanov to All:
SR> Дана задача. Hаписать программу для подсчёта среднего по всем
SR> перестановкам из n элементов значения средней длины циклов в каждой
SR> перестановке. Hужна эффективная работа при n <= 50. Хорошо бы её
SR> решить.
Средняя длина циклов в перестановке равна n/k, где k - число циклов в этой
перестановке.
Число перестановок, имеющих ровно k циклов, равно числу Стирлинга первого рода
без знака c(n,k).
Соответственно, решением задачи будет
n * \sum_{k=1}^n c(n,k)/k
Для вычисления чисел Стирлинга c(n,k) можно использовать рекуррентную формулу:
c(n,k) = (n-1)c(n-1,k) + c(n-1,k-1)
c(n,k) = 0 при n<=0 или k<=0, за исключением c(0,0)=1.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
среднее значение средней длины циклов в перестановках длины n