二項係数のp指数に関する評価

※ MathJax を使用しています。数式を表示するためには、JavaScript をオンにする必要があります。

実数 $x$ に対し, $x$ を超えない最大の整数を $\lfloor x\rfloor$ で表す.

[補題] 任意の $x$, $y$ に対して, $$ 0\leq \lfloor x + y\rfloor - \lfloor x\rfloor - \lfloor y\rfloor \leq 1 $$ が成り立つ.

[証明] $\delta=x-\lfloor x\rfloor$, $\delta'=y-\lfloor y\rfloor$ とおくと, \begin{align*} \lfloor x + y\rfloor &= \bigl\lfloor\lfloor x\rfloor +\delta + \lfloor y\rfloor + \delta'\bigr\rfloor \\ &= \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \delta+\delta' \rfloor. \end{align*} 移項すると, $$ \lfloor x + y\rfloor - \lfloor x\rfloor - \lfloor y\rfloor = \lfloor \delta+\delta' \rfloor. $$ 一方, $0\leq \delta < 1$, $0\leq \delta' < 1$ であるから, $$ 0\leq \delta + \delta' < 2. $$ ゆえに, $$ 0\leq \lfloor \delta+\delta' \rfloor \leq 1. $$ これより, 求める不等式が得られる.

[定理] 二項係数 $\displaystyle\binom{n}{k}$ の $p$ 指数について, \begin{align*} \mathrm{ord}_{p}\left( \binom{n}{k} \right) &= \sum_{i=1}^{\lfloor \log_{p}n\rfloor}\left( \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \right) \\ & = \sum_{i=1}^{\infty}\left( \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \right) \end{align*} が成り立つ.

[証明] $a=\lfloor \log_{p}n\rfloor$ とおくと, $a \leq \log_{p}n < a+1$ であるから, $$ p^{a}\leq n< p^{a+1}. $$ また, $a+1\leq i$ を満たす全ての整数 $i$ に対して, $$ \left\lfloor\frac{n}{p^{i}}\right\rfloor = \left\lfloor\frac{k}{p^{i}}\right\rfloor = \left\lfloor\frac{n-k}{p^{i}}\right\rfloor = 0. $$ したがって, \begin{align*} \mathrm{ord}_{p}\left( \binom{n}{k} \right) &= \mathrm{ord}_{p}\left( \frac{n!}{k!(n-k)!} \right) \\ &= \mathrm{ord}_{p}(n!) - \mathrm{ord}_{p}(k!) - \mathrm{ord}_{p}((n-k)!) \\ &= \sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^{i}}\right\rfloor - \sum_{i=1}^{\infty}\left\lfloor\frac{k}{p^{i}}\right\rfloor - \sum_{i=1}^{\infty}\left\lfloor\frac{n-k}{p^{i}}\right\rfloor \\ &= \sum_{i=1}^{a}\left\lfloor\frac{n}{p^{i}}\right\rfloor - \sum_{i=1}^{a}\left\lfloor\frac{k}{p^{i}}\right\rfloor - \sum_{i=1}^{a}\left\lfloor\frac{n-k}{p^{i}}\right\rfloor \\ &= \sum_{i=1}^{a}\left( \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \right) \\ &= \sum_{i=1}^{\infty}\left( \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \right) \end{align*} となる. (証明終)

[定理] 二項係数 $\displaystyle\binom{n}{k}$ の $p$ 指数 $\displaystyle e= \mathrm{ord}_{p}\left( \binom{n}{k} \right)$ について, 不等式 $p^{e} \leq n$ が成り立つ.

[証明] $a=\lfloor \log_{p}n\rfloor$ とおくと, 前定理より, $$ e = \sum_{i=1}^{a}\left( \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \right). $$ 各 $i$ について, $n/p^{i}=k/p^{i}+(n-k)/p^{i}$ であるから, 上の補題より, $$ 0\leq \left\lfloor\frac{n}{p^{i}}\right\rfloor - \left\lfloor\frac{k}{p^{i}}\right\rfloor - \left\lfloor\frac{n-k}{p^{i}}\right\rfloor \leq 1. $$ ゆえに, $$ e \leq \sum_{i=1}^{a} 1 = a \leq \log_{p}n. $$ したがって, $p^{e} \leq n$ となる. (証明終)

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示