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

一、Stirling 子集数


Stirling 子集数 :


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

不同的放置方法总数是 :
{
n
k
}
begin{Bmatrix} n \ k end{Bmatrix}
{nk}
, 该数称为 Stirling 数 ;


n
n
n
元集分成
k
k
k
个非空子集 的 分法个数 ;

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

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

二、放球模型


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

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

在这里插入图片描述


{
n
k
}
begin{Bmatrix} n \ k end{Bmatrix}
{nk} 表示将
n
n
n
个元素分成
k
k
k
个子集的分法个数 ;


(
n
k
)
begin{pmatrix} n \ k end{pmatrix}
(nk) 表示从
n
n
n
个元素中选出
k
k
k
个小球的方案个数 ;

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

三、Stirling 子集数递推公式


常见的 Stirling 子集数 结果 :


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


n
n
n
个球放在
0
0
0
个不同的盒子里 , 有
0
0
0
种分法 ;


n
n
n
个元素分成
0
0
0
类 , 有
0
0
0
种分法 ; 就是 没有方法 ;


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


n
n
n
个球放在
1
1
1
个不同的盒子里 , 有
1
1
1
种分法 ;


n
n
n
个元素分成
1
1
1
类 , 有
1
1
1
种分法 ; 相当于 全域关系 ;


{
n
2
}
=
2
n

1

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


n
n
n
个球放在
2
2
2
个不同的盒子里 , 有
2
n

1
2^n -1
2n1 种分法 ;


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

1
2^{n-1}
2n1 对集合
, 其中要 减去 空集合 与 全集合 的那一对 , 最终结果是
2
n

1

1
2^{n -1} - 1
2n11 ;


{
n
n

1
}
=
C
n
2
begin{Bmatrix} n \ n-1 end{Bmatrix} = C_n^2
{nn1}=Cn2


n
n
n
个球放在
n

1
n-1
n1 个不同的盒子里 , 有
C
n
2
C_n^2
Cn2 种分法 ;


n
n
n
个元素分成
n

1
n-1
n1 类 , 有两个元素算作一类 , 其它每个元素都自成一类 ; 只要将
n
n
n
个元素中属于一类的
2
2
2
个元素选出即可 , 有多少中选法 , 就有多少分类 ;


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


n
n
n
个球放在
n
n
n
个不同的盒子里 , 有
1
1
1
种分法 ;


n
n
n
个元素分成
n
n
n
类 , 有
1
1
1
种分法 ; 相当于 恒等关系 ;

Stirling 子集数 递推公式 :


{
n
k
}
=
k
{
n

1
k
}
+
{
n

1
k

1
}
begin{Bmatrix} n \ k end{Bmatrix} = kbegin{Bmatrix} n-1 \ k end{Bmatrix} + begin{Bmatrix} n-1 \ k-1 end{Bmatrix}
{nk}=k{n1k}+{n1k1}


n
n
n
个元素分为
k
k
k
,
先把一个元素挑出来 , 放在一边 , 还剩
n

1

n-1
n1 个元素 ;

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

1
n-1
n1 个元素分为
k
k
k
类 , 将挑出来的元素分别加入到
k
k
k
类中 ; 得到的总结果就是
n
n
n
个元素分为
k
k
k
类 , 挑出来的元素分别加入到
k
k
k
类中
,
k
k
k
种不同的方法
, 即分别加入到低
1
,
2
,
3
,


,
k
1,2,3, cdots , k
1,2,3,,k 类中 ;

挑出的元素自成一类 :
n

1
n-1
n1 个元素分为
k

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

1
k-1
k1 个类 , 合并在一起是
k
k
k
个类 ;

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


k
{
n

1
k
}
kbegin{Bmatrix} n-1 \ k end{Bmatrix}
k{n1k} 含义 :
n

1
n-1
n1 个元素分成
k
k
k
个子集

{
n

1
k
}
begin{Bmatrix} n-1 \ k end{Bmatrix}
{n1k} , 再 加入第
n
n
n
个元素到其中之一 有
k
k
k
种方案
, 在上述基础上乘以
k
k
k
;


{
n

1
k

1
}
begin{Bmatrix} n-1 \ k-1 end{Bmatrix}
{n1k1} 含义 : 将
n

1
n-1
n1 个元素分成
k

1
k-1
k1 个子集

{
n

1

k

1
}
begin{Bmatrix} n-1 \ k-1 end{Bmatrix}
{n1k1} , 剩下的第
n
n
n
个元素自然成为一个子集 ( 只有唯一一种方案 ) ;

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


求四元集上的等价关系个数 ,
4
4
4
个元素分为
1
,
2
,
3
,
4
1, 2,3,4
1,2,3,4 类的分法相加 ;


{

4
1
}
+
{
4
2
}
+
{
4
3
}
+
{
4
4
}
=
1
+
(

2
4

1

1
)
+
C
4
2
+
1
=
1
+
7
+
6
+
1
=
15
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
{41}+{42}+{43}+{44}=1+(2411)+C42+1=1+7+6+1=15

四元集上的 有序对个数是
4
×
4
=
16
4 times 4 = 16
4×4=16 个 ;

四元集上的 关系个数是
2
16
=
65536
2^{16} =65536
216=65536
; 包含如下情况 , 含有
0
0
0
个有序对 , 含有
1
1
1
个有序对 ,

cdots
, 含有
16
16
16
个有序对 ;

上面
65536
65536
65536
个二元关系中有
15
15
15
个是等价关系 ;

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


集族
A
mathscr{A}
A
和 集族
B
mathscr{B}
B
都是 集合
A
A
A
的划分
,
如果
A
mathscr{A}
A
中每个划分块
都包含于
B
mathscr{B}
B
的某个划分块
中 , 则称
A
mathscr{A}
A
划分 是
B
mathscr{B}
B
划分 的加细 ;

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

加细关系具有 :

  • 自反省 : 每个划分是它自己的加细
  • 传递性 :
    A
    mathscr{A}
    A

    B
    mathscr{B}
    B
    的加细 ,
    B
    mathscr{B}
    B

    C
    mathscr{C}
    C
    的加细 ,
    A
    mathscr{A}
    A

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