母関数と数列(東京大学2020年前期数学文理共通第4問)

今年の東大数学は少し傾向が変化した印象を受けます。確率分野からの出題が3年連続で無かったのはここ数十年では初めてのことです。また、毎年のように出題されていた整数問題が今年は出題されませんでした。一方で、図形に関連した問題が4題も出題されました。手の付けられないような難問はありませんでしたが決して易化した訳ではなく、学力差がよく反映される試験だったと言えます。

今回は文理共通の数学第4問を取り上げます。文理ともに今年のセットで一番差が付いた問題だと思いますが、母関数を背景にした面白い問題です。


《問題》

$n$、$k$を $1 \leqq k \leqq n$ を満たす整数とする。$n$個の整数$$2^{m} \quad(m=0,1,2, \cdots \cdots, n-1)$$から異なる$k$個を選んでそれらの積をとる。$k$個の整数の選び方すべてに対しこのように積をとることにより得られる${}_{n}\mathrm{C}_{k}$個の整数の和を$a_{n, k}$とおく。例えば、$$\small a_{4,3}=2^{0} \cdot 2^{1} \cdot 2^{2}+2^{0} \cdot 2^{1} \cdot 2^{3}+2^{0} \cdot 2^{2} \cdot 2^{3}+2^{1} \cdot 2^{2} \cdot 2^{3}=120$$である。

(1)$2$以上の整数$n$に対し、$a_{n,2}$を求めよ。

(2)$1$以上の整数$n$に対し、$x$についての整式$$f_{n}(x)=1+a_{n, 1} x+a_{n, 2} x^{2}+\cdots \cdots+a_{n, n} x^{n}$$を考える。 $\dfrac{f_{n+1}(x)}{f_{n}(x)}$ と $\dfrac{f_{n+1}(x)}{f_{n}(2 x)}$ を$x$についての整式として表せ。

(3)$\dfrac{a_{n+1, k+1}}{a_{n, k}}$ を$n$、$k$で表せ。

(東京大学2020年 前期理系第4問)


《考え方》

一見すると複雑そうに見える問題です。二項係数の登場する問題は最近だと2009年、2015年、2018年に出題されていますが、今年は整数問題ではなく整式の問題として出題されました。

題意が取りにくいときは「小さい$n$で様子を見る」を実践しましょう。(1)では多項定理が利用できそうだと気が付ければしめたもの。もし気付けなかったとしても漸化式で処理できます。

(2)はなかなか複雑そうに見えますが、これも題意をちゃんと読み取れれば解けるはずです。ただ、整式$f_{n}(x)$の形をいきなり思い付けるかどうかは経験の差が如実に表れてくるところです。$n$を固定して$k$の漸化式を立てる、といった方針も有効だと気付ければ突破できるかもしれません(ただし時間は掛かりそうです)。

(3)は(2)の結果を利用しましょう。$f_{n+1}(x)$について2種類の式を得ているので、両者で$x^{n+1}$の項の係数を比較することで$\dfrac{a_{n+1, k+1}}{a_{n, k}}$を求めることができます。

●   ●   ●

解答例

 

(1)

$n$個の整数$2^{0}$、$2^{1}$、$2^{2}$、$\cdots$、$2^{n-1}$から重複を許して$2$個を選んで作られるそれらの積の総和は$$(2^{0} + 2^{1} + 2^{2} + \cdots + 2^{n-1})^{2}$$と表すことができる。$a_{n,2}$を用いてこれを展開すると$$\sum^{n-1}_{k=0} (2^{k})^{2}+2a_{n,2}$$となるから、$$\begin{align} a_{n,2}=\,& \dfrac{1}{2}\left\{\left(\sum^{n-1}_{k=0}2^{k}\right)^{2}-\sum^{n-1}_{k=0} (2^{k})^{2}\right\} \\ =\,& \dfrac{1}{2}\left\{\left(\dfrac{2^n-1}{2-1}\right)^{2}-\dfrac{4^n-1}{4-1}\right\} \\ =\,& \color{red}{\dfrac{4^n}{3}-2^n+\dfrac{2}{3}}\end{align}$$

 

 

(2)

$n$個の単項式 $2^m(=0,1,\cdots,n-1)$ の中から異なる$k$個を選んでそれらの積をとり、$k$個の選び方すべてに対してこのような積の総和をとることより得られる${}_{n}\mathrm{C}_{k}$個の整数の和は$a_{n, k} x^{k}$であるから、$$f_{n}(x)=\left(1+2^{0} x\right)\left(1+2^{1} x\right) \cdots \cdots\left(1+2^{n-1} x\right)$$が成り立つ。よって、$$\small \begin{cases}
f_{n+1}(x)=\left(1+2^{0} x\right)\left(1+2^{1} x\right) \cdots \cdots\left(1+2^{n-1} x\right)\left(1+2^{n} x\right) \\
f_{n}(2 x)=\left(1+2^{1} x\right)\left(1+2^{2} x\right) \cdots \cdots\left(1+2^{n} x\right)
\end{cases}$$より、$$\small \begin{cases}
f_{n+1}(x)=f_{n}(x)\left(1+2^{n} x\right) & \cdots ① \\
f_{n+1}(x)=\left(1+2^{0} x\right) f_{n}(2 x)=(1+x) f_{n}(2 x) & \cdots ②
\end{cases}$$という2式を得る。これらより、$$\dfrac{f_{n+1}(x)}{f_{n}(x)}=\color{red}{1+2^{n} x}$$および$$\dfrac{f_{n+1}(x)}{f_{n}(2 x)}=\color{red}{1+x}$$を得る。

 

 

(3)

①、②の2式において$x^{k+1}$の係数を比較すると$$\begin{cases}
a_{n+1, k+1}=2^{n} a_{n, k}+a_{n, k+1} & \cdots ③ \\
a_{n+1, k+1}=2^{k} a_{n, k}+2^{k+1} a_{n, k+1} & \cdots ④
\end{cases}$$となるので、③と④を連立して$a_{n, k+1}$を消去することで、$$\dfrac{a_{n+1, k+1}}{a_{n, k}}=\color{red}{\dfrac{2^{k}\left(2^{n+1}-1\right)}{2^{k+1}-1}}$$を得る。

 


(コメント)

解答を見てしまうと、何ともあっさり解けてしまっている印象を受けると思います。(2)では$a_{n, k}$の定義から$f_{n}(x)$を積の形で導いていますが、これは二項定理の式 $(1+x)^n$ を考えると分かりやすいと思います。異なる$n$個から$k$個の積をとったときの${}_{n}\mathrm{C}_{k}$個の整数の総和の母関数は、二項定理の母関数 $(1+x)^n$ と同じ原理で導かれます。試験場で(2)の多項式の導き方を思いつかなければ潔く退散して他の問題に時間を割くべきでしょう。

 

 

母関数について詳しく知りたい方は「母関数について」のページをご覧下さい。因みに、この数列$a_{n, k}$はオンライン整数列大辞典「OEIS」に未登録のようです。

 

母関数をあらわに取り扱った出題は近年では珍しい気がします。東大がこのようなタイプの問題を出したことで、もしかすると他の大学でも来年以降は数列と母関数を絡めた出題が相次ぐかもしれません。難関大志望の受験生やその指導をされている方は母関数について今一度確認してみると良いでしょう。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です