$n$ は自然数、$x_1, x_2, \dots, x_{2n}$ は 0 以上の整数とする。以下の3つの式を考える。 (1) $\sum_{k=1}^n x_k \le n$ (2) $\sum_{k=1}^{n+1} x_k \ge 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 以上の整数とする。以下の3つの式を考える。

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

(2) $\sum_{k=1}^{n+1} x_k \ge 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$ のとき、(2) と (3) を満たす $(x_{n+1}, x_{n+2}, \dots, x_{2n})$ の個数を求める。

まず、(3) より $\sum_{k=n+1}^{2n} x_k = 2n$ である。

(2) より $\sum_{k=1}^{n+1} x_k \ge n+1$ であるから、$\sum_{k=1}^n x_k + x_{n+1} \ge n+1$ となる。

$\sum_{k=1}^n x_k = m$ であるから、$m + x_{n+1} \ge n+1$ となり、$x_{n+1} \ge n+1 - m$ である。

ここで、$x_{n+1}' = x_{n+1} - (n+1-m)$ とおくと、$x_{n+1}' \ge 0$ となる。

$\sum_{k=n+1}^{2n} x_k = 2n$ を満たす $(x_{n+1}, \dots, x_{2n})$ の個数は、

$x_{n+1} + x_{n+2} + \dots + x_{2n} = 2n$ を満たす 0 以上の整数の組の個数である。

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

$x_{n+1}', x_{n+2}, \dots, x_{2n}$ は 0 以上の整数であるから、求める個数は $_{n-1+m+(n-1)}C_{n-1} = _{2n+m-2}C_{n-1}$ である。

(2) $_{2n+m-2}C_{2n-2} = _{2n+m-1}C_{2n-1} - _{2n+m-2}C_{2n-1}$ を示す。

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

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

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

$_{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)(2n+m-2)! - m(2n+m-2)!}{(2n-1)!m!} = \frac{(2n+m-1-m)(2n+m-2)!}{(2n-1)!m!} = \frac{(2n-1)(2n+m-2)!}{(2n-1)!m!} = \frac{(2n+m-2)!}{(2n-2)!m!} = _{2n+m-2}C_{2n-2}$

(3) (1) かつ (2) かつ (3) を満たす $(x_1, x_2, \dots, x_{2n})$ の個数を求める。

$\sum_{k=1}^n x_k \le n$ であるから、$\sum_{k=1}^n x_k = m$ とすると、$m = 0, 1, \dots, n$ である。

$\sum_{k=1}^n x_k = m$ を満たす $(x_1, x_2, \dots, x_n)$ の個数は $_{m+n-1}C_{n-1}$ にはならない. $\sum_{k=1}^n x_k=m$　を満たす非負整数の組　$\{x_1,...,x_n\}$ の個数は $_{m+n-1}C_{n-1}$ であり、$\sum_{k=1}^n x_k \leq n$　を満たす非負整数の組の個数は$\sum_{m=0}^n {}_{m+n-1}C_{n-1}$

(1) で求めた個数は $_{2n+m-2}C_{n-1}$である。

$\sum_{k=1}^n x_k = m$ となる $m$ を導入して、$\sum_{m=0}^n$ で個数を合計する。

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

したがって、求める個数は $\sum_{m=0}^n {}_{m+n-1}C_{n-1} \cdot {}_{2n+m-2}C_{n-1}$

(3) $\sum_{i=1}^{n} x_i \le n$, $\sum_{i=1}^{n+1} x_i \ge n+1$, $\sum_{i=n+1}^{2n} x_i = 2n$ を満たす $x_1, \dots, x_{2n}$ の個数。

$x_1, \dots, x_n$ は 0 以上の整数であるから、$\sum_{i=1}^{n} x_i = s$ ($0 \le s \le n$) となる。これを満たす組 $(x_1, \dots, x_n)$ の個数は $_{s+n-1}C_{n-1}$ である。

ここで、$x_{n+1} + \dots + x_{2n} = 2n$ となる。

さらに、$x_1 + \dots + x_n + x_{n+1} \ge n+1$ であるから、$s + x_{n+1} \ge n+1$ である。

$x_{n+1} \ge n+1 - s$ である。$x_{n+1}' = x_{n+1} - (n+1-s)$ とすると、$x_{n+1}' \ge 0$ となる。

したがって、$x_{n+1}' + (n+1-s) + x_{n+2} + \dots + x_{2n} = 2n$ であるから、$x_{n+1}' + x_{n+2} + \dots + x_{2n} = 2n - (n+1-s) = n-1+s$ である。

これを満たす組 $(x_{n+1}', x_{n+2}, \dots, x_{2n})$ の個数は $_{n-1+s+(n-1)}C_{n-1} = _{2n+s-2}C_{n-1}$ である。

$\sum_{s=0}^n {}_{s+n-1}C_{n-1} \cdot {}_{2n+s-2}C_{n-1}$

3. 最終的な答え

(1) $_{2n+m-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_{s=0}^n {}_{s+n-1}C_{n-1} \cdot {}_{2n+s-2}C_{n-1}$