---
tags: 数学, 整数問題
---
今年の整数問題（2018/01/10）
==================

## 問題

整数 $n\ (\ge 1)$ に対して、$1 \le a_0 < a_1 < \dots < a_n \le 2n$ かつ $\sum_i a_i$ が $n$ の倍数となる整数の組 $(a_0, a_1, \dots , a_n)$ は何通りあるか、$n$ の式で表せ。その式を $C_n$ とおくと今日(2018/01/10)は私の $C_5$ 歳の誕生日です。

## 解答

$$
\begin{eqnarray*}
C_n &=& \frac{1}{n} \binom{2n}{n+1} \\
&=& \frac{(2n)!}{(n+1)!n!} \\
&=& \frac{1}{n+1} \binom{2n}{n} \\
&=& \binom{2n}{n} - \binom{2n}{n-1} \ \ ({\rm for}\ n \ge 1)\\
\end{eqnarray*}
$$

（つまり $C_n$ は[カタラン数](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0)（ただし $n \ge 1$））

### 解説（証明概要）

まずは $n = 1$ の場合を考える。
$1 \le a_0 < a_1 \le 2$ を満たす $(a_0, a_1)$ は $(1, 2)$ のみで、$1 + 2 = 3$ は明らかに 1 の倍数なので、$C_1 = 1$ である。

次に $n = 2$ の場合を考える。
$1 \le a_0 < a_1 < a_2 \le 4$ を満たす $(a_0, a_1, a_2)$ で $a_0 + a_1 + a_2 \equiv 0\ ({\rm mod}\ 2)$ を満たすのは、$(1, 2, 3), (1, 3, 4)$ の2通りとなり、$C_2 = 2$ である。
ここで、$1 \le a_0 < a_1 < a_2 \le 4$ を満たす $(a_0, a_1, a_2)$ の組に着目すると、$(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)$ の4通りであり、もう1つの条件 $a_0 + a_1 + a_2 \equiv 0\ ({\rm mod}\ 2)$ を満たすのがそのうちの半分（残りの半分は $a_0 + a_1 + a_2 \equiv 1\ ({\rm mod}\ 2)$ である）ということが分かる。

一般に $1 \le a_0 < a_1 < \dots < a_n \le 2n$ を満たす整数の組 $(a_0, a_1, \dots , a_n)$ の総数は、$2n$ 個の中から $n+1$ 個を取り出す **組合せ** の総数であり、よって $\binom{2n}{n+1} = \frac{(2n)!}{(n+1)!(n-1)!}$ 通りある。
これから、そのうち $\sum_i a_i \equiv 0 ({\rm mod}\ n)$ を満たす組合せはそのちょうど $1/n$、すなわち $\frac{1}{n}\binom{2n}{n+1}$ 通りであることを示す。

ここで $b_i := a_i - i - 1 \ (i = 0,\dots,n)$ を考える。$a_i$ の条件から、以下のことが言える。

$$
\begin{eqnarray}
0 \le b_0 \le b_1 \le \dots \le b_n \le n-1 \\
\sum_{i=0}^n b_i = \sum_{i=0}^n a_i - \frac{(n+1)(n+2)}{2}
\end{eqnarray}
$$

さらに、$(b_0,b_1,\dots,b_n)$ は $0$〜$(n-1)$ の $n$個から重複を許して $n+1$ 個を取り出す **重複組合せ** をすべて網羅しており、$(a_0,a_1,\dots,a_n)$ が決まればそれに1対1に対応する（$\because$略）。

今、ある整数 $k \ (1 \le k \le n)$ を考えて、整数の組 $(b^\prime_0,b^\prime_1,\dots,b^\prime_n)$ を以下のように決める。

+ 各 $b_i$ に $k$ を足し $n$ で割った余りを考える
+ それを並べ替えて $b^\prime_0 \le b^\prime_1 \le \dots \le b^\prime_n$ となるように割り当てる

すると $(b^\prime_0,b^\prime_1,\dots,b^\prime_n)$ も $0$〜$(n-1)$ の $n$個から $n+1$ 個を取り出す重複組合せであり、$k=1,\dots,n-1$ でそれぞれ異なる組合せとなる（$k=n$の場合は元の$(b_0,b_1,\dots,b_n)$に一致する）。
またその作り方から、以下が言える。

$$
\begin{eqnarray*}
\sum_{i=0}^n b^\prime_i &\equiv& \sum_{i=0}^n b_i + (n+1)k \pmod{n}\\
&\equiv& \sum_{i=0}^n b_i + k \pmod{n}
\end{eqnarray*}
$$

すなわち、$k=1,\dots,n-1$ と走査することで、元の $(b_0,b_1,\dots,b_n)$ と、その総和を$n$で割った余りが異なる $n-1$ 種類の重複組合せを作ることができる。元の組合せも含めると、総和を $n$ で割った余りが $0$〜$n-1$ のちょうど $n$ 種類が作れることになる。

> 例：$n=3$、$(b_0, b_1, b_2, b_3) = (0, 0, 1, 2)$ とすると、
> + $k=1 \Rightarrow (b^\prime_0, b^\prime_1, b^\prime_2, b^\prime_3) = (0, 1, 1, 2), \sum_i b^\prime_i \equiv 1 \pmod{3}$
> + $k=2 \Rightarrow (b^\prime_0, b^\prime_1, b^\prime_2, b^\prime_3) = (0, 1, 2, 2), \sum_i b^\prime_i \equiv 2 \pmod{3}$
> + $k=3 \Rightarrow (b^\prime_0, b^\prime_1, b^\prime_2, b^\prime_3) = (0, 0, 1, 2)\ (= (b_0, b_1, b_2, b_3)), \sum_i b^\prime_i \equiv 0 \pmod{3}$

このことから次のことが言える。

+ $\sum_i b_i \equiv k \pmod{n}$（$k = 0,1,\dots,n-1$）となる $(b_0,b_1,\dots,b_n)$ は、ちょうど （重複組合せの総数）/$n$ 個（ずつ）存在する

（$n$個から $n+1$個を取り出す）重複組合せの総数は（$2n$個から $n+1$個を取り出す）組合せの総数に一致し、$(b_0,b_1,\dots,b_n)$ は1対1に対応する $(a_0,a_1,\dots,a_n)$ が存在し、$\sum_i a_i$ は $\sum_i b_i$ に（$(b_0,\dots,b_n)$の選び方に依らず$n$のみに依る）定数を加算した値になるので、以下の結論に達する。

+ $k = 0, \dots, n-1$ に対して、$\sum_i a_i \equiv k \pmod{n}$ となる $(a_0,a_1,\dots,a_n)$ は、$\frac{1}{n}\binom{2n}{n+1}$ 個（ずつ）存在する
+ 特に $\sum_i a_i \equiv 0 \pmod{n}$ となる $(a_0,a_1,\dots,a_n)$ は、$\frac{1}{n}\binom{2n}{n+1}$ 個存在する

（証明終わり）