問題文

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}}]