Discrete Math

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

False, 要gcd(a,p)=1

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+1個元素/有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), S_{(0,0)}=1,S{(n,0)}=0

\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}

For a bipartite graph to have Hamilton Cycle

|V_1|=|V_2|

P(A|B)

\frac{P(A\cap B)}{P(B)}

The least number of colors needed for coloring a planar graph is no longer than 5

True, 所有平面圖都可以用少於4個顏色

廣義二項式定理

\binom{a}{k}=\frac{a(a-1)…(a-k+1)}{k!}

平面圖不包含

K_{33},K_5

指數生成函數

e^{cx}=\sum_{n=0}^\infty(c^n*\frac{x^n}{n!})

Edge/Vertex Connectivity

The minimum number of edges/vertex need to remove to disconnect the graph

Acc=

\frac{TP+FP}{Total}

Precision

\frac{TP}{TP+FP}

Recall

\frac{TP}{TP+FN}

The number of division relation for n=p_1^{e_1}*p_2^{e_2}*…*p_k^{e_k}

\prod_{i=1}^k\frac{(e_i+1)(e_i+2)}{2}

Maximum and Minimum Elements

在hasse graph的最上面/下面的元素 不唯一

Greatest/Least Elements

唯一 且如果有多個maximum/minimum元素就不會有greatest/least elements

Total Order and Well Order

Well Order包含Total Order，兩者都需要關係內任兩個元素皆可比較，而良序集還要每個子集都有最小元素

Lattice

任兩個元素有最小上界和最大下界，全序和良序集一定是lattice，但反過來不一定

Boolean Product for Matrix

取and再取or，即把乘換成and/加換成or

N Z Q R [0,1]

只有R和[0,1]不可數

\frac{1}{(1-x)^n}=(1-x)^{-n}=?

\sum_{k=0}^\infty \binom{n+k-1}{k}x^k

雙分平面圖 邊長性質

e\leq2v-4

\in/\ \subseteq

完全一樣的 / 去掉括號一樣
A = {1,{1}} => 1\in A,\{\{1\}\}\subseteq A

平面圖

K_4/