3東京医科歯科大学 2001年 数学 第3問解答・解説

条件 $Z,P_n$ より $A$ は $[n]=\{1,2,\ldots,n\}$ の部分集合である。したがって $f(n,k)$ は $[n]$ の $k$ 個の要素からなる部分集合の個数であり、空集合と $[n]$ 自身はそれぞれ一つなので $$f(n,0)=1,\qquad f(n,n)=1.$$ また、$n>k\ge1$ とする。$n$ を含まない場合は $[n-1]$ から $k$ 個を選び、含む場合は $n$ 以外から $k-1$ 個を選ぶから $$f(n,k)=f(n-1,k)+f(n-1,k-1).$$

条件 $R$ が破れるのは、$x,y\in A$ で $x-y+1=0$、すなわち $y=x+1$ となるときに限る。よって $R$ は $A$ に連続する二整数が含まれないことと同値である。$n\in A$ ならば $n-1\notin A$ である。$n$ を含まない場合と含む場合に分けると、$n>k\ge1$ のとき $$g(n,k)=g(n-1,k)+g(n-2,k-1).$$

連続しない $k$ 個の整数を $1\le a_1<a_2<\cdots<a_k\le n$ とする。各 $i$ について $b_i=a_i-(i-1)$ とおくと、$1\le b_1<b_2<\cdots<b_k\le n-k+1$ となる。逆にこの範囲の $k$ 個の整数 $b_i$ から $a_i=b_i+(i-1)$ と戻せば、連続しない $k$ 個の整数が得られる。この対応は一対一なので $$\displaystyle g(n,k)=\binom{n-k+1}{k}.$$ したがって $$\displaystyle h(m,0)=g(m-1,0)=1,\qquad h(m,m)=g(2m-1,m)=\binom{m}{m}=1.$$ さらに $m>\ell\ge1$ では $g$ の漸化式を $n=m+\ell-1,\ k=\ell$ に適用して $$\begin{aligned} h(m,\ell)&=g(m+\ell-1,\ell)\\ &=g(m+\ell-2,\ell)+g(m+\ell-3,\ell-1)\\ &=h(m-1,\ell)+h(m-1,\ell-1). \end{aligned}$$ 最後に $$\displaystyle g(12,4)=\binom{12-4+1}{4}=\binom{9}{4}=126.$$

組合せの上側の整数が選ぶ個数より小さい場合、その選び方は0通りとする。