All Different Expansion & Bell Numbers

本文分享筆者在計算排列組合(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)} $ $abcb$，$adcd$，$bcac$，....  代表二同二異(且$x_{2}=x_{4}$)
...
$$ \color{red}{\text{註: (3),(4) 雖然都為二同二異，但因為出現是有序的，相同位置不同，視為不同類，保持計數靈活性!!} } $$
顯而易見也是關鍵步驟 ~
可以把 $\color{green}{(1)}$ 類別，標記為 $1111$
可以把 $\color{green}{(2)}$ 類別，標記為 $1234$
可以把 $\color{green}{(3)}$ 類別，標記為 $1213$
可以把 $\color{green}{(4)}$ 類別，標記為 $1232$
...
於是我們可以系統性的，把所有的 $x_{T}$  做適當的分類 ~~
但你實際上去標記，會發現有些標法 $1324$, $1242$,... 是不允許的(會混淆的，會重複算的，迷失在對稱裡等窘境)。會遭遇困難~需要系統性的標法!!

[如何標記?!]
令標記數列 $y_{T}:=(y_t)^{|T|}_{t=1} \in T^{|T|} \quad  ps. 1232 \equiv \bigg( y_{1}=1,...,y_{4}=2 \bigg) $

而且必須滿足以下遞迴式，才不會有"標記窘境"
$$\color{red}{ \bigwedge_{t\in T} \bigg( y_{t} \leq \underset{t' \in \{1,2,....t-1\}}{\text{max}} y_{t'}+1  \bigg) }$$

用集合表示可寫成:
$$\color{red}{\mathcal{D}_{|T|}:= \bigg\{y_{T}\in T^{|T|} :  \bigwedge_{t\in T} \bigg( y_{t} \leq \underset{t' \in \{1,2,....t-1\}}{\text{max}} y_{t'}+1  \bigg)  \bigg\}  }$$

於是可以寫程式去窮舉 $\mathcal{D}_{|T|}$，去計算 $|\mathcal{D}_{|T|}|$，以下是實驗結果 !!
=============================================================
$|\mathcal{D}_1| =  1 ,\mathcal{D}_{1} = \{1\}$
$|\mathcal{D}_2| =  2 ,\mathcal{D}_{2} = \{11,12\}$
$|\mathcal{D}_3| =  5, \mathcal{D}_{3} = \{111,112,121,122,123\}$
$|\mathcal{D}_4| =  15, \mathcal{D}_{4} =\{1111,1112,1121,1122,1123,1211,1212,1213,1221,1222,1223,1231,1232,1233,1234\}$
$|\mathcal{D}_5|=52$ ,  $\mathcal{D}_{5} = $ 略
$|\mathcal{D}_6|=203$ ,  $\mathcal{D}_{6} = $ 略
$|\mathcal{D}_7|=877$ ,  $\mathcal{D}_{7} = $ 略
$|\mathcal{D}_8|=4140$ ,  $\mathcal{D}_{8} = $ 略
$|\mathcal{D}_9|=21147$ ,  $\mathcal{D}_{9} = $ 略
$|\mathcal{D}_{10}|=115975$ ,  $\mathcal{D}_{10} = $ 略
$|\mathcal{D}_{11}|=678570$ ,  $\mathcal{D}_{11} = $ 略
$|\mathcal{D}_{12}|=4213597$ ,  $\mathcal{D}_{12} = $ 略
$|\mathcal{D}_{13}|=27644437$ ,  $\mathcal{D}_{13} = $ 略
==============================================================
[查詢可能的答案?!]
你會發現個數增長的指數快 ....當你跑到 $|T|$ = 14 時，應該會發現電腦無法立即窮舉完，那要如何求得答案 $\mathcal{D}_{|T|} , |T| \geq 14$ 呢??  幸虧我們可以把 $1,2,5,15,52,203,877,4140,21147,115975,678570,4213597,27644437,...$ 這個數列丟進 OEIS (整數數列大百科) ，搜尋後發現跟 Bell Numbers 行為有點像，我們可以很合理臆測(但筆者還未證明)，我們"標記計數" 這件事可能就是 Bell Numbers
從 Bell Numbers 得知 $\mathcal{D}_{16} \overset{?}{=} 10480142147  $
約等於 105 億種標記 = 16張麻將牌型(有序)的種類上界 !!

[標記 $y_{T}$ 的意義?!]
那為何我們要知道 $y_{T} \in \mathcal{D}_{|T|}$ ??，有什麼計算數學意義 ??
$$\color{red}{\text{答: 可以把每一個"標記"想成一個算式 !!} }$$
首先我們先定義 $$ s \in \mathcal{S}(y_{T}) = y_{T} \text{ 的數字種類集} , n_{s} =  \text{個別數字$s$的計數}$$
ex: $$\color{blue}{ \mathcal{S}(112344) = \{1,2,3,4\} \quad  n_1 = 2 , n_2 = 1 , n_3 = 1 , n_4 = 2}$$

對於每個$y_{T}$，就可以定義以下的廣義排列數公式 :
$$
\color{red}{ F\bigg(y_{T},\#_I\bigg) = \underbrace{\sum_{i_1 \in I} \sum_{i_2 \in I-\{i_1\}} ... \sum_{i_{|\mathcal{S}(y_{T})|} \in I- \{i_1,i_2,i_3,...,i_{|\mathcal{S}(y_{T})|-1}\}}\bigg(\prod_{k=1}^{|\mathcal{S}(y_{T})|} P^{\#_{i_{k}}}_{n_{k}} \bigg)   }_{\text{all different expansion}}} = \text{該 $y_{T}$ 狀況下的排列數} $$

註 : $P^{m}_{n} :=  \frac{m!}{(m-n)!}$ 為大家所熟悉的"排列函數"

[極端情況]
$$F\bigg(\overbrace{11...1}^{|T|},\#_I\bigg) = \sum_{i_1 \in I} P^{\#_{i_1}}_{|T|} $$

$$F\bigg(12...|T|,\#_I\bigg) = \sum_{\underbrace{i_1,...i_{|T|}}_{\text{all different }}} \prod_{k=1}^{|T|} P^{\#_{i_k}}_{1} =  \sum_{\underbrace{i_1,...i_{|T|}}_{\text{all different }}} \prod_{k=1}^{|T|} (\#_{i_k})$$
[特殊情況的優化]
如果 $\forall k, n_k = C$ 是常數，會發現"連乘"是可以交換的，在 $\text{all different}$裡，很多$F$值就會是相等的
$$ F = \sum_{\vec{i} \in I^{|\mathcal{S}|}_{\neq}} \bigg(\prod_{k=1}^{|\mathcal{S}|} P^{\#_{i_{k}}}_{C} \bigg) = \color{red}{ |\mathcal{S}|!  \sum_{\vec{i} \in I^{|\mathcal{S}|}_{<}} \bigg(\prod_{k=1}^{|\mathcal{S}|} P^{\#_{i_{k}}}_{C} \bigg)} $$
其中
$ I^{|\mathcal{S}|}_{\neq} :=  \bigg\{\vec{i} \in I^{|\mathcal{S}|}:  \underbrace{i_1 \neq i_2 \neq ... \neq i_{|\mathcal{S}|}}_{\text{all different}}   \bigg\}$
$ I^{|\mathcal{S}|}_{<} :=  \bigg\{\vec{i} \in I^{|\mathcal{S}|}:  i_1 < i_2 < ... < i_{|\mathcal{S}|}   \bigg\} \quad  \text{p.s } I \text{需要先排序 }$


[應用]
例如兩個玩家玩牌類遊戲時，已知每種牌"剩餘個數"(那些 $\#_{I}$)，當發4張牌(依序玩家1->玩家2->玩家1->玩家2)。則發完後玩家2拿到，同花 or 同點(對子) or 同花同點(同花對)的排列數為
$$ F\bigg(1111,\#_I\bigg) + F\bigg(1121,\#_I\bigg) + F\bigg(1212,\#_I\bigg) + F\bigg(1222,\#_I\bigg) + F\bigg(1232,\#_I\bigg)  $$
由此可輕鬆計算機率 !! 其中 $I$ 可為 四種花色集 or $\{A,2,...,J,Q,K\}$ or $52$種牌集 !!

[未來研究]
如何再化簡計算 $F$ ??  $F\bigg(y_{T},\#_I\bigg)$ 如果是定義為某種測度時??

[小記]
本文介紹一種系統性"窮舉式子"，"分類序列"的例子，雖然計算複雜度還是很高，但更能理解"排列組合的深奧結構" !!

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2019.04