2018年入試問題研究に戻る

慶応医1(3)解答

解法1 
$ 2k+2k $ 個の円順列を, $ 2k $ の約数 $ l $ に関して, $ \dfrac{1}{l} $ の回転ではじめて重なるものを考え, それで場合分けする.
そして,円順列を $ l $ 分した部分の順列を数えることで,対応する円順列を数える.
$ k=1 $ のとき.
$ l=2 $ のとき.2分した部分は,白赤か赤白で,同じ円順列を作る.1通り.
$ l=1 $ のとき.白と白,赤と赤が隣りあうので,1通り.
\[ N_1=1+1=2 \] $ k=2 $ のとき.
$ l=4 $ のとき.4分した部分は白赤か赤白で,同じ円順列を作る.1通り.
$ l=2 $ のとき.2分した部分は白赤赤白,赤白白赤,白白赤赤,赤赤白白で,これらは同じ円順列を作る.1通り.
$ l=1 $ のとき.それ以外の順列は \[ \dfrac{8!}{4!4!}-4-2=64 \] あり,これらからできる円順列は $ \dfrac{64}{8}=8 $ 通りである.よって, \[ N_2=1+1+8=10 \] $ k=3 $ のとき.
$ l=6 $ のとき.6分した部分は白赤か赤白で,同じ円順列を作る.1通り.
$ l=3 $ のとき.3分した部分は白赤赤白,赤白白赤,白白赤赤,赤赤白白で,これらは同じ円順列を作る.1通り.
$ l=2 $ のとき.2分した部分は \[ {}_6 \mathrm{C}_3-2=18 \] なので,これからできる円順列は $ \dfrac{18}{6}=3 $ 通り.
$ l=1 $ のとき.それ以外の順列は \[ \dfrac{12!}{6!6!}-18-4-2=900 \] あり,これらからできる円順列は $ \dfrac{900}{12}=75 $ 通りである.よって, \[ N_3=1+1+3+75=80 \]

解法2 
$ k=2 $ のとき. 円周上の等間隔におかれた8点に,位置も区別して2色の玉を配置する. その総数は $ \dfrac{8!}{4!4!}=70 $ である.玉の配置の集合を $ X $ とする. $ X $ の要素を $ x $ で表し, $ X $ の要素の個数を $ \left|X \right| $ で表す. $ \left|X \right|=70 $ である. この円周の,角度が $ \dfrac{k}{8}\cdot 2\pi $ の回転を $ \sigma_k\ (k=0,\ 1,\ \cdots,\ 7) $ と表し, この回転の集合を $ G $ と表す. $ G $ の要素を $ g $ で表す. $ \left|G \right|=8 $ である. $ x $ を $ g $ で回転した配置を $ g(x) $ で表す.
集合 $ X $ を,回転して同じになるものどうしの部分集合に分割する. これらは互いに共通部分のない部分集合であり,その総数を $ N_2 $ とおくのであるから \[ X=X_1\cup X_2\cup \cdots \cup X_{N_2} \] と表せる.
各 $ X_l $ は, $ X_l $ に含まれる任意の $ x $ に対して $ X_l\subset \{g(x)\ |\ g\in G\} $ かつ $ \{g(x)\ |\ g\in G\}\subset X_l $ なので, \[ X_l=\{g(x)\ |\ g\in G\} \] とも表せる.
一般に,ある $ x $ に対し, $ G $ のすべての $ g $ で $ g(x) $ を作ると, この中には同じものが含まれている. $ i\ne j $ で $ \sigma_i(x)=\sigma_j(x) $ となる $ i,\ j $ があるということは, $ j-i=p\quad (\bmod \ 8) $ となる $ p $ で $ x=\sigma_p(x) $ なので, $ g(x)=x $ となる回転 $ g $ で $ \sigma_0 $ とは異なるものが存在することと同値である.
したがって, \[ \left|X_l \right|=|G|-\biggl[\ g(x)=xとなる\sigma_0でないgが存在するx\ (\in X_l)\ の個数\ \biggr] \] である. $ x $ を変えない回転の個数は $ X_l $ に属する他の要素をとっても同じである. \begin{eqnarray*} \left|X\right|&=&\left|X_1\right|+ \cdots +\left|X_{N_2}\right|\\ &=&|G|N_2-\biggl[g(x)=xとなる\sigma_0でないgが存在するx\ (\in X)\ の個数\biggr] \end{eqnarray*} となる.ここで, $ g $ の作用で動かない $ X $ の要素よりなる部分集合を $ X^g $ と表す. \[ \biggl[\ g(x)=xとなる\sigma_0でないgが存在するxの個数\ \biggr]=\sum_{g\ne \sigma_0}\left|X^g\right| \] となる.つまり, \[ \biggl[ g(x)=xとなるものが存在するxの個数\biggr]=\sum_g\left|X^g\right| \] となる. \[ \left|X\right|=|G|N_2-\sum_{g\ne \sigma_0}\left|X^g\right| \] 一方, $ X=X^{\sigma_0} $ であるから, \[ |G|N_2=\sum_{g\in G}\left|X^g\right| \] となる.
ここで, $ X^{\sigma_1},\ X^{\sigma_3},\ X^{\sigma_5} $ は空集合である. $ X^{\sigma_2}=X^{\sigma_4} $ の要素は赤玉と白玉が交互に並ぶときで,位置の区別を考え \[ \left|X^{\sigma_2} \right|=\left|X^{\sigma_4} \right|=2 \] である. $ X^{\sigma_4} $ の要素は,赤玉と白玉が交互に並ぶときと,2個ずつ交互に並ぶときである. \[ \left|X^{\sigma_4} \right|=2+2\times 2=6 \] $ |G|=8 $ なので, \[ N_2=\dfrac{1}{8}\left(70+2+6+2 \right)=10 \] である.

$ k=3 $ のとき. 円周上の等間隔におかれた12点に,位置も区別して2色の玉を配置する. その総数は $ \dfrac{12!}{6!6!}=924 $ である. また,回転の集合 $ G $ は $ |G|=12 $ であるから,記号を含め 同様に考え \[ 12N_3=\sum_{g}\left|X^g\right| \] である.ここで, $ X^{\sigma_1},\ X^{\sigma_3},\ X^{\sigma_5},\ X^{\sigma_7},\ X^{\sigma_9} $ は空集合である. $ X^{\sigma_2}=X^{\sigma_{12}} $ の要素は赤玉と白玉が交互に並ぶときで,位置の区別を考え \[ \left|X^{\sigma_2} \right|=\left|X^{\sigma_{12}} \right|=2 \] である. $ X^{\sigma_4}=X^{\sigma_8} $ の要素は,赤玉と白玉が交互に並ぶときと,2個ずつ交互に並ぶときである. \[ \left|X^{\sigma_4} \right|=\left|X^{\sigma_8} \right|=2+2\times 2=6 \] である. $ X^{\sigma_6} $ の要素は, 赤玉と白玉が交互に並ぶとき, 3個ずつ交互に並ぶとき, 6個ずつ並ぶときである. よって, \[ \left|X^{\sigma_6} \right|=2+3\times 2+6\times 2=20 \] である. \[ N_3=\dfrac{1}{12}\left(924+2+6+20+6+2 \right)=80 \] となる.

$ k=1 $ のとき.同様に考え, \[ N_1=\dfrac{1}{4}\left(6+2 \right)=2 \] となる.

注意1)  解法2の考察は一般化できる.
有限集合 $ X $ に、有限個の要素からなる回転などの変換が作用しているとする. ここにはすべてを固定するものも含まれているとする.つまり,群 $ G $ が作用しているとする.
$ x\in X $ をとる.集合 $ \{g(x)\ |\ g\in G \} $ を $ G(x) $ と書き表す. これを $ G $ による $ x $ の軌跡という.
$ x,\ y \in X $ に対して \[ G(x)=G(y)\ または\ G(x)\cap G(y)=\emptyset \] のいずれかであるから, $ X $ はいくつかの軌跡に分割される. 軌跡の総数を $ \left|X/G \right| $ と表す.解答と同様に, $ g $ の作用で動かない $ X $ の要素よりなる部分集合を $ X^g $ と表す.このとき, \[ \left|X/G \right|=\dfrac{1}{|G|}\sum_{g\in G}\left|X^g\right| \] がなりたつ.これをバーンサイドの補題という.

注意2)  円順列の総数を求める一般的な方法がある. 『数論初歩』の 「オイラーの関数」 「円順列への反転公式の応用」 にある.そこでの記号を用いると, \begin{eqnarray*} N_1&=&f(2,\ 2)=\dfrac{1}{4}\left\{\varphi(2)F(1,\ 1)+\varphi(1)F(2,\ 2) \right\}\\ &=&\dfrac{1}{4}\left(1\cdot\dfrac{2!}{1!1!}+1\cdot\dfrac{4!}{2!2!}\right) =\dfrac{2+6}{4}=2\\ N_2&=&f(4,\ 4)=\dfrac{1}{8}\left\{\varphi(4)F(1,\ 1)+\varphi(2)F(2,\ 2)+\varphi(1)F(4,\ 4) \right\}\\ &=&\dfrac{1}{8}\left(2\cdot\dfrac{2!}{1!1!}+1\cdot\dfrac{4!}{2!2!}+1\cdot\dfrac{8!}{4!4!} \right) =\dfrac{4+6+70}{8}=10\\ N_3&=&f(6,\ 6)=\dfrac{1}{12} \left\{\varphi(6)F(1,\ 1)+\varphi(3)F(2,\ 2) +\varphi(2)F(3,\ 3) +\varphi(1)F(6,\ 6) \right\}\\ &=&\dfrac{1}{12} \left(2\cdot\dfrac{2!}{1!1!}+2\cdot\dfrac{4!}{2!2!}+1\cdot\dfrac{6!}{3!3!}+1\cdot\dfrac{12!}{6!6!} \right) =\dfrac{4+12+20+924}{12}=80 \end{eqnarray*} となる.

注意3) なお,先の解答の例えば$k=3$のときを,そこでの記号で表すと次のようになる.
$n_1=n_2=6$ で $g=6$ である. \[ f(6,\ 6)=p(1,1)+p(2,2)+p(3,3)+p(6,6) \] であるが, \begin{eqnarray*} F(6,\ 6)&=&2p(1,1)+4p(2,2)+6p(3,3)+12p(6,6)\\ F(3,\ 3)&=&2p(1,1)+6p(3,3)\\ F(2,\ 2)&=&2p(1,1)+4p(2,2)\\ F(1,\ 1)&=&2p(1,1) \end{eqnarray*} なので,これを逆に解いて, \begin{eqnarray*} p(6,\ 6)&=&\dfrac{1}{12}\left\{F(6,\ 6)-F(3,\ 3)-F(2,\ 2)+F(1,\ 1)\right\}\\ p(3,\ 3)&=&\dfrac{1}{6}\left\{F(3,\ 3)-F(1,\ 1)\right\}\\ p(2,\ 2)&=&\dfrac{1}{4}\left\{F(2,\ 2)-F(1,\ 1)\right\}\\ p(1,\ 1)&=&\dfrac{1}{2}F(1,1) \end{eqnarray*} これより, \begin{eqnarray*} f(6,\ 6)&=&\dfrac{1}{12}\left\{(1-2-3+6)F(1,\ 1)+(-1+3)F(2,\ 2)+(-1+2)F(3,\ 3)+F(6,\ 6)\right\}\\ &=&\dfrac{1}{12}\left[\{(-1)^2+(-1)^12+(-1)^13+6\}F(1,\ 1)\right.\\ &&\quad \quad \left.+\{(-1)^1+3\}F(2,\ 2)+\{(-1)^1+2\}F(3,\ 3)+F(6,\ 6)\right]\\ &=&\dfrac{1}{12}\left[\{\mu(6)+\mu(3)2+\mu(2)3+\mu(1)6\}F(1,\ 1)\right.\\ &&\quad \quad \left.+\{\mu(3)+\mu(1)3\}F(2,\ 2)+\{\mu(2)+\mu(1)2\}F(3,\ 3)+F(6,\ 6)\right]\\ &=&\dfrac{1}{12}\left[\left\{\sum_{d|6}\mu\left(\dfrac{6}{d} \right)d \right\}F(1,\ 1) +\left\{\sum_{d|3}\mu\left(\dfrac{3}{d} \right)d \right\}F(2,\ 2)\right.\\ &&\quad \quad \left.+\left\{\sum_{d|2}\mu\left(\dfrac{2}{d} \right)d \right\}F(3,\ 3)+F(6,\ 6)\right]\\ &=&\dfrac{1}{12} \left\{\varphi(6)F(1,\ 1)+\varphi(3)F(2,\ 2) +\varphi(2)F(3,\ 3) +\varphi(1)F(6,\ 6) \right\} \end{eqnarray*} を得る.
これを,反転公式を用いて一般的に書き下したものが,「円順列への反転公式の応用」 にある円順列の総数を求める方法である.

問題