文章目錄

• 一、Stirling 子集數(shù)
• 二、放球模型
• 三、Stirling 子集數(shù)遞推公式
• 四、Stirling 子集數(shù)示例 ( 四元集等價(jià)關(guān)系個(gè)數(shù) )
• 五、劃分的二元關(guān)系 加細(xì)關(guān)系

一、Stirling 子集數(shù)

---

Stirling 子集數(shù) :

將 $n$ 個(gè)不同的球 放到 $k$ 個(gè)相同的盒子 中 , 不能有空盒 , 即 每個(gè)盒子至少放一個(gè)球 ;

不同的放置方法總數(shù)是 : $\left\{\begin{array}{c}n\\ k\end{array}\right\}$ , 該數(shù)稱為 Stirling 數(shù) ;

將 $n$ 元集分成 $k$ 個(gè)非空子集 的 分法個(gè)數(shù) ;

劃分 與 等價(jià)關(guān)系 的描述是等價(jià)的 , 每個(gè) 劃分 都與 等價(jià)關(guān)系 一一對(duì)應(yīng) ;

Stirling 子集數(shù)作用 : 求集合中有多少不同的 等價(jià)關(guān)系 , 即求集合中有多少個(gè)不同的 劃分 ;

二、放球模型

---

放球模型 : 上述 斯特林 Stirling 子集數(shù) , 是小球放在盒子中 , 小球是有編號(hào)的 , 需要 區(qū)分不同的小球 , 盒子是沒有編號(hào)的 , 不需要進(jìn)行區(qū)分盒子 ; 下面整理下不同的放球模型 :

• 球有編號(hào) , 盒子沒有編號(hào) ( 不同的球放在相同盒子里 ) : 這是求集合 劃分問題 , Stirling 數(shù) ; 這屬于放球子模型 ;
• 球沒有編號(hào) , 盒子有編號(hào) ( 相同的球放在不同盒子里 ) : 不定方程解問題 , 多重集組合問題 , 正整數(shù)剖分問題 ;
• 球有編號(hào) , 盒子有編號(hào) ( 不同的球放在不同的盒子里 ) : 多重集排列 , 指數(shù)函數(shù)問題 ;

$\left\{\begin{array}{c}n\\ k\end{array}\right\}$ 表示將 $n$ 個(gè)元素分成 $k$ 個(gè)子集的分法個(gè)數(shù) ;

$\left(\begin{array}{c}n\\ k\end{array}\right)$ 表示從 $n$ 個(gè)元素中選出 $k$ 個(gè)小球的方案?jìng)€(gè)數(shù) ;

參考 : 百度百科-放球問題

三、Stirling 子集數(shù)遞推公式

---

常見的 Stirling 子集數(shù) 結(jié)果 :

$\left\{\begin{array}{c}n\\ 0\end{array}\right\}=0$

將 $n$ 個(gè)球放在 $0$ 個(gè)不同的盒子里 , 有 $0$ 種分法 ;

將 $n$ 個(gè)元素分成 $0$ 類 , 有 $0$ 種分法 ; 就是 沒有方法 ;

$\left\{\begin{array}{c}n\\ 1\end{array}\right\}=1$

將 $n$ 個(gè)球放在 $1$ 個(gè)不同的盒子里 , 有 $1$ 種分法 ;

將 $n$ 個(gè)元素分成 $1$ 類 , 有 $1$ 種分法 ; 相當(dāng)于 全域關(guān)系 ;

$\left\{\begin{array}{c}n\\ 2\end{array}\right\}=2^{n?1}?1$

將 $n$ 個(gè)球放在 $2$ 個(gè)不同的盒子里 , 有 $2^n?1$ 種分法 ;

$n$ 元集有 $2^n$ 個(gè)不同的子集合 , 這是冪集的個(gè)數(shù) , 每個(gè)子集合 , 與其補(bǔ)集都成對(duì) , 因此 有 $2^{n?1}$ 對(duì)集合 , 其中要 減去 空集合 與 全集合 的那一對(duì) , 最終結(jié)果是 $2^{n?1}?1$ ;

$\left\{\begin{array}{c}n\\ n?1\end{array}\right\}=C_2^n$

將 $n$ 個(gè)球放在 $n?1$ 個(gè)不同的盒子里 , 有 $C_2^n$ 種分法 ;

將 $n$ 個(gè)元素分成 $n?1$ 類 , 有兩個(gè)元素算作一類 , 其它每個(gè)元素都自成一類 ; 只要將 $n$ 個(gè)元素中屬于一類的 $2$ 個(gè)元素選出即可 , 有多少中選法 , 就有多少分類 ;

$\left\{\begin{array}{c}n\\ n\end{array}\right\}=1$

將 $n$ 個(gè)球放在 $n$ 個(gè)不同的盒子里 , 有 $1$ 種分法 ;

將 $n$ 個(gè)元素分成 $n$ 類 , 有 $1$ 種分法 ; 相當(dāng)于 恒等關(guān)系 ;

Stirling 子集數(shù) 遞推公式 :

$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=k\left\{\begin{array}{c}n?1\\ k\end{array}\right\}+\left\{\begin{array}{c}n?1\\ k?1\end{array}\right\}$$

將 $n$ 個(gè)元素分為 $k$ 類 ,
先把一個(gè)元素挑出來 , 放在一邊 , 還剩 $n?1$ 個(gè)元素 ;

挑出的元素合并到其它類 : 將這 $n?1$ 個(gè)元素分為 $k$ 類 , 將挑出來的元素分別加入到 $k$ 類中 ; 得到的總結(jié)果就是 $n$ 個(gè)元素分為 $k$ 類 , 挑出來的元素分別加入到 $k$ 類中 , 有 $k$ 種不同的方法 , 即分別加入到低 $1,2,3,?,k$ 類中 ;

挑出的元素自成一類 : 將 $n?1$ 個(gè)元素分為 $k?1$ 類 , 每個(gè)類都非空 , 然后讓挑出來的元素自成一類 , 該自稱一類的類 與 之前的 $k?1$ 個(gè)類 , 合并在一起是 $k$ 個(gè)類 ;

上述兩種情況同時(shí)考慮 , 就是 Stirling 子集數(shù)的遞推公式 ;

$k\left\{\begin{array}{c}n?1\\ k\end{array}\right\}$ 含義 : 將 $n?1$ 個(gè)元素分成 $k$ 個(gè)子集 $\left\{\begin{array}{c}n?1\\ k\end{array}\right\}$ , 再 加入第 $n$ 個(gè)元素到其中之一 有 $k$ 種方案 , 在上述基礎(chǔ)上乘以 $k$ ;

$\left\{\begin{array}{c}n?1\\ k?1\end{array}\right\}$ 含義 : 將 $n?1$ 個(gè)元素分成 $k?1$ 個(gè)子集$\left\{\begin{array}{c}n?1\\ k?1\end{array}\right\}$ , 剩下的第 $n$ 個(gè)元素自然成為一個(gè)子集 ( 只有唯一一種方案 ) ;

四、Stirling 子集數(shù)示例 ( 四元集等價(jià)關(guān)系個(gè)數(shù) )

---

求四元集上的等價(jià)關(guān)系個(gè)數(shù) , 即 $4$ 個(gè)元素分為 $1,2,3,4$ 類的分法相加 ;

$\left\{\begin{array}{c}4\\ 1\end{array}\right\}+\left\{\begin{array}{c}4\\ 2\end{array}\right\}+\left\{\begin{array}{c}4\\ 3\end{array}\right\}+\left\{\begin{array}{c}4\\ 4\end{array}\right\}=1+(2^{4?1}?1)+C_2^4+1=1+7+6+1=15$

四元集上的 有序?qū)€(gè)數(shù)是 $4\times 4=16$ 個(gè) ;

四元集上的 關(guān)系個(gè)數(shù)是 $2^{16}=65536$ 個(gè) ; 包含如下情況 , 含有 $0$ 個(gè)有序?qū)?, 含有 $1$ 個(gè)有序?qū)?, $?$ , 含有 $16$ 個(gè)有序?qū)?;

上面 $65536$ 個(gè)二元關(guān)系中有 $15$ 個(gè)是等價(jià)關(guān)系 ;

五、劃分的二元關(guān)系 加細(xì)關(guān)系

---

集族 $\mathcal{A}$ 和 集族 $\mathcal{B}$ 都是 集合 $A$ 的劃分 ,
如果 $\mathcal{A}$ 中每個(gè)劃分塊 都包含于 $\mathcal{B}$ 的某個(gè)劃分塊 中 , 則稱 $\mathcal{A}$ 劃分 是 $\mathcal{B}$ 劃分 的加細(xì) ;

加細(xì) 是一個(gè)二元關(guān)系 , 是劃分之間的二元關(guān)系 ;

加細(xì)關(guān)系具有 :

• 自反省 : 每個(gè)劃分是它自己的加細(xì)
• 傳遞性 : $\mathcal{A}$ 是 $\mathcal{B}$ 的加細(xì) , $\mathcal{B}$ 是 $\mathcal{C}$ 的加細(xì) , $\mathcal{A}$ 是 $\mathcal{C}$ 的加細(xì)
• 沒有對(duì)稱性 : 加細(xì)不具有對(duì)稱性
• 沒有全域關(guān)系 : 有的劃分之間互相都不是加細(xì)

總結(jié)

以上是生活随笔為你收集整理的【集合论】Stirling 子集数 ( 斯特林子集数概念 | 放球模型 | Stirling 子集数递推公式 | 划分的二元关系 加细关系 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。