素数 p で割り切れない二項係数の個数 - 球面倶楽部零八式 mark II

${}_nC_{r}(r=0,\ldots,n)$ のうち、素数 $p$ で割り切れないものの個数は、 $n$ を $p$ 進数で表示したときの各桁を $a_0\cdots a_k$ としたとき、 $(a_0+1)\times\cdots \times(a_k+1)$ となる。

例えば、 ${}_{100}C_{r}(r=0,\ldots,100)$ のうち、素数 $7$ で割り切れないものの個数は、 $100_{(10)}=202_{(7)}$ であるから，9個であることがわかる。もちろん、その9個は $r=0,1,2,49,50,51,98,99,100$ である。これぐらいは暗算でできる。

暗算というのは、 ${}_{100}C_{r}(r=0,\ldots,100)$ が暗算でできる、ということではなく、それが7で割りきれない $r$ は暗算で求められるということ。まぁ、当然か。

練習: ${}_{1000}C_{r}(r=0,\ldots,1000)$ が $13$ で割り切れる $r$ の個数を求めよ。また、 $r$ の最大値を求めよ。

答:13進数の表記には、16進数の文字を用いるものとする。

割り切れないものの個数は $1000_{(10)}=5BC_{(13)}$ だから、 $6\times C\times D_{(13)}=6\times12\times13_{(10)}=936_{(10)}$ 個だから、割り切れるものの個数は $1001-936=65$ 個、 $r$ の最小値は $D_{(13)}=13_{(10)}$ だから、二項係数の対称性により、最大値は $1000-13=987$ となる。