Download presentation
Presentation is loading. Please wait.
1
Twelvefold way 何伟
2
举几个栗子 不知道怎么开始讲，就先举几个计数的例子；例子很简单所以就直接放答案了。
3
𝑚 𝑛 (𝑚) 𝑛 假设我们有n个不同球，m个不同盒子 𝑚! 𝑛 𝑚 1、随便放，每个盒子可以容纳足够的球，不需要所有盒子都一定放满；
2、假设盒子的个数不小于球的个数，每个盒子至多装一个球； (𝑚) 𝑛 3、假设球的个数不小于盒子的个数，要求每个盒子至少装一个球； 1、每个球有m种选择，一共n个球，乘法原理； 2、用陶老师讲的list做，list的长度m相当于球的个数n，对于第j个球，有(m-j+1)种选择，然后累乘；降幂； 3、将n个球视为一个集合，分成m个blocks，S(n,m)，放入m个排列的盒子中，对于某一种分法分出的blocks我们有m!种放法放入盒子中. 𝑚! 𝑛 𝑚
4
将这个具体问题抽象化，把球看成是一个势为n的集合N，盒子看成是势为m的集合M，球放入盒子的过程视为N到M的一个映射;
三种不同限制条件的函数1，2，3， 球跟盒子有相同和不同之分，所以N，M分别有两种限制，两两组合四种，构成12种类型的计数问题，称之为twelvefold way;
5
Emmm这是weki给的12种问题解法，我们只介绍四种
6
假设集合N的势为n，集合X的势为x。 跟前面一样，只是把集合M换成X
7
SUM= 𝑥 𝑛 Functions from 𝑵 to 𝑿
元素从N映射到X，函数为任意的良定义函数。 N中的每个元素都有x种选法对应到X中的元素 SUM= 𝑥 𝑛 Function为arbitrary，即满足well-defined的任意函数，N，X未加说明为distinguishable 与第一个例子类似，N中的每个元素映射到X中有x种选择
8
Injective functions from 𝑵 to 𝑿
SUM= (𝑥) 𝑛 相当于把球放在盒子里，每个盒子最多装一个球 有个长度为n的list，第一个元素取法x种，第二个元素取法(x-1)种，第j个元素有(x-j+1)种取法，所以累乘起来就是x的降n次幂。
9
Injective functions from N to X, up to a permutation of N
等价于从X中取n个元素，有多少种组合 𝑥 𝑥−1 𝑥−2 …(𝑥−𝑛+1) 𝑛! 等价于choose n elements from X 如果考虑排列有𝑥 𝑥−1 𝑥−2 …(𝑥−𝑛+1)种 选取的元素共有n！种排列方式 所以一共有
10
Functions from N to X, up to a permutation of N
(𝑥+𝑛−1) 𝑥+𝑛−2 𝑥+𝑛−3 …𝑥 𝑛! 就是书上的multisets with n elements, 因为可重复，所以取一个后可以再补一个，最后一个不用补，可等价视为在（x+n-1）个元素中取n个元素 书上讲的有点迷，不太好理解
11
Thank you!
Similar presentations
