Lucas定理推导过程(全网最全,哈哈哈哈)
和大家一起學習Lucas定理,在網上找了好久都沒有找到詳細的推導過程,這大概就是傳說中的的一血了吧
求證 C n m = C n / p m / p ? C n % p m % p ( m o d ( p ) ) C_n^m = C_{n/p}^{m/p} * C_{n\%p}^{m\%p}\quad\quad\quad(mod(p)) Cnm?=Cn/pm/p??Cn%pm%p?(mod(p))
p為素數
(mod( p ))是兩邊同時取余p的意思
證明:
已知p為素數,將非負整數a轉化成p-進制數:
a = a k p k + a k ? 1 p k ? 1 + a k ? 1 p k ? 2 + . . . . + a 1 ? k + a 0 a=a_kp^k+a_{k-1}p^{k-1}+a_{k-1}p^{k-2}+....+a_1*k+a_0 a=ak?pk+ak?1?pk?1+ak?1?pk?2+....+a1??k+a0?
由于p是素數對于 1 ≤ j ≤ p ? 1 , 1\le j\le p-1, 1≤j≤p?1,都有 C p j = p j ? C p ? 1 j ? 1 ≡ 0 m o d ( p ) C_p^j=\frac{p}{j}*C_{p-1}^{j-1} \equiv0 \quad \quad mod(p) Cpj?=jp??Cp?1j?1?≡0mod(p)
于 是 知 ( 1 + x ) p = 1 + C p 1 x + C p 2 x ? 1 + C p 3 + . . . . + C p p ? 1 x p ? 1 + C p p x p = 1 + ∑ i = 1 p ? 1 C p j + x p ≡ 1 + x p m o d ( p ) 于是知(1+x)^p=1+C_p^1x+C_{p}^2{x-1}+C_p^3+....+C_p^{p-1}x^{p-1}+C_p^px^p=1+\sum_{i=1}^{p-1}C_p^j+x^p\equiv1+x^p \quad\quad\quad mod(p) 于是知(1+x)p=1+Cp1?x+Cp2?x?1+Cp3?+....+Cpp?1?xp?1+Cpp?xp=1+∑i=1p?1?Cpj?+xp≡1+xpmod(p)
( 1 + x ) p ≡ 1 + x p m o d ( p ) ① (1+x)^p\equiv1+x^p \quad\quad\quad mod(p)\quad\quad\quad ① (1+x)p≡1+xpmod(p)①
設 n = s p + q , m = t p + r n=sp+q , m=tp+r n=sp+q,m=tp+r
即 s = n / p q = n % p t = m / p r = m % p 即s=n/p\quad\quad\quad q=n\%p\quad\quad\quad t=m/p\quad\quad\quad r=m\%p 即s=n/pq=n%pt=m/pr=m%p
( 1 + x ) n = ( 1 + x ) s p + q = ( 1 + x ) s p ? ( 1 + x ) p = ( ( 1 + x ) p ) s ? ( 1 + x ) q (1+x)^n=(1+x)^{sp+q}=(1+x)^{sp}*(1+x)^p=\biggr((1+x)^p\biggr)^s*(1+x)^q (1+x)n=(1+x)sp+q=(1+x)sp?(1+x)p=((1+x)p)s?(1+x)q
代入公式①得:
( 1 + x ) n = ( 1 + x p ) s ? ( 1 + x ) q m o d ( p ) (1+x)^n=(1+x^p)^s*(1+x)^q\quad\quad\quad mod(p) (1+x)n=(1+xp)s?(1+x)qmod(p)
對 ( 1 + x p ) s (1+x^p)^s (1+xp)s和 ( 1 + x p ) s ? ( 1 + x ) q (1+x^p)^s*(1+x)^q (1+xp)s?(1+x)q分別進行二項式展開得
( 1 + x p ) s ? ( 1 + x ) q = ∑ i = 0 s ( s i ) ? x i ? p ? ∑ i = 0 q ( q j ) ? x j m o d ( p ) (1+x^p)^s*(1+x)^q=\sum_{i=0}^s\binom{s}{i}*x^{i*p}*\sum_{i=0}^q\binom{q}{j}*x^j\quad\quad\quad mod(p) (1+xp)s?(1+x)q=∑i=0s?(is?)?xi?p?∑i=0q?(jq?)?xjmod(p)
即 ( 1 + x ) n = ∑ i = 0 s ( s i ) ? x i ? p ? ∑ i = 0 q ( q j ) ? x j m o d ( p ) ② 即(1+x)^n=\sum_{i=0}^s\binom{s}{i}*x^{i*p}*\sum_{i=0}^q\binom{q}{j}*x^j\quad\quad\quad mod(p)\quad\quad\quad ② 即(1+x)n=i=0∑s?(is?)?xi?p?i=0∑q?(jq?)?xjmod(p)②
對 ( 1 + x ) n (1+x)^n (1+x)n進行二項式展開得:
( 1 + x ) n = ∑ i = 0 s p + q ( s p + q k ) ? x k ③ (1+x)^n=\sum_{i=0}^{sp+q}\binom{sp+q}{k}*x^k\quad\quad\quad ③ (1+x)n=i=0∑sp+q?(ksp+q?)?xk③
首先求③中 x t p + r x^{tp+r} xtp+r的系數為 ( s p + q t p + r ) \binom{sp+q}{tp+r} (tp+rsp+q?)
然后求②中 x t p + r x^{tp+r} xtp+r,我們發現,當且僅當i = t , j = r ,能夠得到 x t p + r x^{tp+r} xtp+r的系數,即為 ( s t ) ( q r ) \binom{s}{t}\binom{q}{r} (ts?)(rq?)
即 ( s p + q t p + r ) = ( s t ) ( q r ) ( m o d ( p ) ) 即\binom{sp+q}{tp+r}=\binom{s}{t}\binom{q}{r}\quad\quad\quad(mod(p)) 即(tp+rsp+q?)=(ts?)(rq?)(mod(p))
即 ( n m ) = ( n / p m / p ) ( n % p m % p ) ( m o d ( p ) ) 即\binom{n}{m}=\binom{n/p}{m/p}\binom{n\%p}{m\%p}\quad\quad\quad(mod(p)) 即(mn?)=(m/pn/p?)(m%pn%p?)(mod(p))
即 C n m = C n / p m / p ? C n % p m % p ( m o d ( p ) ) 即C_n^m = C_{n/p}^{m/p} * C_{n\%p}^{m\%p}\quad\quad\quad(mod(p)) 即Cnm?=Cn/pm/p??Cn%pm%p?(mod(p))
總結
以上是生活随笔為你收集整理的Lucas定理推导过程(全网最全,哈哈哈哈)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： excel版本问题解决方案
- 下一篇： java计算机毕业设计开放式教学评价管理