Discrete Math

If p is prime,then a^{p-1}\equiv1\ mod\ p

False, 要gcd(a,p)=1

If a^{p-1}\equiv1\ mod\ p, then p is prime

False

The meaning of Stirling Number of the second kind?

相異物放進相同箱且沒有一箱是空的

The meaing of Onto Function

相異物放進相異箱中

N相異物放進K相異箱中(可以有空)

(S(m,1)+S(m,2)+…+S(m,k))

Dearrangement?

All pumutations that number k is not in posistion k. For S={1,2,3}=> A = 312 is a dearrangement

無限等比級數

\frac{a_1}{1-r}

有限等比級數

\frac{a_1(1-r^n)}{1-r}

1+2x+3x^2+…=\sum_{k=0}^\infty{(k+1)*x^k}

\frac{1}{(1-x)^2}

1+4x+9x^2+…=\sum_{k=0}^\infty{k^2x^k}

\frac{(1+x)}{(1-x)^3}

1+x+x^2+…=\sum_{k=0}^\infty{x^k}

\frac{1}{1-x}

Catalan Number=? and the meaning?

C_n=\frac{1}{n+1}\binom{2n}{n} 在一串乘法中有多少方法可以結合裡面的元素/有n個node的BST數量

Solution for Fibonacci \lambda^2-\lambda-1=0

\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)

Definition of Simple Graph

A graph with no Loop and 重邊

The number of vertices that have odd degree is ?

Even

Induction Subgraph

For a subgraph G^{'}(V^{'},E^{'})\in G(V,E) 中E^{'}要包含所有在原圖G中V^{'}所連的邊

Clique

一個頂點的子集，其誘導子圖為完全圖

Forest Therom

A graph without cycle has |E| \leq |V|-1

The number of regions in a planar graph(Euler's Formula)

v-e+r=2 or 有k個分量則v-e+r=1+k

k-regular graph?

A graph with all deg(v)=k

A connected planar graph with v >=3 has e=?

e \leq 3v-6

Equivalence Relation

Reflexive Symmetric Transitive

Equivalent Class

A set of elements that have relation with certain element in an Equivalent Relation. 如R={(1,1),(2,2),(3,3),(1,2),(2,1)}則Equivalent Class [1] = {1,2}

Partial Ordering

Reflexive Anti-Symmetric Transitive

S(m,n)=?

S(m-1,n-1)+n*S(m-1,n)

\binom{r-1}{k}+\binom{r-1}{k-1}=?

\binom{r}{k}

\sum_{k=0}^n\binom{r+k}{k}=\binom{r}{0}+\binom{r+1}{1}+…+\binom{r+n}{n}=?

\binom{r+n+1}{n}

\sum_{i=0}^n\binom{i}{k}=\binom{0}{k}+\binom{1}{k}+…+\binom{n}{k}=?

\binom{n+1}{k+1}

D_n=?

(n-1)(D_{n-1}+D_{n-2})\ where\ D_1=0,D_2=1

Onto(m,n)=?

n!*S(m,n)=\sum_{i=0}^n{(-1)^n*\binom{n}{i}*(n-i)^m}