本文分享筆者在計算排列組合(combinatorics)時，發現並描述系統性的窮舉公式 :) 暫時命名為 $\color{red}{\text{All Different Expansion }}$ ??  (有歷史文獻名詞歡迎筆者補充) [情境/動機] 假設箱子裡面有很多種物品，種類集記做 $I$ , 每種物品 $i$ 各有 $\#_i$ 個，向量記做 $\#_{I} := (\#_{i})_{i \in I}$ $$\text{箱子裡共有 } \sum_{i \in I} \#_i  \text{ 個物品}$$    令 $T := \{1,2,3,....|T|\}$，今從箱子裡"逐一"抽取物品共 $|T|$ 次 (抽出 $|T|$ 個物品) ============================================================= $$\color{blue}{\text{形成序列 : } x_{T} := (x_{t})^{|T|}_{t=1} \in I^{|T|}} $$ 註: $x_{t}$ 代表第 $t$ 次抽到的物品 ============================================================= 以下舉個小小的例子，來說明動機~ $I := \{a,b,c,d\}$，$|T| = 4 $，且假設物品個數無上限  $\color{red}{ \forall i \in I \quad \#_{i} = \infty}$ 於是我們可以開始窮舉(brute & force)情況 ~~ $\color{green}{(1)}$  $aaaa$，$bbbb$，$cccc$，$dddd$ 代表全同的情況 $\color{green}{(2)}$  $abcd$，$bcda$，$acbd$，....  代表全異的情況，共 $4!$種 $\color{green}{(3)}$  $abad$，$cbcd$，$bcba$，....  代表二同二異(且$x_{1}=x_{3}$) $\color{green}{(4)...

本文介紹如何推導機率博弈遊戲(Gambling Model)，含集點卡免費遊戲機制，並統整期望值 [預備知識] 需要先了解機率母函數的概念，詳細可先看這篇: http://discoverforgottenmath.blogspot.com/2018/08/expected-ratio-of-n-trials-probability.html 定義新名詞"項值" 代表　${\text{Variable}}^{\text{Value}}$ [基本遊戲] 假設單局，玩$k$ 張卡(物件)，令樣本元/空間為 $\omega \in \Omega_{k}$，回報項值記為 $x^{Gain_k(\omega)}$，付出項值記為 $y^{Paid_k(\omega)}$，而基本遊戲機率母函數可寫為 $$ f_{k}(x,y):= \left(  \sum_{\omega \in \Omega_{k}} p_{\omega} x^{Gain_k(\omega)}y^{Paid_k(\omega)}    \right) $$ 註: 如果每張卡付出值＋回報值皆為獨立則　$$f_k(x,y) =  \left(  \sum_{\omega \in \Omega_{1}} p_{\omega} x^{Gain_1(\omega)}y^{Paid_1(\omega)}    \right)^{k}  $$ [集點機制] 當結束一局遊戲，玩 $k$ 張卡，可以有機率 $p_{b}$ 集一些點數，項值記為 $z^{Bonus(b)}$，集點機率母函數可寫為　$$ g_{k}(z) = \sum_{b \in B_k} p_{b} z^{Bonus(b)}  $$ [兌獎拉霸] 集滿 $\# \in \mathbb{N}$ 點數後，自動立即消費 $\#$點數，產生拉霸遊戲，有 $p_{j}$ 的機率可以直接獲得獎金，項值記為 $x^{\text{Jackpot}(j)}$ ，而剩下的機率，分別有機率　$p_{k}$　可以參與　$k$　張卡免費遊戲，並且免費遊戲可以有集點機制!! 註: $$\sum_{j \in J}p_{j} + \sum_{k \in K} p...

本文介紹如何利用機率母函數(Probability Generating Function) 推導  $\color{red}{獨立n 局期望比例(投資報酬率)的解析式}$，相關概念與延伸問題 [機率情境] 現實生活中，往往是有付出($Paid$) 可能會有回報($Gain$)。 設樣本元/空間記做 $\omega \in \Omega$，$|\Omega|<\infty$，單局發生機率為 $p_{\omega}$ 此時會有產生成對樣本 $(Gain(\omega),Paid(\omega))$。 代表有 $\color{red}{p_{\omega}}$ 機率，你會先付出$\color{blue}{Paid(\omega)} \neq 0$ 元，而最後會回收 $\color{blue}{Gain(\omega)}$ 元 ，當局淨收入為 $Gain(\omega)-Paid(\omega)$，單局投資報酬率為 $\frac{Gain(\omega)}{Paid(\omega)}$ 而單局期望投資報酬率為 $$\sum_{\omega \in \Omega} p_{\omega}\left(\frac{Gain(\omega)}{Paid(\omega)}\right) =:  E\left[\frac{X_i}{Y_i}\right]$$ 其中 $(X_i, Y_i)$ 為隨機變數序對 : (回收值，付出值) $$(X_i,Y_i) \overset{iid}{\in} \bigg\{(Gain(\omega),Paid(\omega))  \bigg\}_{p_{\Omega}=(p_{\omega})}$$ [$n$局期望比例(投資報酬率)] 然而往往會參與 $n$ 局，投資報酬率(隨機變數)為 $ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i} $ ，目標是如何計算出 $E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right]$  ??，很明顯即使每局是獨立同分布，一般情況下，$$E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}...

本文介紹經典的"賓果 Bingo" 遊戲，機率與期望值的解析計算公式的計算概念，相關的數學建模....等等 [遊戲情境] 總共有 $n$ 個相異的號碼彩球，號碼集為 $S:=\{1,2,3,....n\}$，今玩家可以花$1$元，買$1$張賓果卡 ($5 \times 5$) 位置座標集 $Z$, $|Z|=25$，然後從$S$ 隨機均勻選擇 $25$個相異的號碼並排列到一個佇列(queue)，而開球只會開前 $m$ 顆球，$25 \leq m\leq n$，而給定獎項圖形集 $\color{red}{p \in P := \{Bingo，王，十，一_1,一_2,...,一_5  \}}$ (可自行設計) ，以及已知賠率表向量 $odds_{P}$。開完球後，把Bingo 卡上的中獎的號碼圈起來形成"中獎圖形" ===================================================== 其中獎項圖形 : "$Bingo$" 代表$25$個號碼全中 "十"代表第 $3$ 列(row)  第 $3$ 行 (column) 有中 (共$9$個號碼) "王"代表第 $1$ , $3$ , $5$ 列(row)  第 $3$ 行 (column) 有中 (共$17$個號碼) "$一_k$" 代表第 $k$ 列有中 (共$5$個號碼) ===================================================== 若中獎圖形有涵蓋獎項圖形大致會獲得，賠率 $odds_{p} \times 1 $ 元，但有些合理規則: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $[ 規則 1 ]$ 若獎項圖形 $p_1,p_2$ 有完全重疊$(p_1 \subseteq p_2)$，則以大圖形 $odds_{p_2}$ 賠率算 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ $$\color{green}{ 重要假設: 合理的...

本文介紹格子點(Lattice) 幾何意義與多項式定理(Mutinomial Theorem) 的關係，並可協助我們理解計算一些機率問題。 [符號定義] 非負整數 / 非負實數:  $\mathbb{Z}_{\geq 0} := \{0,1,2,3,4,......\}  \subseteq [0,\infty) =: \mathbb{R}_{\geq 0}$ 離散機率向量:  $$p_{I} := (p_{i})_{i \in I} \text{ s.t } \sum_{i\in I}p_i =1 ，|I|<\infty  $$ 發生事件 $i \in I$ 的累積次數向量: $$ k_{I} := (k_i)_{i \in I} \in \mathbb{Z}^{|I|}_{\geq 0} $$ $\mathbb{Z}^{|I|}_{\geq 0}$ 就是 $|I|$ 維格子點 !! [格子點情境] 出發點定義為 $k^{start}_{I}:= \overbrace{(0,0...,0)}^{|I|}$，今發生一次 $p_{I}$ 分布隨機互斥事件，等價於"點的移動"(state transition)，數學定義如下: $$  \text{Event } i  \text{ happens }  \Longleftrightarrow  \overbrace{(\color{red}{k_i},k_{-i})}^{k^{old}_{I}}  \underset{\text{with probability }p_{i}}{\longrightarrow}   \overbrace{(\color{red}{k_i+1},k_{-i})}^{ k^{new}_{I}}    $$ PS1: 其中  $k_{-i} := (k_{i'})_{i' \in I-\{i\}}$ PS2: 不管怎麼走都在第一象限，也就是只能往右，往上，往高.... 當發生 $n$ 次獨立同分布 $p_{I}$ (iid) 的事件後，所有可能點位置在以下的集合上 $$  S_{n}(\col...

本文說明機率論如何在給定機率事件(Events) 如何轉成互斥機率事件(Disjoint Events) 的一些方法 [機率論複習/符號定義] 令 $\omega \in \Omega$ 為樣本點(sample)，樣本空間(sample space)。以及已經定義的(pre-defined)一些事件集 (Events) $ e \in E$ ，與每個事件 $e$ 所對應的樣本點集 $\omega \in \Omega_{e}$ 當隨機發生時，相當於從樣本空間 $\Omega$ 根據機率分布 $p_{\Omega}$ 而產出一個元素 $\omega_{*}$  當 $\omega_{*} \in \Omega_{e}$  我們說事件 $e$ 發生，反之沒發生，發生的機率為 $$p_{e}:=\sum_{\omega \in \Omega_{e}}p_{\omega}$$ 註: 現實生活中，事件 $e$ 的樣本集通常是 $\{0,1\}^{n}$ 的子集, $n$ 可能為"實驗次數"或是"黑箱個數" $$\bigwedge_{e \in E} \left( \Omega_{e} \subseteq \{0,1\}^{n} \right)$$ [問題定義] 如何給定 $ \Omega_{E} :=  \{\Omega_{e}\}_{e \in E}$ 找到互斥事件集 $E^{disjoint}$ 與其樣本集 $\Omega_{E^{disjoint}}:= \{\Omega_{e} \}_{e \in E^{disjoint}}$ 而且 $$  \bigwedge_{e \in E} \bigg( p_{e} \in Span \bigg\{ p_{e'}: e'\in E^{disjoint} \bigg\} \bigg)$$ [文氏圖交集想法] 很明顯有一個解 $\Omega_{E^{disjoint}} =  \bigg\{\displaystyle{ \bigcap_{e \in S}\Omega_{e} \cap \bigcap_{e \in E\setminus S}\bar{\Omega}_{e } : S \subseteq E ...

本文介紹筆者自己定義的名詞 : Merge Encoding ，或許有別的學術名詞 !! 數學概念簡單易懂，用途方便理解集合論，機率論，壓縮紀錄大量的元素等等 :) 在數學上，我們習慣會用  $\{0,1\} = \{ False , True \}$，而且日常生活經驗常構造出高維度子集合 $$ s \in  S \subseteq  \{0,1\}^{n} $$ ==================================================== 例如 : $n = 3$  長相大概像這樣 $$ s \equiv (s_1,s_2,s_3) \in S = \{(0,0,1), (1,0,1),.....\} \subseteq \{0,1\}^3$$ ==================================================== 很明顯 $|S| \leq 2^{n}$，而且 $$\bigwedge_{s \in S}\bigg(\sum_{k=1}^{n} s_k \in [0,n]_{\mathbb{Z}} \bigg)$$ 可以把 $n$ 想成物件的集合個數 $|K|$ ，$K$ 為物件集，則 $S$ 相當於選取哪些物件可能的組合，類似背包問題(knapsack problem)的概念。 ===================================================== 例如: $(0,1,1)$ 代表選第2個與第3個物件 ===================================================== 今想要表達一個物件 $k \in K$ 在集合$S$是可有可無的概念，也就是  $$(s_{k},s_{-k}) , (\bar{s_k},s_{-k})  \in  S$$ 其中 $$\bar{s_k} =  \left\{ \begin{array}{ccc} 1 & \text{if }  & s_k = 0 \\  0 & \text{if } & s_k =1 \\ ...

本文介紹比較有效率計算路徑個數的演算法，以及一些數學概念的整合 [符號定義] 考慮點集 $k \in K = \{1,2,.....|K|\}$ (stages) ，以及每個 stage $k$ 的可能值 $x_k$ 與其空間集 $X_{k}$ (state space)  也就是 $$ \bigwedge_{k \in K}\bigg( x_k \in X_{k} \bigg)$$ 另外我們把 $K$ 集定義有序陣列的概念(list,array) !!  $K^{<} := [1,2,3,4,....|K|] , K^{>} := [|K|,....,2,1]$ 而現實生活中有許多分類的層狀結構，數學上可寫成 $$ \bigwedge_{k \in K^{<}}\bigg(x_k\in \color{red}{X_{k}(x_{k-1})} \bigg)$$ 其中 $\color{red}{X_{k}(x_{k-1})} \subseteq X_{k}$ 為 DependSet 的概念，代表給定 $x_{k-1}$ 下，$X_{k}$ 的可能值，這些 $\color{red}{X_{k}(x_{k-1})}$ 是已經被定義的，而且 $X_{1}(\underset{=\emptyset}{x_0}) \equiv X_{1}$ 註: 每個 $X_{k}$ 只跟上一層 $x_{k-1}$ 值有關，而與前幾個值 $x_{k-2},x_{k-3}, ...$ 無關， 即類似馬可夫鍊(Markov Chain)相依，而非路徑相依 (Path-dependent) ================================== 舉例: 生物分類的界門綱目科屬種的概念 可以想成 $X_1 = $ 界 ，$X_2(x_1) = $ 門 ，$X_3(x_2) =  $  綱 .... ================================== [問題定義] 定義 $$\mathcal{R} :=  X_{1} \times X_{2}(x_1) \times X_3(x_2) .... \times X_{|K|}(x_{|K|-1})...

本文介紹在一張簡單無向圖 $G(V,E^{<})$上，點記做 $i,j \in V$。 每個邊 $e := \{i,j\} \in E^{<}$ ，Either 連通=0 or 不連通=1。今給定起訖點 $o,d  \in V , o \neq d$ ，od-pair 記做  $<o,d>$ ，由於可能有很多替代的路徑可以從 $o$ 走到 $d$ 如何描述(表達集合) $<o,d>$ 為連通/不連通時"邊集"的情況 ?? ====================================================== 預備知識: $$\displaystyle{ \bigwedge_{s \in S}} Equation(s) $$  是邏輯大 And 或可嚴謹讀作  $\forall s \in S , Equation(s) \text{ is true}$    $$ \displaystyle{\bigvee_{s \in S} } Equation(s) $$  是邏輯的大 Or   或可讀作  $ \exists s \in S , Equation(s) \text{ is true }$ ====================================================== 符號定義: 1. $\mathcal{P}_{<o,d>}$  為起點為 $o$，終點為 $d$ 所有"路徑名稱(下標 index)"的集合    2. $  E^{<}_{p}   \subseteq E^{<}$ 路徑 $p \in \mathcal{P}_{<o,d>}$ 經過的無向邊集 3. 起訖點$<o,d>$可能會經過的所有無向邊的集合(路徑是由"邊"組成的) $$\displaystyle{E^{<}_{<o,d>} :=  \bigcup_{p \in \mathcal{P}_{<o,d>}} E^{<}_{p}...

本文介紹"隨機變數"與線性代數"內積空間"的關係 !! ============================================= 在線性代數(Linear Algebra) 裡大家都熟悉向量的內積運算，即給定兩個 $|I|$ 維向量，$u_{I}:= (u_i)_{i \in I},\quad v_{I}:= (v_i)_{i\in I}  \in \mathbb{R}^{|I|}$，註: 編號化 $I \equiv \{1,2,3,....|I|\}$ 可以定義大家熟悉內積的運算 $$\left< u_{I},v_{I} \right> := \sum_{i\in I} u_i \cdot v_i$$ 簡記為$<u,v>$，令 $w$ 也為向量，$\alpha , \beta  \in \mathbb{R}$ 為實數 有一些大家熟悉的內積空間性質 (*)  , (註:不討論係數為虛數 $\mathbb{C}$): =========================================================== $ [1] \text{對稱性 }   \left< u,v \right>  =   \left< v,u \right> $ $ [2]\text{左分配律}    \left<u + w  , v \right>  =   \left<u , v \right>  +  \left<w , v \right>  $ $ [3] \text{右分配律}     \left<u   , v+w \right>  =   \left<u , v \right>  +  \left<u , w \right>  $ $ [4] \text{左線性}   \lef...

本文為筆者學習微積分，函數概念與Chain Rule 的時候，遇到的一些概念大坑。本文一一澄清一些個人看法，並分享 Chain Rule 廣義的樣子，以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 $y = f(x)$ 開始，我們習慣把 Input 變數用"括號"刮起來，Output y 代表值，f 代表函數。或是可以想成這樣:   $$ x \overset{f}{\longrightarrow} y $$ 這種表示法概念上很嚴謹，但缺點是你必須要用三個符號 $x$，$y$，$f$ 而在微分方程領域出現這種寫法 $y = y(x)$  (把 $f$ 換成 $y$) ，這種寫法就頗簡潔，Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 $y$ 到底是給定的"值"還是"函數"(註: 通常大多代表函數 $y$，值的話通常會這樣寫 $y(x_{0})$,$y_{0}$) ============================================================== [Bonus] $y=y(x)$這種表示法還有一個好處，如果允許 $f$ 是一對多，那麼 $y(x)$ 就是 $y \text{ is depend on } x$ 的意思，如果你喜歡用集合論來表示可以先定義$f$ 的定義域/對應域 $$ f : X \rightarrow Y$$ 然後 $y(x)$ 可以寫成這樣 $y \in Y_{x}$，其中值域為 $$ f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y$$ ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒： (Ex1) 代換法會重新改變函數的 Input 例如 : $y = f(x) = x+1$ , $ z = g(y) = 2y$ 　可以代換一下，寫成 $z = g[f(x)] = 2(x+1)$ 如果你用簡記你會發現　$y(x) , z(y) , z(y(x)) \equiv z...

本文是記錄一些使用集合論語言，表達路徑(Path)/線段(Undirected Arc) 組成的關係: 令所有的路徑集為 $p \in P$，所有的線段集 $a \in A$ 路徑是由許多線段(無方向性)所組成的，自然存在對應關係 $E \subseteq P\times A$，可使用圖論二分圖描述 $G(P\cup A,E)$ 可以定義相依集：$$P_{a}:=\{p\in P : (p,a)\in E \},A_{p}:= \{a\in A :(p,a) \in E \}$$  並且滿足以下自然對偶邏輯(Natural Dual Correspondence) $$ \bigwedge_{(p,a)\in P\times A} \left( p \in P_a  \Longleftrightarrow a \in A_{p}  \right)   $$ 如果$X_a$為線段長，則很明顯路徑長可寫為 $$\bigwedge_{p \in P}\left( X_{p}:= X(A_p) = \sum_{a\in A_p} X_{a} \right)$$ 路徑長公式可以寫成線性系統　$$ X_{P} := M_{P\times A} X_{A} $$ (其中$X_P$,$X_{A}$ 為向量，$M_{P\times A}$ 為 $0-1$ adjacency sparse  matrix) 由線性系統可以求出反矩陣，而導出 $X_{A}= M^{-1}_{P\times A}X_{P} $) 定義 $p$ 損壞必定影響的路徑集 $$ \bigwedge_{p\in P}\left( P^{\cap}_{p}:= \bigcap_{a\in A_{p}} P_{a} \right) $$ 代表只要路徑 $p$ 斷了，則所有路徑 $p' \in P^{\cap}_{p}$ 也必定會斷，($p$是$p'$的一部分)  $$ \bigwedge_{p \in P}\bigwedge_{p' \in P^{\cap}_{p}} \left(A_{p} \subseteq A_{p'}\right)$$ 定義 $p$ 損壞可能影響的路徑集 ...

本文為分析電玩裡常見的期望值小問題: ================================================== 如果有 $n$ 個庫存物/道具。每使用 $1$ 次庫存物/道具時，有 $p \in [0,1]$ 的機率不會消耗這次使用，那麼平均而言總共可以使用幾次 ??  有多少扣達(quota) ?? (假設每次使用的機率機制相同，獨立同分布，Bernoulli 試驗) ================================================== 首先先定義隨機變數 $T$ ，代表總共只可以使用了 $T$ 次，而以 $t$ 表示隨機變數的"取值"，根據生活經驗很明顯 $t \in [n,\infty)_{\mathbb{Z}} = \{n,n+1,n+2,.....\}$  定義當 $T = t$ (當隨機變數 $T$ 取值為 $t$) 的機率為 $$ P_t := Pr(T=t)  $$ 則本文目標為計算期望值: $$ E[T] =  (\text{可能次數} \times \text{對應的機率}) \text{的總和} $$ $$ = \sum_{t \in [n,\infty)_{\mathbb{Z}}} t \cdot Pr(T=t) = \sum^{\infty}_{t = n} t \cdot P_{t} = \underbrace{ \lim_{N \rightarrow \infty} \left(\sum^{N}_{t = n} t \cdot P_{t}\right) }_{\text{嚴謹寫法}}$$ 而機率計算如下: $$ P_{t}= \overbrace{\left[ \underset{\text{不盡相異物直線排列數}}{\left( \begin{array}{c} t-1 \\ n-1 \\ \end{array} \right)} p^{t-n} (1-p)^{n-1} \right]}^{\text{前 $t-1$ 次，共消耗了 $n-1$ 個道具，得到了$t-n$ 次再使用機會}} \cdot \overbrace{(1-p)}^{\text{最後 1 次 消耗了...

本文為紀錄簡易博弈模型，若滿足有交集則彩金"疊加性"，則傳統期望值可推廣到非互斥事件上。 給定 開獎結果(樣本空間) $\Omega$ ，投注項目集 $B$ ， 投注項目 $b$所對應的開獎結果集 $\Omega_{b}$ $$ \bigwedge_{b \in B}\left(\Omega_{b} \subset \Omega\right)$$ 以及定義 $\Omega_{b}$補集: $$\displaystyle{\bigwedge_{b \in B} \left( \bar{\Omega}_{b}:= \Omega \setminus \Omega_{b} \right) }$$ 機率公設與 $\Omega_{b}$ 定義計算如下: $$\displaystyle{ \sum_{\omega \in \Omega} P(\omega) = 1} $$ $$\displaystyle{\bigwedge_{b \in B} \left( P(\Omega_{b}) := \sum_{\omega \in \Omega_{b}} P(\omega) \right)} $$ 描述文氏圖互斥分割集概念如下: $$\displaystyle{\Omega = \bigcup^{\text{disjoint}}_{S \subseteq B} \left(\bigcap_{b \in S}\Omega_{b} \cap \bigcap_{b \in B\setminus S} \bar{\Omega}_{b}\right)  }$$ 開獎機制如下: 假定 開獎結果 $\omega$，投注$b$ 項目中獎可獲得彩金 $c^{bingo}_{b}$ 元，槓龜獲得彩金 $c^{turtle}_{b}$ 元 $$\displaystyle{\bigwedge_{(b,\omega) \in B\times \Omega}\left\{\begin{array}{l}\omega \in \Omega_{b} \Longleftrightarrow \text{得到 } c^{bingo}_{b}\\ \omega \not\in \Omega_{b} \Longleftrightarrow  \text{...

本篇介紹一些筆者認為重要的整數規劃-圖形，邏輯建模技巧與概念，關於整數規劃的用途，可先參考之前這篇: http://discoverforgottenmath.blogspot.tw/2017/09/why-integer-programming-is-important-in.html 而建模技巧是把日常生活中的邏輯給正確的連結到方程式上!! 以下我們都把 $X \in \{0,1\}$ 視為  boolean 決策變數 ======================================= 刻劃出點 Node $i , j$ 跟邊 Arc $(i,j)$ 關係 ======================================= 定義: $X_{i} = 1  \text{ iff }  $ 我選擇了點 $i$ $X_{ij} = 1  \text{ iff }  $ 我選擇了邊 $(i,j)$ $$(E1) \quad \text{if  $(i,j)$ is selected  then ($i$ and $j$) are selected} $$ $$ \left\{\begin{array}{c} X_{(i,j)}\leq X_i \\ X_{(i,j)}\leq X_j \\ \end{array}\right.$$ $$(E2) \quad \text{if ($i$ and $j$) are selected then $(i,j)$ is selected } $$ $$ X_{i}+X_{j} \leq 1+X_{(i,j)} $$ $(E1)$ 是現實生活中自然的邏輯: 意涵代表，我選擇了這條邊 $(i,j)$ 則我自然會 cover $i , j$ 這兩個點 $(E2)$ 則不一定會有的邏輯，需思考 $(i,j)$ 的定義 例如:  我定義 $(i,j)$ 為直接從 $i$ 走到 $j$ 則走路徑 $(i \rightarrow j \rightarrow k \rightarrow w)$ 則 $X_{i}=1 , X_{w} =1 $ 但是 $X_{(i,w)} = 0$ ，...

本篇以隨筆平易近人的方式，寫一些如何降低演算法"計算量"的一些核心抽象概念。 [利用分配律尋找完全多分圖] 相信大家都知道加法$(+)$ ，乘法$(\times)$ 分配律的概念，複習一下 $$   (A+B)\times (C+D)   =A \times C + B \times C + A \times D + B \times D$$ 左式推廣我們可以寫成 $$ \underbrace{(A_1+A_2+....+A_{L_1})}_{\text{第一組}}\times  \underbrace{(B_1+B_2+....+B_{L_2})}_{\text{第二組}} \times ...  \times \underbrace{( ... )}_{\text{第 $m$ 組}}  $$ 每一組 有$L_{i}$ 個元素，總共有 $L$ 個元素(字母) 而且每一組有 $L_{i} -1$ 個加法，總共就有 $$\displaystyle{\sum^{m}_{i=1}(L_i - 1) =  L - m } \text{ 個加法} $$ 由於每一組中間穿叉乘法，有 $m-1$ 個乘法。我們分別把加法，乘法個數記做 ~ $\otimes $ , $ \oplus$，所以左式總共的運算數為 $$  \text{左式運算量 = } (m-1) \cdot \otimes  + (L-m) \cdot \oplus    $$ 右式完全展開，非常多項，要完整寫出來並非容易的事，但是我們知道它應該是長這樣 $$ (\text{第一組連乘}) + (\text{第二組連乘} ) + (\text{第三組連乘} ) + ........ $$ 至於究竟有幾組連乘呢 ?? 答案是 $\displaystyle{ \prod^{m}_{i=1}L_i }$ 組，而每一組中間穿叉 $L_i -1$ 乘法 右式總運算量為 $$ \text{右式運算量 = } (L-m)\cdot \otimes  + \displaystyle{ \pr...

本篇文章使用淺顯易懂集合論的語言，連接統計學現實與抽象化的過程，來重新詮釋統計學的概念，並區分一些差異與澄清一些觀念，希望能對初學統計的讀者有些幫助。 [定義有限母體] 日常生活中，母體的概念大家都能理解，很多很多個體。我們可以定義一個很大但有限的集合$\Omega$ ，每個獨一無二的個體記做 $s$ ，所以可以寫成 $s \in \Omega$ 而全部個數記做 $N$ (現實生活中$N$很大通常未知，除非我們有能力有時間消耗大量成本做普查才能得知 $N$) $$ |\Omega| = N  $$ [ex:] 例如全台灣人，兩千三百萬人左右，則可以寫成 $N \approx 2300 \times 10^4$ 而我們感興趣的可能是個體的可以量化的屬性(如:身高，成績)，所以可以定義一個實數函數(real-valued function) $$ X : \Omega \longrightarrow  \mathbb{R}  $$ [ex:] 例如阿元的月收入$\$$  可以寫成     $X(阿元) =  22 \times 10^3$  或是記做下標 $X_{阿元} = 22 \times 10^3$ ，而每個人的月收入有高有低，如果把那些"值"聯集起來，我們能說一定若在實數域裡面 !! [屬性值有哪些] 數學上來說就是 range of $X$ , image of $X$ $$ X(\Omega) := \{ X_s  \in \mathbb{R}: s\in \Omega \} = \bigcup_{s\in \Omega} \{ X_s\} \subset \mathbb{R} $$ 這時我們可以把薪水的值記做 $x \in X(\Omega)$ [計數與比例] 這時大家會好奇說有沒有其他人跟我一樣的薪水，還有那群人在全台灣人佔了多少比例，所以會計算個數 (Count) ，以及比例 (Frequency) 。 正是數學定義如下: $$  \text{Count}(x,\Omega) :=   |\{ s\in \Omega :  X_s = x  ...

本篇為筆者使用集合論符號，方便抽象推廣化到多維陣列。 ====================================== [符號提醒] 由於有些符號有點抽象，為了方便讀者了解，小寫大多為"元素"，大寫大多為"集合" $\prod$ 代表集合的 Catesian Product , $ \sum $ 代表連加，$| \cdot |$ 代表集合元素個數(Cardinality)，符號幾乎不會混用，並注意字母粗體的差別!! [定義論域] 首先定義下標符號集合 $i \in I$ , 而且給定多維離散結構有限集合 $$\mathcal{R}_{I}  \subseteq U_{I} $$ 其中 $U_{I}$ 為給定 $|I|$維座標宇集 $$ u_{I} \in U_{I} = \prod_{i\in I}U_i$$ , 正式定義如下 ====================================== [定義整體離散結構] $$ \mathcal{R}_{I} := \left\{ u_I = \underbrace{(u_i)_{i\in I}}_{|I|\text{dim - tuple}} \in U_{I} \left| u_i \in U_i  , \forall i \in I ,  u_{I} \text{ satisfies something ...} \right. \right \}$$ [ex1] 關於 $\mathcal{R}_{I}$ 與 depend sets 的例子可以參考這篇 https://discoverforgottenmath.blogspot.tw/2017/08/framework-of-creating-depend-sets-given.html 可以簡記 $u_{I} \in \mathcal{R}_{I}$ 對於每個 $i \in I$，可以把 $u_{I}$ 寫成 $(u_{i},u_{I-\{i\}} )$ , 也可以簡記為 $u_{I} = (u_{i},u_{-i} )$  (賽局理論表示法) ====================================== [收集出一維結構] 對...