Twelvefold way 十二种计数原理

Presentation on theme: "Twelvefold way 十二种计数原理"— Presentation transcript:

1 Twelvefold way 十二种计数原理
谢逸

2 Overview In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer. The twelvefold way是一个计数问题的分类框架

3 我们规定，N和X均为有限集，n=|N|和x=|X|是集合的势，也就是说N为n元集，X是x元集，考虑f:N→X。
3种函数类型：无条件的，单射的，满射的 4种等价关系： equality;完全相同才等价 equality up to a permutation of {N}; N中元素的不同排序皆等价 equality up to a permutation of {X}; X中元素的不同排序皆等价 equality up to permutations of {N} and {X}. N和X中元素的不同排序皆等价 根据乘法原理，总共12种情况，也就是我们所说的twelvefold way

4 Functions from N to X Injective functions from N to X Injective functions from N to X, up to a permutation of N Functions from N to X, up to a permutation of N Surjective functions from N to X, up to a permutation of N Injective functions from N to X, up to a permutation of X Injective functions from N to X, up to permutations of N and X Surjective functions from N to X, up to a permutation of X Surjective functions from N to X Functions from N to X, up to a permutation of X Surjective functions from N to X, up to permutations of N and X Functions from N to X, up to permutations of N and X

5

6 Case 1 Function from N to X：
等价于在没有限制的情况下数X中n元序列的个数。函数f: N→X取决于集合N中n个元素的所对应对的值，而每个元素所对应的值可以在集合X中任选一个。

7 Example 1 N={p,q}, X={a,b,c}, 那么可能的情况： (a,a),(a,b),(a,c),(b,a),(b,b)(b,c),(c,a),(c,b),(c,c) 可能的情况有 |(a,a),(a,b),(a,c),(b,a),(b,b)(b,c),(c,a),(c,b),(c,c)| =32=9.

8 Conclusion 1 Function from N to X has a total of xn possibilities.
每个N中元素可能映射到x个X中的元素 故总共种xn可能

9 Case 2 Injective(单射) functions from N to X 等价于数n个X中不同元素元素的序列
即n-permutation of X 不能重复！！！

10 Example 2 N={p,q}, X={a,b,c,d}, 那么可能的情况： (a,b),(a,c),(a,d),(b,a),(b,c)(b,d), (c,a),(c,b),(c,d),(d,a),(d,b),(d,c) 可能的情况有42=12

11 Conclusion 2 可能的情况有xn种. 理由：每个元素比前一个少一种选择，因此是x(x-1)……(x-n+1)= xn（x的n阶下降阶乘）

12 Case 3 Injective functions from N to X, up to a permutation of N 单射
等价于数集合X的n元子集

13 Example 3 N={p,q}, X={a,b,c,d}, 那么可能的情况：
(a,b),(a,c),(a,d),(b,c)(b,d),(c,d),(d,a),(d,b),(d,c) 可能的情况有42/2!=6种。

14 Conclusion 3 可能的情况有 从等价类的角度想，全集为所有单射情况，即case2，同样的n个元素的不同排列形成一个等价类，每个等价类的元素个数为n!，因此在case 2的基础上除去n!

15 Case 4 Functions from N to X, up to a permutation of N

16 等价于数X中的n元多重集（multiset）
(Multiset：同一元素可出现多次，与顺序无关。(a,b)与(b,a)同, (a,a,b)与(a,b,b)不同) 为什么呢？

17 我们把这个问题形象化一下 其实就是书架问题的变化： 集合N中的元素看做n本书，把集合X中的元素看做书架。
f把N中的每个元素映射到X中，也就是把n本书放到x个架子上。 N中元素的不同排列是等价的，也就是说n本书是相同的。

18 Example 4 N={p,q}, X={a,b,c}, 那么可能的情况： (a,a),(a,b),(a,c),(b,b)(b,c),(c,c) 可能的情况有6种。 等价于把p,q这两本相同的书放在a,b,c三个书架上。可以全在书架a上(a,a)，全在b上(b,b)，全在c上(c,c),一本在a上一本在b上(a,b),一本在a上一本在c上(a,c),一本在b上一本在c上(b,c)。

19 Conclusion 4 可能的情况有

20 我们可以回顾一下之前的书架问题 每放置一本书，可以将该书理解为一个隔板，增加了一层书架。
如果将书和隔板看做一个对象，问题就转换为从x-1 (隔板)+n(书)个元素中，取n个元素的方法数。也就是 𝑥+𝑛−1 𝑛

21 或者用商集的观点来考虑： 先考虑n本不同的书 x-1个格挡和n本不同的书进行排列，总排列数是 (x-1+n)！ 在(x-1+n)!个排列构成的集合中，定义等价关系为：仅仅是格挡的置换而导致的不同排列(list)是等价的（实际上，确实可以忽略格挡的不同）。则等价类元素个数就是(x-1)!, 商集个数就是(x-1+n)! / (x-1)!。 而事实上书是一样的，因此书的顺序改变也是等价的，等价类的大小为n!，商集个数为 𝑥+𝑛−1 𝑛

22 感兴趣的同学可以上https://en. wikipedia
感兴趣的同学可以上 BB%84%E5%90%88%E6%95%B0%E5%AD%A6_(Fall_2011)/Basic_enumeration#Subsets_of_fixed_size获取更多资讯