二項定理の問題ツイートを組合せ論的解釈と多項式・FPSで解く

今日は二項定理に関しての挑戦です！

10問あります！何問解けますか？

4問以上解ける人はCの扱いは特に問題ないと思います！

7問以上解ける人は本当に数学が好きな人なんだろうなと思いますね！#数学 #何問解けますか #美しい等式 pic.twitter.com/Mx1UNjtRKb
— 根本大貴 (@8z2Ie58UFRGxfzm) 2023年9月28日

このツイートを目にしたので, 解いてみました.

9問目は式が違うようなのでこれから解こうという方はお気を付けください.

(9)の最後のC(n,n)の部分はC(n,l)の誤りです。
申し訳ございません。
— 根本大貴 (@8z2Ie58UFRGxfzm) 2023年9月29日

最近競プロerの間でFPSを勉強しようという流れがあるようなのでFPSを用いた解法も載せようと思ったのですが, 多項式の範疇に収まるのがほとんどです. また, 最後にそれっぽい競プロの問題を何問か紹介します.

(1) $\sum_{i=0}^n {}_n C_i$

組合せ論的解釈

${}_n C_i$ は, $n$ 個の物から $i$ 個選ぶ方法の個数です. これをすべての $i (0 \leq i \leq n)$ について足し合わせた値は, $n$ 個の物から任意の個数を選ぶ方法の個数に等しくなります. このとき, $n$ 個の物を独立に選ぶか選ばないかを決められるので答えは $2^n$ となります.

多項式・FPS

$f(x) = \sum_{i=0}^n {}_n C_i x^i$ とすると, 答えは $f(1)$ です. 二項定理より $f(x)=(1+x)^n$ となるため, $f(1)=2^n$ が得られます.

(2) $\sum_{i=0}^{2n} (-1)^i {}_{2n} C_i$

組合せ論的解釈

この式は, 「 $2n$ 個の物から偶数個を選ぶ方法の個数」から「 $2n$ 個の物から奇数個を選ぶ方法の個数」を引いたものです. $2n$ 個の物のうち $2n-1$ 個の物について選ぶか選ばないかを決め, そのうえで最後の一個を選ぶか選ばないかを決めることにすると, 最後の一個を選んだ場合と選ばなかった場合のうち一方では奇数個, もう一方では偶数個が選ばれています. よって, $2n$ 個の物から偶数個を選ぶ方法の個数と奇数個を選ぶ方法の個数は等しく, その差は $0$ になります.*1

多項式・FPS

$f(x) = \sum_{i=0}^{2n} (-1)^i {}_{2n} C_i x^i$ とすると, 答えは $f(1)$ です. 二項定理より $f(x)=(1-x)^{2n}$ となるため, $f(1)=0$ が得られます.

(3) $\sum_{i=0}^n i \times {}_n C_i$

組合せ論的解釈

$i \times {}_n C_i$ は, $n$ 個の物の中から $i$ 個を選び, さらにその $i$ 個の中から $1$ 個を選ぶ方法の個数に等しいです*2. これをすべての $i (0 \leq i \leq n)$ について足し合わせた値を求めるには, まず二回選ばれる物を $n$ 個の中から選び, 残る $n-1$ 個を任意に選ぶ方法の個数を考えればよいです. 前者は $n$ 通り, 後者は $2^{n-1}$ 通りなので, 答えは $n2^{n-1}$ となります.

多項式・FPS

$f(x) = \sum_{i=0}^n i \times {}_n C_i x^i$ とすると, 答えは $f(1)$ です. 係数として二項係数に加えて $i$ が掛けられているのが厄介に思われますが, これは微分係数として得ることができます. 具体的には, (1)の式を微分したものに $x$ を掛けて次数を調整することで $f(x) = x( (1+x)^n)' = xn(1+x)^{n-1}$ となり, $f(1) = n2^{n-1}$ が得られます.

(4) $\sum_{i=0}^n \frac{ {}_n C_i }{i+1}$

組合せ論的解釈

$\frac{ {}_n C_i }{i+1}$ について考えます. $n$ 個の物から $i$ 個選ぶ方法の個数が ${}_n C_i$ ですが, ここで $n$ 個の物に $1$ から $n$ までの番号が付けられていて, 選ばれた $i$ 個の番号を昇順に並べると $x_1,x_2,\ldots,x_i$ になるものとします. さらに, $i+1$ 個の半開区間 $[0,x_1), [x_1, x_2), \ldots, [x_{i-1}, x_i), [x_i, n+1)$ を考えます.

$0$ 以上 $n+1$ 以下の整数をランダムに選んだとき, それが $k$ 番目の区間に含まれる確率を $P_k$ とします. この値は $k$ 番目の区間の幅に比例します. また, $k$ 番目の区間の幅が $l$ となるような場合の数を $c(k,l)$ とすると, 対称性より任意の $l$ に対して $c(1,l) = c(2,l) = \ldots = c(i,l) = c(i+1,l)$ が成り立ちます. 以上から, $n$ 個の物から $i$ 個選ぶ方法全体で $i+1$ 個の区間の幅の平均は等しく, ゆえに(選ぶ方法全体の平均としては) $P_1=P_2=\ldots=P_{i+1}=\frac{1}{i+1}$ となります. 特に $P_1=\frac{1}{i+1}$ であることに注目すると, $\frac{ {}_n C_i }{i+1}$ は「 $n$ 個の物から $i$ 個選ぶ方法それぞれに対して『 $0$ 以上 $n$ 以下の整数をランダムに選んだとき, それが $1$ 番目の区間に含まれる確率』を足したもの」となります.

これをすべての $i$ について足し合わせます. $y=0,1,\ldots,n$ に対し, $y$ が $1$ 番目の区間に含まれるような選び方は番号が $y$ 以下の物を選ばないような選び方に等しく, この個数は番号が $y$ より大きいものを任意に選ぶ方法の個数なので $2^{n-y}$ となります. そして, すべての $y$ に対するこの値の総和は $\sum_{i=0}{n} 2^i = 2^{i+1}-1$ です. 確率の分母は $n+1$ なので, 答えは $\frac{2^{n+1}-1}{n+1}$ となります. *3

多項式・FPS

(1)の式の $0$ から $t$ までの定積分を考えると $\int^t_0 (1+x)^n dx = \sum_{i=1}^{n+1} \frac{{}_n C_{i-1} t^i}{i} - 1$ となり, 対応する $f(x)$ と概ね一致します. 積分を式の展開をせずに計算し, $x$ で割る等して細部を整えると $f(x) = \frac{(1+x)^{n+1}-1}{(n+1)x}$ が導け, $f(1) = \frac{2^{n+1}-1}{n+1}$ となります.

(5) $\sum_{i=0}^m {}_{n+i} C_n$

組合せ論的解釈

平面上の座標 $(0,0)$ から始めて $(0,+1), (+1,0)$ の二種類の移動を繰り返して $(x,y)$ に移動する経路の個数は ${}_{x+y} C_x$ となることが知られています. これを考えると, 求める式の値は $(n,0), (n,1), \ldots,(n,m)$ までの経路数を足し合わせた値となります. (少々唐突ですが) 各 $i$ に対し, $(n+1,m)$ までの経路のうち $(n,i)$ から $(n+1,i)$ への移動を含むものの個数は $(n,i)$ までの経路数に等しいです. $(n+1,m)$ までの経路はこの分類で漏れ・重複が無いため, 答えは ${}_{n+m+1} C_m$ となります.

多項式・FPS

$\sum_{i=0}^{\infty} {}_{n+i} C_i x^i= \frac{1}{(1-x)^{n+1}}$ です(負の二項定理). 求めたいのはこれに $\sum_{i=0}^{\infty} x^i = \frac{1}{1-x}$ を掛けた式 $\frac{1}{(1-x)^{n+2}}$ の $x^m$ の係数であり, ${}_{n+m+1} C_m$ となります.

(6) $\sum_{i=1}^n {}_{3n} C_{3i-1}$

組合せ論的解釈

求めたいのは $3n$ 個の物から任意の個数を選ぶ方法のうち, 選ばれた個数を $3$ で割った余りが $2$ となるものの個数です. これを $a_n$ とします. $3n$ 個の物のうち $3n-3$ 個の物について選ぶか選ばないかを決め, そのうえで残りの $3$ 個を選ぶか選ばないかを決めることにします. $3$ 個に対して選ぶか選ばないかを決めると, 選ばれた個数を $3$ で割った余りはそれぞれ $3$ 通りにおいて $1, 2$ に, $2$ 通りにおいて $0$ になります. このことから, $a_n$ は「 $3n-3$ 個から選ぶ方法であって, 選ばれた個数を $3$ で割った余りが $0$ または $2$ であるもの」の $3$ 倍と「 $3n-3$ 個から選ぶ方法であって, 選ばれた個数を $3$ で割った余りが $1$ であるもの」の $2$ 倍の和になります. これと(1)の結果を使うと $a_n = 3\times 2^{3n-3} - a_{n-1}$ となり, 変形や代入によって $a_n = 3 \times \sum_{i=0}^{n-1} (-1)^i 8^{n-1-i}$ が得られます. 等比数列の和の公式を用いてこれを計算すると, 答えは $\frac{8^n - (-1)^n}{3}$ となります.

多項式・FPS

求めたいのは $g(x)=x^2(1+x)^{3n}$ から, 次数が $3$ の倍数であるような項のみを取り出した関数 $f(x)$ に対する $f(1)$ の値です.

$\omega$ を $1$ の三乗根のうち $x^2+x+1=0$ の解であるものとします. すると, $g(x) + g(\omega x) + g(\omega ^2 x)$ は次数が $3$ の倍数でない項が $1+\omega + \omega^2 = 0$ となって消えるため, $3f(x)$ に等しくなります. よって $f(1) = \frac{g(1) + g(\omega) + g(\omega ^2)}{3}$ となり, $(1+\omega )^3=-1$ や $1+\omega + \omega^2=0$ を使いながら計算することで $f(1) = \frac{8^n - (-1)^n}{3}$ が得られます.

(7) $\sum_{i=0}^n i^2 \times {}_n C_i$

組合せ論的解釈

(3)と同様に, $n$ 個の物の中から $i$ 個を選び, さらにその $i$ 個の中から重複を許して $2$ 個を選ぶ方法の個数をすべての $i$ について足し合わせます. ある一個が $3$ 回選ばれる場合の数は $n2^{n-1}$ , 二個が $2$ 回ずつ選ばれる場合の数は $n(n-1)2^{n-2}$ なので答えは $n(n+1)2^{n-2}$ となります.

多項式・FPS

(3)の結果をもう一度微分して $x$ 倍すると $f(x) = xn(n-1)(1+x)^{n-2} + n(1+x)^{n-1}$ が得られます. これより $f(1) = n(n+1)2^{n-2}$ となります.

(8) $\sum_{i=0}^n {}_{2n-i} C_i$

組合せ論的解釈

普通の ${}_{2n} C_i$ のような式と違い, 選ぶたびに物が減っていきます. そこで, 「 $2n$ 個の物から $i$ 回選ぶ. 選ぶときは選ばれていない物のうち連続する $2$ 個を選んで塊にしないといけない. (選ぶ順番は区別しない)」というようなことを考えると, 選ばれなかった $1$ 個の物と選ばれたことで生じた $2$ 個の物からなる塊を並べて合計 $2n$ 個とする方法の個数となり, フィボナッチ数列の $2n$ 番目の項が答えとなります.

多項式・FPS

$f=(1+x)x$ とすると, 求めたいのは $\sum_{i=0}^{\infty}f^i$ の $x^{2n}$ の係数です. $f=x+x^2$ なのでこれは結局 $+1, +2$ を繰り返して合計で $2n$ にする方法の個数と一致し, フィボナッチ数列の $2n$ 番目の項と分かります.

(9) $\sum_{i=0}^l {}_n C_{i} \times {}_{m} C_{l-i}$

組合せ論的解釈

$n+m$ 個から $l$ 個選ぶ方法を, $n$ 個の中から何個選ぶかで分けて足し合わせいるにすぎず, ${}_{n+m} C_l$ となります.*4.

多項式・FPS

$(1+x)^n(1+x)^m$ の $l$ 次の項の係数が答えであり, この式は $(1+x)^{n+m}$ となるので ${}_{n+m} C_l$ となります.

(10) $\sum_{i=1}^n ({}_{2n} C_{2i-1})^2$

組合せ論的解釈

${}_2n C_i = {}_2n C_{2n-i}$ なので, $\sum_{i=1}^n {}_{2n} C_{2i-1} \times {}_{2n} C_{2n - 2i + 1}$ が求めたい値です. (9)の考え方を用いると「 $4n$ の物から合計で $2n$ 個選ぶ方法であって, 前半の $2n$ 個からは奇数個が選ばれるようなもの」が答えとなります. $4n$ 個の物に, 前半の $2n$ 個と後半の $2n$ 個でそれぞれ $1$ から $2n$ まで番号が付けられているとします.

$4n$ 個から $2n$ 個選ぶ方法のうち, 前半で番号 $x$ の物と後半で番号が $x$ の物とでちょうど一方が選ばれているような $x$ の有無で場合分けをします.

そのような $x$ が存在する場合, その最小値 $x'$ に対し, $x'$ 番目の選び方を入れ替える(前半が選ばれていればそれをやめて代わりに後半を選び, 後半が選ばれていれば代わりに前半を選ぶ)ことで前半から選ばれている個数の偶奇を入れ替えられます. また, これによって $x'$ の位置は変わらないことから, $x$ が存在する場合は前半から奇数個選ばれる方法と偶数個選ばれる方法とで対応が取れています. このとき, 奇数個選ばれる方法の個数を $A$ とします.
そのような $x$ が存在しない場合, ちょうど $n$ 個の番号において前半と後半の両方から選ばれており, この場合の数は ${}_{2n} C_n$ です. また, 前半から選ばれている個数の偶奇は $n$ の偶奇によります.

以上から ${}_{4n} C_{2n} = {}_{2n} C_n + 2A$ が得られ, $A =\frac{ {}_{4n} C_{2n} - {}_{2n} C_n} {2}$ と分かります. また, $x$ が存在しない場合は $n$ が奇数の場合に限り計上されますが, $\frac{{}_{2n} C_n - (-1)^n {}_{2n} C_n}{2}$ が対応する式となります. よって, 答えは $\frac{ {}_{4n} C_{2n} - {}_{2n} C_n} {2} + \frac{{}_{2n} C_n - (-1)^n {}_{2n} C_n}{2} = \frac{ {}_{4n} C_{2n} - (-1)^n {}_{2n} C_n}{2}$ です.

多項式・FPS

${}_2n C_i = {}_2n C_{2n-i}$ なので, $\sum_{i=1}^n {}_{2n} C_{2i-1} \times {}_{2n} C_{2n - 2i + 1}$ が求めたい値です. $g(x) = \sum_{i=0}^{2n} {}_{2n} C_i x^i = (1+x)^{2n}$ とすると, $g(x)$ の奇数次の項のみを取り出した関数 $f(x)$ に対する $f(x)^2$ の $x^{2n}$ の係数が答えとなります. $f(x) = \frac{g(x) - g(-x)}{2} = \frac{(1+x)^{2n} - (1-x)^{2n}}{2}$ なので, $f(x)^2 = \frac{(1+x)^{4n} + (1-x)^{4n} - 2(1-x^2)^{2n}}{4}$ となり, $x^{2n}$ の係数は $\frac{{}_{4n} C_{2n} -{}_{2n} C_n (-1)^n }{2}$ となります.