東北大学 2019年度後期・文系数学後期第4問解答・解説

問題

$k$ ， $n$ を正の整数とする。整数 $a_{1}, a_{2}, \dots, a_{k}$ と整数 $b_{1}, b_{2}, \dots, b_{k}$ を並べた次のような表を考える。
% 図は省略以下の条件(i)，(ii)，(iii)を同時に満たすようなすべての表の個数を $A_{n, k}$ とする。

(i) $1 ≦ a_{1} ≦ a_{2} ≦ \dots ≦ a_{k} ≦ n$

(ii) $1 ≦ b_{1} ≦ b_{2} ≦ \dots ≦ b_{k} ≦ n$

(iii) $a_{i} < b_{i}$ と $a_{j} > b_{j}$ を満たすような $i$ ， $j$ が存在する。

以下の問いに答えよ。

(1) $A_{n, 2}$ を求めよ。

(2) $A_{n, k}$ が偶数であることを示せ。

(3) $A_{3, 3}$ を求めよ。

出典：東北大学 2019年度後期日程第2次学力試験後期・文系後期第4問

方針

解法1（補集合を包除原理で数える）

条件(iii)は「どこかで $a_{i} < b_{i}$ があり、別のどこかで $a_{j} > b_{j}$ がある」という条件である。補集合は、すべての $i$ で $a_{i} ≦ b_{i}$ となる場合、またはすべての $i$ で $a_{i} ≧ b_{i}$ となる場合である。対称性によりこの2つは同数で、重なりは $a_{i} = b_{i}$ が全ての $i$ で成り立つ場合である。(2)は上下段を入れ替える対応で偶数性を示し、(3)は $n = 3, k = 3$ の非減少列10個を表にして補集合を数える。

解法2（交差する並びを直接数える）

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

解答

解法1（補集合を包除原理で数える）

(1)

まず条件(i),(ii)だけを満たす表を数える。 $k = 2$ では $1 ≦ a_{1} ≦ a_{2} ≦ n$ を満たす組は $_{n + 1} C_{2} = \frac{n ( n + 1 )}{2}$ 個あり、 $b_{1}, b_{2}$ も同じだけある。したがって全体は ${\frac{n ( n + 1 )}{2}}^{2}$ 個である。

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

条件(iii)を満たさない表は、すべて $a_{i} ≦ b_{i}$ であるか、すべて $a_{i} ≧ b_{i}$ である表である。よって包除原理により

A_{n, 2} = {\frac{n ( n + 1 )}{2}}^{2} - 2 \cdot \frac{n ( n + 1 ) ^{2} ( n + 2 )}{12} + \frac{n ( n + 1 )}{2} = \frac{n ( n - 1 ) ( n - 2 ) ( n + 1 )}{12}

である。

(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 (mod 2)$ すなわち $A_{n, k}$ は偶数である。

(3)

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

次に、すべての $i$ で $a_{i} ≦ 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} ≧ b_{i}$ の場合も同じく50個である。両方に含まれるのは $a_{i} = b_{i}$ が全ての $i$ で成り立つ10通りである。

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

解法2（交差する並びを直接数える）

(1)

$k = 2$ で条件(iii)が成り立つ一方の向きは

a_{1} < b_{1} ≦ b_{2} < a_{2}

である。ここで

(a_{1}, b_{1}, b_{2} + 1, a_{2} + 1)

は $1, 2, \dots, n + 1$ から選んだ4個の狭義増加列になる。逆の対応も成り立つから、この向きの表は

_{n + 1} C_{4}

個である。

もう一方の向き $a_{1} > b_{1}, a_{2} < b_{2}$ も同数なので

A_{n, 2} = 2_{n + 1} C_{4} = \frac{n ( n - 1 ) ( n - 2 ) ( n + 1 )}{12} .

(2)

条件を満たす表の上下段を交換する。この操作を2回行えば元に戻る。一方、交換しても変わらない表なら $a_{i} = b_{i}$ がすべての $i$ で成り立ち、条件(iii)に反する。したがって固定点のない2個組ができるので $A_{n, k}$ は偶数である。

(3)

$1, 2, 3$ から作る長さ3の非減少列は10個である。最初に上段が小さく、後で大きくなる組は

(a_{1} a_{2} a_{3}) (b_{1} b_{2} b_{3}) 113122113222123222133222133223

の5組である。上下を交換した5組も条件を満たすから

A_{3, 3} = 2 \cdot 5 = 10.

東北大学 2019年度後期・文系数学 後期 第4問

問題

方針

解法1（補集合を包除原理で数える）

解法2（交差する並びを直接数える）

解答

解法1（補集合を包除原理で数える）

(1)

(2)

(3)

解法2（交差する並びを直接数える）

(1)

(2)

(3)

東北大学 2019年度
後期・文系数学後期第4問