Очікувана мінімальна степінь#11262

Очікувана мінімальна степінь (Розбір)

Вибрати $x$ різних цілих чисел із $n$ можна $C_{n}^{x}$ C_n^x способами.

Розглянемо, скільки існує підмножин із $x$ чисел, мінімальним елементом у яких є число $i$ . Для цього в підмножину обов'язково включається число $i$ , а також обираються ще $x - 1$ x - 1 чисел, кожне з яких строго більше $i$ . Чисел, більших від $i$ , всього $n - i$ n - i, і обрати з них $x - 1$ x - 1 число можна $C_{n - i}^{x - 1}$ C_{n-i}^{x-1} способами.

Зазначимо також, що повинно виконуватися нерівність $i + x - 1 \leq n$ i + x - 1 \le n, оскільки інакше неможливо обрати $x - 1$ x - 1 чисел, більших від $i$ . Звідси слідує обмеження $i \leq n - x + 1$ i \le n - x + 1.

Щоб обчислити очікуване значення величини $2^{S}$ 2^S, необхідно знайти середньозважене значення цієї величини по всіх можливих підмножинах:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}

Якщо $i > n - x + 1$ i > n - x + 1, то кількість відповідних підмножин вважається рівним нулю.

Приклад

У першому тесті можливий єдиний варіант вибору: ${1, 2, 3, 4}$ \{1, 2, 3, 4\}. Мінімальним елементом є число $1$ , тому шукане значення дорівнює $2^{1} = 2$ 2^1 = 2.

У другому тесті існує три рівноймовірних варіанти: ${1, 2}$ , ${1, 3}$ і ${2, 3}$ . Відповідні значення $S$ рівні $1$ , $1$ і $2$ . Тоді середнє значення величини $2^{S}$ 2^S дорівнює

(2^{1} + 2^{1} + 2^{2}) /3 = 8/3 = 2.6666666

(2^1 + 2^1 + 2^2) / 3 = 8 / 3 = 2.6666666

Обчислимо вказану відповідь за формулою:

\frac{\sum _{i = 1}^{n} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}} = \frac{2 ^{1} \cdot C _{2}^{1} + 2 ^{2} \cdot C _{1}^{1}}{C _{3}^{2}} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

\frac{\sum_{i = 1}^n 2^i \cdot C_{n - i}^{x - 1}}{C^x_n} = \frac{2^1 \cdot C_2^1 + 2^2 \cdot C_1^1}{C^2_3} = \frac{2 \cdot 2 + 4 \cdot 1}{3} = \frac{8}{3}

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

Функція Cnk обчислює значення біноміального коефіцієнта $C_{n}^{k}$ C_n^k. Значення біноміальних коефіцієнтів будемо зберігати в осередках масиву $d p$ .

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

C++

Основна частина програми.

scanf("%d %d", &n, &x);
memset(dp, -1, sizeof(dp));

Вичислюємо відповідь: $\frac{\sum _{i = 1}^{n - x + 1} 2 ^{i} \cdot C _{n - i}^{x - 1}}{C _{n}^{x}}$ \frac{\sum_{i = 1}^{n - x + 1} 2^i \cdot C_{n - i}^{x - 1}}{C^x_n}.

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);