組合せの問題で使われるCについて素朴な疑問があります。

nCr=n!/r!(n-r)!
は何故整数になるのでしょうか？

組合せを考えてるから当たり前といえばそうですが、毎度計算のときに分母分子が綺麗にキャンセルされてとても不思議です。
Cが必ず整数になることは数学的に証明出来るのでしょうか？