Среднее значение минимума всех возможных подмножеств размера K из первых N натуральных чисел

Даны два натуральных числа N и K , задача состоит в том, чтобы найти среднее значение минимума всех возможных подмножеств размера K из первых N натуральных чисел.

Примеры:

Input: N = 3, K = 2
Output: 1.33333
Explanation:
All possible subsets of size K are {1, 2}, {1, 3}, {2, 3}. The minimum values in all the subsets are 1, 1, and 2 respectively. The mean of all the minimum values is (1 + 1 + 2)/3 = 1.3333.

Input: N = 3, K = 1
Output: 2.00000

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы найти все подмножества, образованные из элементов [1, N], и найти среднее значение всех минимальных элементов подмножеств размера K.

Временная сложность: O(N* ^2N )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, если учесть тот факт, что общее количество подмножеств, сформированных размером K , равно ^N C _K , и каждый элемент, скажем, i встречается ^{(N – i)} C _{(K – 1)} раз как минимальный элемент.

Поэтому идея состоит в том, чтобы найти сумму ( ^{N – i} C _{K – 1)} )*i по всем возможным значениям i и разделить ее на общее количество сформированных подмножеств, т. е. ^N C _K .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)