IDEA激活码
文章目录
-
-
-
- 等价关系与划分对应问题
- 第二类斯特林数计算公式
- 4元集等价关系计算
- 6元集等价关系计算
-
-
等价关系与划分对应问题
等价关系 与 划分 计算 :
- 1.等价关于 与 划分 一一对应 : 非空集合
A
A
A 上的等价关系 与
A
A
A 上的划分是 一一对应 的 ;
(A
A
A 上有多少个 不同的 等价关系 , 就产生同样个数的不同的划分 )
- 2.数学模型 : 将
n
n
n 个不同的球 , 放入
r
r
r 个相同的盒子中 , 并且不能出现空盒 ,
n
≥
r
n \geq r
n≥r ; 不同的放球方法对应不同的划分数 ;
- 3.第二类 Stirling 数 : 将
n
n
n 个不同的球, 放入
r
r
r 个相同的盒子中 , 方案数记做
S
(
n
,
r
)
S(n,r)
S(n,r) , 或
{
n
r
}
\begin{Bmatrix} n \\ r \end{Bmatrix}
{nr} ;
第二类斯特林数计算公式
第二类 Stirling 数计算方法 :
- 1.Stirling 数计算公式 :
- ①
S
(
n
,
0
)
=
0
S(n,0) = 0
S(n,0)=0
- ②
S
(
n
,
1
)
=
1
S(n,1) = 1
S(n,1)=1
- ③
S
(
n
,
2
)
=
2
n
−
1
−
1
S(n,2) = 2^{n-1} - 1
S(n,2)=2n−1−1
- ④
S
(
n
,
n
−
1
)
=
C
(
n
,
2
)
S(n,n-1) = C(n, 2)
S(n,n−1)=C(n,2)
- ⑤
S
(
n
,
n
)
=
1
S(n,n) = 1
S(n,n)=1
- ①
- 2.Stirling 数递推公式 :
S
(
n
,
r
)
=
r
S
(
n
−
1
,
r
)
+
S
(
n
−
1
,
r
−
1
)
S(n,r) = rS(n-1, r) + S(n-1, r-1)
S(n,r)=rS(n−1,r)+S(n−1,r−1)
4元集等价关系计算
题目 : 等价关系
- 条件 : 集合
A
=
{
a
,
b
,
c
,
d
}
A = \{a,b,c,d\}
A={a,b,c,d} ;
- 问题 : 上述集合有多少等价关系 ;
解答 :
分析 :
-
1.有序对个数 : 集合
A
A
A 上有
4
×
4
=
16
4 \times 4 = 16
4×4=16 个有序对 ;
-
2.二元关系个数 : 集合
A
A
A 上的 二元关系 个数 是
2
有
序
对
个
数
=
2
16
2^{有序对个数} = 2^{16}
2有序对个数=216 个 ;
- ① 公式推演 : 每个二元关系有
0
0
0 到
16
16
16 个不等的有序对个数 , 分别统计 有
0
0
0 个有序对 ,
1
1
1 个有序对 ,
2
2
2 个有序对 ,
⋯
\cdots
⋯ ,
16
16
16 个有序对的 情况 ;
- ② 计算过程 :
C
(
16
,
0
)
+
C
(
16
,
1
)
+
C
(
16
,
2
)
+
⋯
+
C
(
16
,
16
)
=
2
16
C(16, 0) + C(16, 1) + C(16,2) + \cdots + C(16, 16) = 2^{16}
C(16,0)+C(16,1)+C(16,2)+⋯+C(16,16)=216 ;
- ① 公式推演 : 每个二元关系有
-
3.无法直接得出等价关系数 :
A
A
A 上有
2
16
2^{16}
216 个二元关系 , 逐个验证 等价关系 要求的 自反 , 对称 , 传递 性质 , 肯定行不通 , 计算量巨大 ;
-
4.求划分个数 : 集合
A
A
A 的 等价关系个数 与 划分个数 是一一对应的 , 因此求其划分个数即可 ;
分步求解 :
① 使用 第二类 Stirling 求其不同的划分个数 :
S
(
4
,
1
)
+
S
(
4
,
2
)
+
S
(
4
,
3
)
+
S
(
4
,
4
)
S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4)
S(4,1)+S(4,2)+S(4,3)+S(4,4)
② 根据公式 :
S
(
n
,
1
)
=
1
S(n,1) = 1
S(n,1)=1 , 计算 Stirling 数的值 :
S
(
4
,
1
)
=
1
S(4, 1) = 1
S(4,1)=1
③ 根据公式 :
S
(
n
,
2
)
=
2
n
−
1
−
1
S(n,2) = 2^{n-1} - 1
S(n,2)=2n−1−1 , 计算 Stirling 数的值 :
S
(
4
,
2
)
=
2
4
−
1
−
1
=
2
3
−
1
=
7
S(4, 2) = 2^{4 - 1} - 1 = 2^3 -1=7
S(4,2)=24−1−1=23−1=7
④ 根据公式1 :
S
(
n
,
n
−
1
)
=
C
(
n
,
2
)
S(n,n-1) = C(n, 2)
S(n,n−1)=C(n,2) ( Stirling 数计算公式 ) , 根据公式2 :
C
(
n
,
r
)
=
n
!
(
n
−
r
)
!
r
!
C(n, r) = \cfrac{n!}{(n-r)!r!}
C(n,r)=(n−r)!r!n! , 计算 Stirling 数的值 :
S
(
4
,
2
)
=
C
(
4
,
2
)
=
(
4
2
)
=
4
!
(
4
−
2
)
!
2
!
=
4
×
3
×
2
×
1
2
×
2
=
6
S(4, 2) = C(4,2) =\dbinom{4}{2} =\cfrac{4!}{(4-2)!2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6
S(4,2)=C(4,2)=(24)=(4−2)!2!4!=2×24×3×2×1=6
⑤ 根据公式 :
S
(
n
,
n
)
=
1
S(n,n) = 1
S(n,n)=1 , 计算 Stirling 数的值 :
S
(
4
,
4
)
=
1
S(4, 4) = 1
S(4,4)=1
⑥ 最终划分结果 :
A
A
A 上有 15 个划分 ;
S
(
4
,
1
)
+
S
(
4
,
2
)
+
S
(
4
,
3
)
+
S
(
4
,
4
)
=
1
+
7
+
6
+
1
=
15
S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 1 + 7 + 6 + 1 = 15
S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15
6元集等价关系计算
题目 :
- 条件 :
A
=
{
1
,
2
,
3
,
4
,
5
,
6
}
A=\{1,2,3,4,5,6\}
A={1,2,3,4,5,6}
- 问题 : 计算
A
A
A上的 二元关系 的 个数 和
A
A
A 上等价关系的个数 ;
解答 :
二元关系个数 :
- 1> 集合元素个数 : 集合
A
A
A 中有
6
6
6 个元素 ,
∣
A
∣
=
6
|A| = 6
∣A∣=6 ;
- 2> 有序对个数 :
∣
A
∣
×
∣
A
∣
=
6
×
6
=
36
|A| \times |A| = 6 \times 6 = 36
∣A∣×∣A∣=6×6=36 ;
- 3> 二元关系个数 :
- ① 推演过程 : 二元关系 包含
0
0
0 到
36
36
36 不等的有序对 , 那么需要考虑以上所有情况 , 分别统计 有
0
0
0 个有序对 ,
1
1
1 个有序对 ,
2
2
2 个有序对 ,
⋯
\cdots
⋯ ,
36
36
36 个有序对的 情况 ;
- ② 计算公式 :
C
(
36
,
0
)
+
C
(
36
,
1
)
+
C
(
36
,
2
)
+
⋯
+
C
(
36
,
36
)
=
2
36
C(36, 0) + C(36, 1) + C(36,2) + \cdots + C(36, 36) = 2^{36}
C(36,0)+C(36,1)+C(36,2)+⋯+C(36,36)=236
- ① 推演过程 : 二元关系 包含
等价关系个数 :
- 1> 一一对应 : 等价关系的个数 与 集合的划分数 是一一对应的 ,
- 2> 进行划分 : 将 集合
A
A
A 划分成
1
1
1 块 ,
2
2
2 块,
3
3
3 块,
4
4
4 块,
5
5
5 块,
6
6
6 块 ;
- 3>写出对应式子 : 集合的划分数为
S
(
6
,
1
)
+
S
(
6
,
2
)
+
S
(
6
,
3
)
+
S
(
6
,
4
)
+
S
(
6
,
5
)
+
S
(
6
,
6
)
S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6)
S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6)
逐个求出
S
(
6
,
1
)
+
S
(
6
,
2
)
+
S
(
6
,
3
)
+
S
(
6
,
4
)
+
S
(
6
,
5
)
+
S
(
6
,
6
)
S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6)
S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6) 每个 Stirling 数的值 ;
① 根据公式 :
S
(
n
,
1
)
=
1
S(n,1) = 1
S(n,1)=1 , 计算 Stirling 数的值 :
S
(
6
,
1
)
=
1
S(6, 1) = 1
S(6,1)=1
② 根据公式 :
S
(
n
,
2
)
=
2
n
−
1
−
1
S(n,2) = 2^{n-1} - 1
S(n,2)=2n−1−1 , 计算 Stirling 数的值 :
S
(
6
,
2
)
=
2
6
−
1
−
1
=
2
5
−
1
=
32
−
1
=
31
S(6, 2) = 2^{6-1} - 1 = 2^5 - 1 = 32 - 1 = 31
S(6,2)=26−1−1=25−1=32−1=31
③ 根据递推公式 :
S
(
n
,
r
)
=
r
S
(
n
−
1
,
r
)
+
S
(
n
−
1
,
r
−
1
)
S(n,r) = rS(n-1, r) + S(n-1, r-1)
S(n,r)=rS(n−1,r)+S(n−1,r−1) , 计算 Stirling 数的值 :
S
(
6
,
3
)
=
3
S
(
5
,
3
)
+
S
(
5
,
2
)
S(6, 3) = 3S(5,3) + S(5,2)
S(6,3)=3S(5,3)+S(5,2)
拆分成下面两部 进行计算 :
( 1 ) 先计算
S
(
5
,
3
)
=
3
S
(
4
,
3
)
+
S
(
4
,
2
)
S(5, 3) = 3S(4,3) + S(4,2)
S(5,3)=3S(4,3)+S(4,2)
- 1> 其中 使用公式
S
(
n
,
n
−
1
)
=
C
(
n
,
2
)
S(n, n-1) = C(n,2)
S(n,n−1)=C(n,2) 计算
S
(
4
,
3
)
S(4,3)
S(4,3) :
-
S
(
4
,
3
)
=
C
(
4
,
2
)
=
(
4
2
)
=
4
!
(
4
−
2
)
!
×
2
!
=
4
×
3
×
2
×
1
2
×
2
=
6
S(4,3) = C(4,2) = \dbinom{4}{2} = \cfrac{4!}{(4-2)! \times 2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6
S(4,3)=C(4,2)=(24)=(4−2)!×2!4!=2×24×3×2×1=6
-
- 2> 使用公式
S
(
n
,
2
)
=
2
n
−
1
−
1
S(n, 2) = 2^{n-1} - 1
S(n,2)=2n−1−1 计算
S
(
4
,
2
)
S(4,2)
S(4,2) :
-
S
(
4
,
2
)
=
2
4
−
1
−
1
=
7
S(4,2) = 2^{4-1} - 1 = 7
S(4,2)=24−1−1=7
-
- 3>
S
(
5
,
3
)
S(5, 3)
S(5,3) 结果 :
S
(
5
,
3
)
=
3
S
(
4
,
3
)
+
S
(
4
,
2
)
=
3
×
6
+
7
=
25
S(5, 3) = 3S(4,3) + S(4,2) =3\times 6 + 7 =25
S(5,3)=3S(4,3)+S(4,2)=3×6+7=25
( 2 ) 在计算
S
(
5
,
2
)
S(5,2)
S(5,2) 的结果 , 使用公式
S
(
n
,
2
)
=
2
n
−
1
−
1
S(n, 2) = 2^{n-1} - 1
S(n,2)=2n−1−1 进行计算 :
S
(
5
,
2
)
=
2
5
−
1
−
1
=
15
S(5, 2) = 2^{5-1} - 1 =15
S(5,2)=25−1−1=15
( 3 ) 最终结果 :
S
(
6
,
3
)
=
3
S
(
5
,
3
)
+
S
(
5
,
2
)
=
3
×
25
+
15
=
90
S(6, 3) = 3S(5,3) + S(5,2) = 3\times25 + 15 =90
S(6,3)=3S(5,3)+S(5,2)=3×25+15=90
④ 根据递推公式 :
S
(
n
,
r
)
=
r
S
(
n
−
1
,
r
)
+
S
(
n
−
1
,
r
−
1
)
S(n,r) = rS(n-1, r) + S(n-1, r-1)
S(n,r)=rS(n−1,r)+S(n−1,r−1) , 计算 Stirling 数的值 :
S
(
6
,
4
)
=
4
S
(
5
,
4
)
+
S
(
5
,
3
)
=
4
×
C
(
5
,
2
)
+
25
=
4
×
5
!
3
!
×
2
!
+
25
=
4
×
5
×
4
×
3
×
2
3
×
2
×
2
+
25
=
65
S(6, 4) = 4S(5,4) + S(5,3) = 4\times C(5,2) + 25 = 4\times \cfrac{5!}{3!\times2!}+25 = 4\times \cfrac{5\times4\times3\times2}{3\times2\times2}+25=65
S(6,4)=4S(5,4)+S(5,3)=4×C(5,2)+25=4×3!×2!5!+25=4×3×2×25×4×3×2+25=65
⑤ 根据公式 :
S
(
n
,
n
−
1
)
=
C
(
n
,
2
)
S(n, n-1)= C(n,2)
S(n,n−1)=C(n,2) , 计算
S
(
6
,
5
)
S(6,5)
S(6,5) :
S
(
6
,
5
)
=
C
(
6
,
2
)
=
6
!
(
6
−
2
)
!
×
2
!
=
6
×
5
×
4
×
3
×
2
4
×
3
×
2
×
2
=
15
S(6,5) = C(6,2) = \cfrac{6!}{(6-2)! \times2!} = \cfrac{6\times5\times4\times3\times2}{4\times3\times2 \times2} =15
S(6,5)=C(6,2)=(6−2)!×2!6!=4×3×2×26×5×4×3×2=15
⑥ 根据公式 :
S
(
n
,
n
)
=
1
S(n, n) = 1
S(n,n)=1 , 计算
S
(
6
,
6
)
S(6,6)
S(6,6) ;
S
(
6
,
6
)
=
1
S(6,6) = 1
S(6,6)=1
⑦ 将上面计算的
6
6
6 个斯特林数相加 , 得到的结果 :
S
(
6
,
1
)
+
S
(
6
,
2
)
+
S
(
6
,
3
)
+
S
(
6
,
4
)
+
S
(
6
,
5
)
+
S
(
6
,
6
)
=
1
+
31
+
90
+
65
+
15
+
1
=
203
S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6) = 1 + 31 + 90 + 65 + 15 + 1 =203
S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6)=1+31+90+65+15+1=203
