Combination:コンビって略したくなるよね

…ということで、どうも、Weskdohnです。最近暑いですね。
さて本日は、競技数学がいい感じに煮詰まってきた(?)ので、
数学について少し話そうかなと思います。
僕自身、OMC(online math contest)というのをやっているのですが、
最高位が39位(それも非正規コン)なので、まさしく才能のない競技数学erな訳です。(そもそも三角関数すらまともに使えません。中3なのに……)
それはさておき、今日は何を話そうかと悩んだんですが、場合の数の初歩的なテクニックについてお話しようと思います。

Combinationについての初歩的テクニック

まずは、こちらの式から。
$${{}_n\mathrm{C}_k={}_{n-1}\mathrm{C}_{k-1}+{}_{n-1}\mathrm{C}_k}$$
組合せ論における基礎的問題ですね。
証明:
まずは、感覚的なところで考えてみましょう。
n個のボールについて、k個取り出す場合の数を考えます。
この時、ある特定のボール(仮にAとします)について、k個のうちに含まれているかどうかで場合分けします。
i:Aがk個に含まれている場合の数は、A以外のk-1個をn-1個から選ぶことを考えればよいので、$${{}_{n-1}\mathrm{C}_{k-1}}$$通りです。
ii:Aがk個に含まれていない場合の数は、k個をn-1個から選ぶことを考えればよいので、$${{}_{n-1}\mathrm{C}_{k}}$$通りです。
n個からk個選ぶ場合の数は$${{}_n\mathrm{C}_k}$$通りですから、上の式が示されました❚
さて、これを使うと、かなり便利な結果を得ることが出来ます。
性質:$${{}_{n}\mathrm{C}_{n}+{}_{n+1}\mathrm{C}_{n}+…+{}_{n+k}\mathrm{C}_{n}={}_{n+k+1}\mathrm{C}_{n+1}}$$
証明概要(詳しい所は省略):
最初のcombination式について、$${{}_{n}\mathrm{C}_{n}={}_{n+1}\mathrm{C}_{n+1}}$$と変形できるので、後は先ほど紹介した式を繰り返し用いることで、結果を得ることが出来ます。
ほぇー……

『こちらの式、いつ使うんじゃい』って思う人、いると思います。少なくとも僕は、この知識を三年(！)もの間スルーしてきました。しかし、この式を用いる問題が、少なからず存在するんです。
例えば、次のような問題。
問題:X(0<x<2025)個の相異なるボールから、Y(0<y<2025)個を選び出すことを考えます。すべてのX,Yについて、これを計算した総和を求めなさい。
(但し、選び出せないX,Yの組み合わせはスルーすることにします。)(目標:5分)解答は下にあります↓

解答:
上の性質を利用すると、あるYの値について、Xの場合の数の総和は$${{}_{2025}\mathrm{C}_{Y+1}}$$になっています。0<Y<2025ですから、$${{}_{2025}\mathrm{C}_2+…+{}_{2025}\mathrm{C}_{2025}}$$を求めれば良いことがわかります。
二項定理よりこの値は、$${2^{2025}-2025-1=2^{2025}-2026}$$通りです。❚

…というように便利な性質なので、皆さん是非使ってみて下さい。

ちなみに、上の問題は僕が作りました。
え、簡単だった？すみません、問題が見つからなかったものですので…