【集合论】Stirling 子集数 ( 斯特林子集数概念 | 放球模型 | Stirling 子集数递推公式 | 划分的二元关系加细关系 )

韩曙亮

发布于 2023-03-28 18:06:51

8500

发布于 2023-03-28 18:06:51

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、Stirling 子集数

Stirling 子集数 :

将

个不同的球放到

个相同的盒子中 , 不能有空盒 , 即每个盒子至少放一个球 ;

不同的放置方法总数是 :

\begin{Bmatrix} n \\ k \end{Bmatrix}

, 该数称为 Stirling 数 ;

将

元集分成

个非空子集的分法个数 ;

划分与等价关系的描述是等价的 , 每个划分都与等价关系一一对应 ;

Stirling 子集数作用 : 求集合中有多少不同的等价关系 , 即求集合中有多少个不同的划分 ;

二、放球模型

放球模型 : 上述斯特林 Stirling 子集数 , 是小球放在盒子中 , 小球是有编号的 , 需要区分不同的小球 , 盒子是没有编号的 , 不需要进行区分盒子 ; 下面整理下不同的放球模型 :

球有编号 , 盒子没有编号 ( 不同的球放在相同盒子里 ) : 这是求集合划分问题 , Stirling 数 ; 这属于放球子模型 ;
球没有编号 , 盒子有编号 ( 相同的球放在不同盒子里 ) : 不定方程解问题 , 多重集组合问题 , 正整数剖分问题 ;
球有编号 , 盒子有编号 ( 不同的球放在不同的盒子里 ) : 多重集排列 , 指数函数问题 ;

\begin{Bmatrix} n \\ k \end{Bmatrix}

表示将

个元素分成

个子集的分法个数 ;

\begin{pmatrix} n \\ k \end{pmatrix}

表示从

个元素中选出

个小球的方案个数 ;

参考 : 百度百科-放球问题

三、Stirling 子集数递推公式

常见的 Stirling 子集数结果 :

\begin{Bmatrix} n \\ 0 \end{Bmatrix} = 0

将

个球放在

个不同的盒子里 , 有

种分法 ;

将

个元素分成

类 , 有

种分法 ; 就是没有方法 ;

\begin{Bmatrix} n \\ 1 \end{Bmatrix} = 1

将

个球放在

个不同的盒子里 , 有

种分法 ;

将

个元素分成

类 , 有

种分法 ; 相当于全域关系 ;

\begin{Bmatrix} n \\ 2 \end{Bmatrix} = 2^{n -1} - 1

将

个球放在

个不同的盒子里 , 有

2^n -1

种分法 ;

元集有

2^n

个不同的子集合 , 这是幂集的个数 , 每个子集合 , 与其补集都成对 , 因此有

2^{n-1}

对集合 , 其中要减去空集合与全集合的那一对 , 最终结果是

2^{n -1} - 1

;

\begin{Bmatrix} n \\ n-1 \end{Bmatrix} = C^n_2

将

个球放在

n-1

个不同的盒子里 , 有

C^n_2

种分法 ;

将

个元素分成

n-1

类 , 有两个元素算作一类 , 其它每个元素都自成一类 ; 只要将

个元素中属于一类的

个元素选出即可 , 有多少中选法 , 就有多少分类 ;

\begin{Bmatrix} n \\ n \end{Bmatrix} = 1

将

个球放在

个不同的盒子里 , 有

种分法 ;

将

个元素分成

类 , 有

种分法 ; 相当于恒等关系 ;

Stirling 子集数递推公式 :

\begin{Bmatrix} n \\ k \end{Bmatrix} = k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

将

个元素分为

类 , 先把一个元素挑出来 , 放在一边 , 还剩

n-1

个元素 ;

挑出的元素合并到其它类 : 将这

n-1

个元素分为

类 , 将挑出来的元素分别加入到

类中 ; 得到的总结果就是

个元素分为

类 , 挑出来的元素分别加入到

类中 , 有

种不同的方法 , 即分别加入到低

1,2,3, \cdots , k

类中 ;

挑出的元素自成一类 : 将

n-1

个元素分为

k-1

类 , 每个类都非空 , 然后让挑出来的元素自成一类 , 该自称一类的类与之前的

k-1

个类 , 合并在一起是

个类 ;

上述两种情况同时考虑 , 就是 Stirling 子集数的递推公式 ;

k\begin{Bmatrix} n-1 \\ k \end{Bmatrix}

含义 : 将

n-1

个元素分成

个子集

\begin{Bmatrix} n-1 \\ k \end{Bmatrix}

, 再加入第

个元素到其中之一有

种方案 , 在上述基础上乘以

;

\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

含义 : 将

n-1

个元素分成

k-1

个子集

\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}

, 剩下的第

个元素自然成为一个子集 ( 只有唯一一种方案 ) ;

四、Stirling 子集数示例 ( 四元集等价关系个数 )

求四元集上的等价关系个数 , 即

个元素分为

1, 2,3,4

类的分法相加 ;

\begin{Bmatrix} 4 \\ 1 \end{Bmatrix} + \begin{Bmatrix} 4 \\ 2 \end{Bmatrix}+ \begin{Bmatrix} 4 \\ 3 \end{Bmatrix}+\begin{Bmatrix} 4 \\ 4 \end{Bmatrix} = 1 + ( 2^{4-1} - 1 ) + C^4_2 +1 =1+7+6+1 = 15

四元集上的有序对个数是

4 \times 4 = 16

个 ;

四元集上的关系个数是

2^{16} =65536

个 ; 包含如下情况 , 含有

个有序对 , 含有

个有序对 ,

\cdots

, 含有

个有序对 ;

上面

65536

个二元关系中有

个是等价关系 ;

五、划分的二元关系加细关系

集族

\mathscr{A}

和集族

\mathscr{B}

都是集合

的划分 , 如果

\mathscr{A}

中每个划分块都包含于

\mathscr{B}

的某个划分块中 , 则称

\mathscr{A}

划分是

\mathscr{B}

划分的加细 ;

加细是一个二元关系 , 是划分之间的二元关系 ;

加细关系具有 :

自反省 : 每个划分是它自己的加细
传递性 :

\mathscr{A}

是

\mathscr{B}

的加细 ,

\mathscr{B}

是

\mathscr{C}

的加细 ,

\mathscr{A}

是

\mathscr{C}

的加细

没有对称性 : 加细不具有对称性
没有全域关系 : 有的划分之间互相都不是加细

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-10，如有侵权请联系 cloudcommunity@tencent.com 删除

百度

基础

集合

模型

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度