ルーカスの定理

M をm個の要素を持つ集合とし、i の様々な値に対して長さ p i の m i 個のサイクルに分割します。次に、これら^のサイクル_のそれぞれを別々に回転させることができるため、巡回群C _{p ⁱ}の直積である群GがMに作用します。したがって、この群はサイズnのサブセットNにも作用します。 Gの要素数はpの累乗であるため、その軌道のいずれについても同じことが言えます。したがって、 pを法として計算するには、この群作用の不動点のみを考慮する必要があります。不動点とは、いくつかのサイクルの和集合であるサブセットNのことです。より正確には、 k - i上の帰納法によって、Nにはサイズp ⁱのサイクルが正確にn _i個あることが示されます。したがって、 Nの選択肢の数は正確に です 。 ${\displaystyle {\tbinom {m}{n}}}$${\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}}$

この証明はネイサン・ファインによるものである。^[2]

pが素数でnが1 ≤ n ≤ p − 1の整数である場合、二項係数の分子は

${\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}$

はpで割り切れるが、分母は割り切れない。したがってpはを割り切れる。通常の生成関数では、これは次のことを意味する。 ${\displaystyle {\tbinom {p}{n}}}$

${\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}$

帰納的に、任意の非負整数iに対して、

${\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}$

ここで、 mを非負整数、pを素数とします。mをpを_底として書き、ある非負整数kと0 ≤ mi ≤ p -1を満たす整数m _iに対して、 ${\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}}$

${\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}$

基数pでのnの表現は一意であり、最終積では、n _{i は}基数pでのnの表現におけるi番目の桁です。これはルーカスの定理を証明しています。