KAIST POW 2019-02 Simplification of an expression with factorials

문제 링크

2019-02 Simplification of an expression with factorials - KAIST Math Problem of the Week

POW라는 걸 믿을 수 없을 정도로 쉬운 문제가 나와버렸다. 스포방지 안할래...

---

문제. 모든 자연수 \(n,m\)에 대해, 다음이 정수임을 보여라.

$$ C_{n,m} = \frac{(nm)!}{(m!)^{n}n!} $$

 

Sol 1.

 

\(C_{n,m}\)은 \(nm\)개의 수를 구분이 가지 않는 \(n\)개의 group으로 나누는 경우의 수이므로 당연히 정수이다.

 

Sol 2.

 

\(\displaystyle n!C_{n,m} = \begin{pmatrix} m \\ m \end{pmatrix} \begin{pmatrix} 2m \\ m \end{pmatrix} \cdots \begin{pmatrix} nm \\ m \end{pmatrix}\)이다.

\(\begin{pmatrix} km \\ m \end{pmatrix} = \frac{km}{m} \begin{pmatrix} km-1 \\ m-1 \end{pmatrix} \equiv 0 (\text{mod } k)\)이므로 주어진 식의 우변은 \(n!\)의 배수이다.