2017　東京工業大学　第５類AO総合問題MathJax

(1)　$a(n)$と$b(n,k)$は，式１と式２でそれぞれ定義されている．$a(5)$および$b(7,3)$の値を求めよ．

$a(n)=\{\begin{array}{ll}1& \text{（}n=1\text{）}\\ a(n-1)\times n& \text{（}n>1\text{）}\end{array}$（式１）

$b(n,k)=\{\begin{array}{ll}n& \text{（}k=1\text{）}\\ b(n,k-1)\times n& \text{（}k>1\text{）}\end{array}$（式２）

(2)　$c(n,k)$は式３で定義されている．図１の(A)〜(C)に示す木構造は，式３の(A)〜(C)それぞれの式変形を図示している．図２は，ある$c(n,k)$について定義に基づく式変形で得られる木構造である．図２の【ア】〜【ウ】に該当する$c(n,k)$とその値を求めよ．

$c(n,k)=\{\begin{array}{lll}1& \text{（}n=k\text{）}& \text{(A)}\\ n& \text{（}k=1\text{）}& \text{(B)}\\ c(n-1,k-1)+c(n-1,k)& \text{（}n>k>1\text{）}& \text{(C)}\end{array}$（式３）

• 

  図１

• 

  図２

(3)　(2)の方法で得られる$c(n,k)$の木構造において，葉を除く節点の個数を$d(n,k)$とする．式４の【エ】〜【ク】を答えよ．

$d(n,k)=\{\begin{array}{ll}\text{【エ】}& \text{（}n=k\text{または}k=1\text{）}\\ d(\text{【オ】},\text{【カ】})+d(\text{【キ】},\text{【ク】})+1& \text{（}n>k>1\text{）}\end{array}$（式４）

(4)　$n\geqq 1$かつ$k\geqq 1$のとき，異なる$n$個から重複を許して$k$個をとる組合せの数を$e(n,k)$とする．式５の【ケ】〜【ス】を答えよ．

$e(n,k)=\{\begin{array}{lll}\text{【ケ】}& \text{(}n=1\text{または}k=1\text{)}& \text{(D)}\\ e(\text{【コ】},\text{【サ】})+e(\text{【シ】},\text{【ス】})& \text{（}n>1\text{かつ}k>1\text{）}& \text{(E)}\end{array}$（式５）

(5)　式５の(E)が成り立つ理由を$150$字程度で説明せよ．

　杭$x$の最上位から杭$y$の最上位に円盤を一枚移動する一回の操作を$M(x,y)$とする．$n$枚の円盤を杭$x$から$x$とは異なる杭$y$に，最小回数の操作で移動する操作列を$L(n,x,y)$として，その回数を$H(n)$とする．以下では，三本の杭を$\mathrm{A}\text{，}\mathrm{B}\text{，}\mathrm{C}$とする．例えば，$n=2$のとき，

$\begin{array}{lll}L(2,\mathrm{A},\mathrm{B})& =& (M(\mathrm{A},\mathrm{C}),M(\mathrm{A},\mathrm{B}),M(\mathrm{C},\mathrm{B}))\text{，}\\ H(2)& =& 3\end{array}$

である．

(1)　$L(4,\mathrm{A},\mathrm{C})$を$L(3,\mathrm{*},\mathrm{*})$と$M(\mathrm{*},\mathrm{*})$からなる操作列で答えよ．ただし，$M(\mathrm{*},\mathrm{*})$の個数を最小にせよ．「$\mathrm{*}$」は適切な杭を表す．

(2)　$L(4,\mathrm{A},\mathrm{C})$を$L(2,\mathrm{*},\mathrm{*})$と$M(\mathrm{*},\mathrm{*})$からなる操作列で答えよ．ただし，$M(\mathrm{*},\mathrm{*})$の個数を最小にせよ．「$\mathrm{*}$」は適切な杭を表す．

(3)　式６は，$L(n,x,y)$の再帰的定義である．式６の【ア】〜【エ】を答えよ．ただし，$x\text{，}y$どちらでもない杭を$z$とせよ．

$L(n,x,y)=\{\begin{array}{ll}\text{【ア】}& \text{（}n=1\text{）}\\ (\text{【イ】},\text{【ウ】},\text{【エ】})& \text{（}n>1\text{）}\end{array}$（式６）

(4)　式７は，$H(n)$の再帰的定義である．式７の【オ】〜【キ】を答えよ．

$H(n)=\{\begin{array}{ll}\text{【オ】}& \text{（}n=1\text{）}\\ 2\times \text{【カ】}+\text{【キ】}& \text{（}n>1\text{）}\end{array}$（式７）

(5)　式８は，再帰によらない$H(n)$の式である．【ク】〜【コ】を答えよ．導出の過程を示すこと．

$H(n)={\text{【ク】}}^{\text{【ケ】}}-\text{【コ】}$（式８）

(6)　各円盤の番号を小さい円盤から順に$1\text{，}2\text{，}\cdots \text{，}n$とする．$L(10,\mathrm{A},\mathrm{C})$において$852$回目の操作で移動する円盤の番号および移動元と移動先の杭を答えよ．