問題文
Problem Statement
You are given two positive s: 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 and return 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.
日本語訳
あなたは2つの正の引数n,xが与えられる.
あなたは1からnの自然数から異なるx個の数を選ぶ.1からnの選ぶ確率は一様にランダムである.
ここで,選んだx個の中で最小のものをsとするとき,2のs乗の期待値を求めよ.つまり,考えられるすべての組み合わせから2のs乗の平均を求めよ.
解法
まず,n個の数からx個選んだときの最小値がsである確率を求める.ここで,1<=s<=nである.分母にはn個の数からx個選んだときの組み合わせの数nCxをおく.分子には最小値sを選び,残りのx-1個をsより大きい数であるn-s個の中から選ぶ組み合わせの数n-sCx-1をおく.
e^{i\pi} = -1
[tex:{\frac{1}{2}}]