水泥數學筆記

書藉網站:http://www-cs-faculty.stanford.edu/~uno/gkp.html

Ch 1. Recurrence

Ch 2. Sums

Ch 3. Integer Functions

符號
x 小於等於x的最大整數
x 大於等於x的最小整數
x=xx x的分數部份
[α..β] 即[]區間

Ch 4. numbery theory

  • 在本章中p表示質數

質數:只有二個因數(1和它自己)的數
合成數:有三個以上因數的數

  • 1不是質數
  • 所有大於1的數不是質數就是合成數
  • 第n個質數Pnnlnn

prime number theorem
小於x的質數個數 π(x)xlnx

算數基本定理 (Fundamental Theorem of Arithmetic)
若x為整數且x > 1,則x的因式分解唯一

Ch 5. Binomial Coefficients, Hypergeometric Functions

(r0)=1,(r1)=r,(r2)=r(r1)2

p.156 symmetry identidy
(nk)=(nnk)

p.157 absorption identidy
(rk)=rk(r1k1)=>k(rk)=r(r1k1)=>(rk)(rk)=r(r1k)

p.158 addtion formula
(rk)=(r1k)+(r1k1)(rk)(rk)+k(rk)=r(r1k)+r(r1k1)

p.160 summation on the upper index
0kn(km)=(0m)+(1m)++(nm)=(n+1m+1)

p.161
kn(m+kk)=(m+n+1m+1)=(m+n+1n)

p.164 negating the upper index (或upper negation)
(rk)=(1)k(kr1k)

p.165
(1)m(n1m)=(1)n(m1n)km(rk)(1)k=(r0)(r1)++(1)m(rm)=(1)m(r1m)

Ch 6. Special Numbers

Ch 7. Generating Functions

Ch 8. Discrete Probability

Ch 9. Asmptotics

Ch 10. Mathematical Analysis of Fundamental Algorithms