$n$ は自然数、$x_1, x_2, \dots, x_{2n}$ は 0 以上の整数とする。以下の式(1)～(3)について考える。 (1) $\sum_{k=1}^{n} x_k \leq n$ (2) $\sum_{k=1}^{n+1} x_k \geq n+1$ (3) $\sum_{k=n+1}^{2n} x_k = 2n$ (1) $\sum_{k=1}^{n} x_k = m$ ($m$ は 0 以上 $n$ 以下の整数) のとき、(2)かつ(3)を満たす 0 以上の整数の組 $(x_{n+1}, x_{n+2}, \dots, x_{2n})$ の個数を $m, n$ で表せ。 (2) $1$ 以上 $n$ 以下の整数 $m$ に対して、${}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1}$ を示せ。 (3) (1) かつ (2) かつ (3) を満たす 0 以上の整数の組 $(x_1, x_2, \dots, x_{2n})$ の個数を $n$ で表せ。

1. 問題の内容

$n$ は自然数、$x_1, x_2, \dots, x_{2n}$ は 0 以上の整数とする。以下の式(1)～(3)について考える。

(1) $\sum_{k=1}^{n} x_k \leq n$

(2) $\sum_{k=1}^{n+1} x_k \geq n+1$

(3) $\sum_{k=n+1}^{2n} x_k = 2n$

(1) $\sum_{k=1}^{n} x_k = m$ ($m$ は 0 以上 $n$ 以下の整数) のとき、(2)かつ(3)を満たす 0 以上の整数の組 $(x_{n+1}, x_{n+2}, \dots, x_{2n})$ の個数を $m, n$ で表せ。

(2) $1$ 以上 $n$ 以下の整数 $m$ に対して、${}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1}$ を示せ。

(3) (1) かつ (2) かつ (3) を満たす 0 以上の整数の組 $(x_1, x_2, \dots, x_{2n})$ の個数を $n$ で表せ。

2. 解き方の手順

(1) 条件より、

$\sum_{k=1}^{n} x_k = m$

$\sum_{k=n+1}^{2n} x_k = 2n$

よって、$x_{n+1} + \dots + x_{2n} = 2n$ である。

また、$\sum_{k=1}^{n+1} x_k \geq n+1$ であるから、$x_1 + x_2 + \dots + x_n + x_{n+1} \geq n+1$ である。

$\sum_{k=1}^{n} x_k = m$ より、$m + x_{n+1} \geq n+1$, つまり、$x_{n+1} \geq n+1-m$ である。

$x_{n+1} = y + n+1-m$ ($y \geq 0$) とおくと、

$x_{n+1} + x_{n+2} + \dots + x_{2n} = y + n+1-m + x_{n+2} + \dots + x_{2n} = 2n$

$y + x_{n+2} + \dots + x_{2n} = m+n-1$

$x_{n+2}, \dots, x_{2n} \geq 0$ である。

これは、$n$ 個の変数 ($y, x_{n+2}, \dots, x_{2n}$) の和が $m+n-1$ になる場合の数を求める問題である。

したがって、求める個数は ${}_{(m+n-1) + (n-1)}C_{n-1} = {}_{m+2n-2}C_{n-1}$ である。

(2) ${}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1}$

$= \frac{(2n+m-1)!}{(2n-1)!m!} - \frac{(2n+m-2)!}{(2n-1)!(m-1)!}$

$= \frac{(2n+m-1)! - m(2n+m-2)!}{(2n-1)!m!}$

$= \frac{(2n+m-2)!(2n+m-1 - m)}{(2n-1)!m!}$

$= \frac{(2n+m-2)!(2n-1)}{(2n-1)!m!}$

$= \frac{(2n+m-2)!}{(2n-2)!m!} = {}_{2n+m-2}C_{2n-2}$

(3) (1)より $\sum_{k=1}^{n} x_k \leq n$ なので、$m = \sum_{k=1}^{n} x_k$ とおくと、$0 \leq m \leq n$ である。

また、(1)より $x_{n+1} + \dots + x_{2n} = 2n$ である。

$x_1, \dots, x_n$ を固定したとき、条件(2)(3)を満たす $x_{n+1}, \dots, x_{2n}$ の個数は、(1)の結果より ${}_{m+2n-2}C_{n-1}$ である。

求める個数は、$\sum_{m=0}^{n} {}_{m+2n-2}C_{n-1} \times$ (与えられた$m$に対する、$x_1+\dots + x_n = m$の組み合わせ数)

ここで、$x_1 + x_2 + \dots + x_n = m$ を満たす 0 以上の整数の組 $(x_1, x_2, \dots, x_n)$ の個数は ${}_{m+n-1}C_{n-1}$ である。

よって、求める個数は $\sum_{m=0}^{n} {}_{m+2n-2}C_{n-1} \times {}_{m+n-1}C_{n-1}$ である。

ここで、条件(1)より$\sum_{k=1}^{n} x_k \leq n$ である。

$x_1 + \dots + x_n + y = n$ ($y \geq 0$) とおくと、$x_1, \dots, x_n, y \geq 0$ を満たす整数解の個数は ${}_{(n+1)+n-1}C_{n} = {}_{2n}C_{n}$ である。

$\sum_{k=n+1}^{2n} x_k = 2n$ を満たす 0 以上の整数の組 $(x_{n+1}, \dots, x_{2n})$ の個数は ${}_{2n+(n-1)}C_{n-1} = {}_{3n-1}C_{n-1}$ である。

(1)と(2)と(3)を同時に満たす組の個数は、

$\sum_{k=1}^{2n} x_k = \sum_{k=1}^{n} x_k + \sum_{k=n+1}^{2n} x_k$ であり、

$x_1+\dots+x_n \le n$ かつ $x_1+\dots+x_{n+1} \ge n+1$ かつ $x_{n+1}+\dots+x_{2n}=2n$ を満たすような $(x_1, \dots, x_{2n})$ を数えれば良い。

$\sum_{k=n+1}^{2n} x_k = 2n$ より、$x_{n+1}, \dots, x_{2n}$ の組の個数は ${}_{(2n)+(n-1)}C_{n-1} = {}_{3n-1}C_{n-1}$ 個存在する。

また、$0 \le \sum_{k=1}^{n} x_k = m \le n$ より、$x_1 + \dots + x_n \le n$を満たす$x_1, \dots, x_n$ の組の個数は${}_{2n}C_{n}$ である。

3. 最終的な答え

(1) ${}_{m+2n-2}C_{n-1}$

(2) ${}_{2n+m-2}C_{2n-2} = {}_{2n+m-1}C_{2n-1} - {}_{2n+m-2}C_{2n-1}$ (証明済み)

(3) $\sum_{m=0}^{n} {}_{m+2n-2}C_{n-1} {}_{m+n-1}C_{n-1}$

または、

${}_{2n}C_{n} {}_{3n-1}C_{n-1}$