3.2.5 Surjective functions from N to X, up to a permutation of N

Presentation on theme: "3.2.5 Surjective functions from N to X, up to a permutation of N"— Presentation transcript:

1 3.2.5 Surjective functions from N to X, up to a permutation of N
OPEN TOPIC 匡舒磊 Surjective functions from N to X, up to a permutation of N Begin

2 Introduction This case is equivalent to counting multisets with n elements from X, for which each element of X occurs at least once. This is also equivalent to counting the compositions of n with x (non-zero) terms, by listing the multiplicities of the elements of x in order.

3 Methods from Wiki

4 Stars and bars First choose a total ordering of the sets N and X, and note that by applying a suitable permutation of N, every surjective function N → X can be transformed into a unique weakly increasing (and of course still surjective) function. If one connects the elements of N in order by n − 1 arcs into a linear graph, then choosing any subset of n − x arcs and removing the rest, one obtains a graph with x connected components, and by sending these to the successive elements of X, one obtains a weakly increasing surjective function N → X; also the sizes of the connected components give a composition of n into x parts. This argument is basically the one given at stars and bars, except that there the complementary choice of x − 1 "separations" is made 第一步：把k个球放在k个盒子中(每盒1个)。这样，我们满足了限制条件③，并且方案只有一种，所以最后乘上1。 第二步：这时手上还剩(n-k)个球，由于每个盒子已经有一个球了，这(n-k)个球就可以以限制条件①来分配。那么这(n-k)个球的分配方案就是状态4了。套用状态4的公式有F=C(n-k+k-1，n-k)·1=C(n-1，n-k)。其实C(n-1，n-k)是等于C(n-1,k-1)的，众所周知，组合中，C(n,r)= C(n,n-r)。由于(n-k)+(k-1)=n-1,所以C(n-1，n-k)= C(n-1,k-1)。 Lorem ipsum dolor sit amet

5 counting the compositions of n with x (non-zero) terms
x1+x2+…+xk=n

6 正整数分拆

7 正整数的分拆 把n分为k个正整数之和的一种表示方法叫做n的一个k部分拆，其个数记为p(n, k) 在有序分拆中，考虑分拆部分求和之间的顺序。
有序分拆与无序分拆 把n分为k个正整数之和的一种表示方法叫做n的一个k部分拆，其个数记为p(n, k) 在有序分拆中，考虑分拆部分求和之间的顺序。 假定x1+x2+…+xk=n，xi之间不同的排序记为不同的方案，称之为n的有序k拆分，如3的有序2拆分为：3=1+2=2+1。 (Surjective functions from N to X, up to a permutation of N) 在无序拆分中，不考虑其求和的顺序。一般假定xi 递减，我们称之为n的无序k拆分，如3的无序k拆分为：3=1+2。这种拆分可以理解为将n个无区别的球分为r份且每份至少有一个球。(Surjective functions from N to X, up to a permutation of X) 一般情况下，无序拆分的个数用 p(n) 表示，则 p(2)=1，p(3)=2，p(4)=4。 在通常情况下，整数分拆是指整数的无序分拆。 Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm.

8 正整数的分拆 P(n, k) = p (n-1, k-1) + p(n-k, k)
有序分拆与无序分拆 P(n, k) = p (n-1, k-1) + p(n-k, k) P(n+k, k) = p(n, 1)+p(n, 2)+…+p(n, k) P(n, k) = 𝑛 𝑘−1 𝑘−1 !𝑘! + 𝑅 𝑘−2 (𝑛) Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm.

9 Ferrers 示图 n的k部分拆的个数p(n, k) 等于n 的最大分部为k的个数
无序分拆 n的k部分拆的个数p(n, k) 等于n 的最大分部为k的个数 就是将行与列倒换 后一分拆叫做前一分拆的共轭分拆 Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm. (6, 3, 3, 2) (4, 4, 3, 1, 1, 1)

10 正整数的分拆 1≤𝑛≤𝑘 𝐶 𝑘 m 𝑛−1 =0 𝑛=𝑘+1 𝐶 𝑘 m 𝑛−1 =1 𝑜𝑟 0
有序分拆与无序分拆 对于给定的正整数j和m，设 𝐶 𝑘 m (𝑛−1)表示把正整数n分拆成恰有m个部 分且分布量都大于k后的有序分拆数 1≤𝑛≤𝑘 𝐶 𝑘 m 𝑛−1 =0 𝑛=𝑘 𝐶 𝑘 m 𝑛−1 =1 𝑜𝑟 0 𝑛≥𝑘+2⋀𝑚= 𝐶 𝑘 m 𝑛−1 =1 𝑛≥𝑘+2∧𝑚>1 𝐶 𝑘 m 𝑛−1 = 𝐶 𝑘 m 𝑛−2 + 𝐶 𝑘 m−1 (𝑛−𝑘−2) Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy. Lorem ipsum dolor sit amet, consectetuer. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonumm.

11 分配问题

12 分配问题 ①每个盒子中的球爱放几个放几个，也可以不放 ②每个盒子要么不放，要么放一个（可以知道拿来装球的盒子数就是n个）
——12态 ①每个盒子中的球爱放几个放几个，也可以不放 ②每个盒子要么不放，要么放一个（可以知道拿来装球的盒子数就是n个） ③每个盒子起码放一个。

13 分配问题 How to prove it？ Creative Flying High Strong

14 Thanks