March 28 ADA University Students + Schoolchildren
Expected Minimum Power
You are given two positive integers n and x.
You are going to choose x distinct integers, each between 1 and n, inclusive. The choice will be made uniformly at random. That is, each of the possible x-element subsets of the integers 1 to n is equally likely to be chosen.
Let S be the smallest integer among the x chosen ones. Compute the expected value of 2^S. In other words, determine the average value of 2 to the power of S, where the average is taken over all possible choices of the x distinct integers.
Input data
Two positive integers: n (1 ≤ n ≤ 50) and x (1 ≤ x ≤ n).
Output data
Print the average value of 2 to the power of S with 4 decimal digits.
Examples
4 4
2.000000
3 2
2.666667
Note
In the first test case the only possible situation is that you will choose (1, 2, 3, 4). In this case, the minimum is 1, and the expected value is 2^1 = 2.
In the second test case there are three equally likely scenarios: you will select either {1, 2} or {1, 3} or {2, 3}. The corresponding values of S are 1, 1 and 2 respectively. Thus, the average value of 2^S is (2^1 + 2^1 + 2^2) / 3 = 8 / 3 = 2.6666666.