11262. Ожидаемая минимальная степень

Даны два положительных целых числа n и x.

Требуется выбрать x различных целых чисел от 1 до n включительно. Выбор осуществляется равновероятно, то есть каждое из возможных x-элементных подмножеств множества {1, 2, …, n} выбирается с одинаковой вероятностью.

Пусть S – наименьшее число среди выбранных x чисел. Найдите математическое ожидание величины 2^S. Иными словами, необходимо определить среднее значение 2 в степени S, где усреднение производится по всем возможным выборам x различных чисел.

Вход. Два натуральных числа n (1 ≤ n ≤ 50) и x (1 ≤ x ≤ n).

Выход. Выведите математическое ожидание величины 2^S, округлённое до 4 знаков после десятичной точки.

Пример входа 1	Пример выхода 1
4 4	2.000000
Пример входа 2	Пример выхода 2
3 2	2.666667

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Выбрать x различных целых чисел из n можно способами.

Рассмотрим, сколько существует подмножеств из x чисел, минимальным элементом в которых является число i. Для этого в подмножество обязательно включается число i, а также выбираются ещё x – 1 чисел, каждое из которых строго больше i. Чисел, больших i, всего n – i, и выбрать из них x – 1 число можно способами.

Отметим также, что должно выполняться неравенство i + x – 1 ≤ n, поскольку иначе невозможно выбрать x – 1 чисел, больших i. Отсюда следует ограничение i ≤ n – x + 1.

Чтобы вычислить ожидаемое значение величины 2^S, необходимо найти средневзвешенное значение этой величины по всем возможным подмножествам:

=

Если i > n – x + 1, то количество соответствующих подмножеств считается равным нулю.

Пример

В первом тесте возможен единственный вариант выбора: {1, 2, 3, 4}. Минимальным элементом является число 1, поэтому искомое значение равно 2¹ = 2.

Во втором тесте существует три равновероятных варианта: {1, 2}, {1, 3} и {2, 3}. Соответствующие значения S равны 1, 1 и 2.  Тогда среднее значение величины 2^S равно

(2¹ + 2¹ + 2²) / 3 = 8 / 3 = 2.6666666

Вычислим указанный ответ по формуле:

= = =

Реализация алгоритма

Функция Cnk вычисляет значение биномиального коэффициента . Значения биномиальных коэффициентов будем сохранять в ячейках массива dp.

long long dp[51][51];

long long Cnk(int n, int k)

{

if (n == k) return 1;

if (k == 0) return 1;

if (dp[n][k] != -1) return dp[n][k];

return dp[n][k] = Cnk(n - 1, k - 1) + Cnk(n - 1, k);

}

Основная часть программы.

scanf("%d %d", &n, &x);

memset(dp, -1, sizeof(dp));

Вычисляем ответ: a = .

a = 0;

for (i = 1; i <= n - x + 1; i++)

a = a + Cnk(n - i, x - 1) * (1LL << i);

res = 1.0 * a / Cnk(n, x);

Выводим ответ.

printf("%lf\n", res);