11262. Expected minimum power

 

You are given two positive integers n and x.

You are required to choose  distinct integers from 1 to n inclusive. The selection is made uniformly at random; that is, each possible x-element subset of the set {1, 2, …, n} is chosen with equal probability.

Let S be the smallest integer among the selected  numbers. Find the expected value of 2S. In other words, determine the average value of 2 raised to the power S, where the average is taken over all possible selections of x distinct integers.

 

Input. Two positive integers n (1 ≤ n ≤ 50) and x (1 ≤ x ≤ n).

 

Output. Print the expected value of  2S, rounded to 4 digits after the decimal point.

 

Sample input 1

Sample output 1

4 4

2.000000

 

 

Sample input 2

Sample output 2

3 2

2.666667

 

 

SOLUTION

combinatorics

 

Algorithm analysis

There are  ways to choose x distinct integers from n.

Let us consider how many subsets of x numbers have the minimum element equal to i. For this, the subset must include the number i, and additionally choose x – 1 numbers, each of which is strictly greater than i. There are n – i numbers greater than i, and the number of ways to choose x – 1 numbers from them is .

Note that the inequality i + x – 1 ≤ n must hold; otherwise, it is impossible to choose x – 1 numbers greater than i. This leads to the constraint i ≤ n – x + 1.

To compute the expected value of the 2S, we need to find the weighted average of this value over all possible subsets:

 =

If i > n – x + 1, then the number of corresponding subsets is considered to be zero.

 

Example

In the first test case, there is only one possible selection: {1, 2, 3, 4}. The minimum element is 1, so the required value is 21 = 2.

In the second test case, there are three equally likely selections:{1, 2}, {1, 3} and {2, 3}. The corresponding values of S are 1, 1 and 2.  Therefore, the average value of the 2S is

(21 + 21 + 22) / 3 = 8 / 3 = 2.6666666

Now compute the required answer using the formula:

 =  =  =

 

Algorithm implementation

The function Cnk computes the value of the binomial coefficient . The values of the binomial coefficients will be stored in the cells of the array 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);

}

 

The main part of the program.

 

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

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

 

Compute the answer: 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);

 

Print the answer.

 

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