東北大学 2019年度 後期日程 第2次学力試験文系（後期）数学 第4問

(1)
まず条件(i),(ii)だけを満たす表を数える。$k=2$ では $$1\leqq a_1\leqq a_2\leqq n$$ を満たす組は $${}_{n+1}{\mathrm{C}}_2=\frac{n(n+1)}{2}$$ 個あり、$b_1,b_2$ も同じだけある。したがって全体は ${\left\{\frac{n(n+1)}{2}\right\}}^2$ 個である。

次に、すべての $i$ で $a_i\leqq b_i$ となる表を数える。固定した $b_1,b_2$ に対して、$a_1\leqq a_2$、$a_1\leqq b_1$、$a_2\leqq b_2$ を満たす組を数えると、合計は $\frac{n(n+1{)}^2(n+2)}{12}$ である。上下を入れ替えれば、すべての $i$ で $a_i\geqq b_i$ となる表も同じ個数である。また両方に含まれるのは $a_i=b_i$ が全ての $i$ で成り立つ場合で、その個数は $\frac{n(n+1)}{2}$ である。

条件(iii)を満たさない表は、すべて $a_i\leqq b_i$ であるか、すべて $a_i\geqq b_i$ である表である。よって包除原理により$$\begin{array}{rl}{\displaystyle A_{n,2}}& {\displaystyle ={\left\{\frac{n(n+1)}{2}\right\}}^2-2\cdot \frac{n(n+1{)}^2(n+2)}{12}+\frac{n(n+1)}{2}}\\ {\displaystyle }& {\displaystyle =\frac{n(n-1)(n-2)(n+1)}{12}}\end{array}$$である。

(2)
条件(i),(ii),(iii)を満たす表に対して、上段と下段を入れ替える対応を考える。つまり $(a_1,\dots ,a_k),(b_1,\dots ,b_k)$ を $(b_1,\dots ,b_k),(a_1,\dots ,a_k)$ に対応させる。この対応は再び条件(i),(ii),(iii)を満たす表を与える。

また、条件(iii)を満たす表では、上下段を入れ替えても元の表と同じになることはない。もし同じなら全ての $i$ で $a_i=b_i$ となり、条件(iii)に反するからである。したがって表は2つずつ組になる。よって $A_{n,k}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}2)$ すなわち $A_{n,k}$ は偶数である。

(3) $n=3,k=3$ とする。条件(i)を満たす非減少列は $111,112,113,122,123,133,222,223,233,333$ の10通りである。したがって条件(i),(ii)だけを満たす表は ${10}^2=100$ 個である。

次に、すべての $i$ で $a_i\leqq b_i$ となる表を数える。上の10個の $b$ の列に対して可能な $a$ の個数は順に $1,2,3,3,5,6,4,7,9,10$ である。したがってその合計は $1+2+3+3+5+6+4+7+9+10=50$ である。すべて $a_i\geqq b_i$ の場合も同じく50個である。両方に含まれるのは $a_i=b_i$ が全ての $i$ で成り立つ10通りである。

よって $$A_{3,3}=100-2\cdot 50+10=10$$ である。

$k=2$ では大小関係が途中で入れ替わる2方向を直接数える。片方の向きは4つの整数の狭義増加列へ写せる。(2)は上下交換の対合、(3)は10個の非減少列から交差する組を列挙する。

(1)
$k=2$ で条件(iii)が成り立つ一方の向きは$$a_1<b_1\leqq b_2<a_2$$である。ここで$$(a_1,b_1,b_2+1,a_2+1)$$は $1,2,\dots ,n+1$ から選んだ4個の狭義増加列になる。逆の対応も成り立つから、この向きの表は$${}_{n+1}{\mathrm{C}}_4$$個である。

もう一方の向き $a_1>b_1,a_2<b_2$ も同数なので$$A_{n,2}=2{}_{n+1}{\mathrm{C}}_4=\frac{n(n-1)(n-2)(n+1)}{12}\mathrm{.}$$(2)
条件を満たす表の上下段を交換する。この操作を2回行えば元に戻る。一方、交換しても変わらない表なら $a_i=b_i$ がすべての $i$ で成り立ち、条件(iii)に反する。したがって固定点のない2個組ができるので $A_{n,k}$ は偶数である。

(3)
$1,2,3$ から作る長さ3の非減少列は10個である。最初に上段が小さく、後で大きくなる組は$$\begin{array}{cccccc}(a_1{a}_2{a}_3)& 113& 113& 123& 133& 133\\ (b_1{b}_2{b}_3)& 122& 222& 222& 222& 223\end{array}$$の5組である。上下を交換した5組も条件を満たすから$$A_{3,3}=2\cdot 5=10.$$