среднее значение средней длины циклов в перестановках длины n

From

Max Alekseyev (2:5015/60)

To

Sergey Rezvanov

Date

2002-09-23T21:07:28Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Sergey !

Replying to a message of Sergey Rezvanov to All:

 SR> Дана задача. Написать программу для подсчёта среднего по всем
 SR> перестановкам из n элементов значения средней длины циклов в каждой
 SR> перестановке. Нужна эффективная работа при 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)