计算机问题求解 – Open topic 3.2 - 多重集合的组合问题 2017年03月21日

目录 引论：各种定义 问题转化：多重集合与不定方程 浅谈不定方程的解(多重集合的组合) 今天我从三个部分来介绍我要讲的问题： 多重集合的组合问题。

Chapter 1

多重集 定义：多重集或多重集合是数学中的一个概念，是集合概念的推广。在一个集合中，相同的元素只能出现一次，因此只能显示出有或无的属性。在多重集之中，同一个元素可以出现多次。 性质：多重集的势的计算和一般集合的计算方法一样，出现多次的元素则需要按出现的次数计算，不能只算一次。一个元素在多重集里出现的次数称为这个元素在多重集里面的重数（或重次、重复度）。

奇奇怪怪的定义和符号 1.S=｛k1·a1，k2·a2，k3·a3…..kn·an｝ 注：（ki·ai）表示ai这个元素的重数为ki。（就是有ki个ai元素） 2.S的r组合：S中的r个对象的无序选择；一个势为r的S的多重子集是r组合中的一个集合。 3.si= ｛x1·a1，x2·a2，x3·a3…..xn·an｝；∑xi=r. 好吧，下面内容就是我为了讲的方便做的定义。首先，我想引入一种表示方式，如第一条，ki·xi表示S中xi这个元素的重数为ki。 然后，引入一个概念：S的一个r组合：也就是S中的r个对象的无序选择，一个大小（也就是势）为r的S的多重子集是一个r组合。我用符号化的语言表示一下，也就是小si。这个小si就是r组合中的一个。举个例子： e.g. 设S=｛2·a，1·b，3·c｝，那么S的3组合是： ｛2·a，1·b｝，　｛2·a，1·c｝，　｛1·a，1·b，1·c｝，　｛1·a，2·c｝，　｛1·b，2·c｝，　｛3·c｝

Chapter 2

探讨的问题 1.S的k种类型的r组合的数量。 2. S=｛ ∞ ·a1， ∞ ·a2， ∞ ·a3….. ∞ ·ak｝ 3.si= ｛x1·a1，x2·a2，x3·a3…..xk·ak｝；∑xi=r. 4.x1=?;x2=?;x3=?......xn=?; Question:1.这些xi的组合是多少？？ 2.如果对xi有限制，那么这些xi的组合是多少？ 然后，我今天探讨的问题是这个多重集S的K种类型的r组合的数量，并且前提条件都是每一种类型的重数在原来的集合S里面是无限多的。

问题转化：多重集合与不定方程 1.si= ｛x1·a1，x2·a2，x3·a3…..xk·ak｝；∑xi=r. S的任意r组合均呈｛x1·a1，x2·a2，…，xk·ak｝的形式，其中x1+x2+…+xk=r。反过来，每个满足 x1+x2+…+xk=r的整数序列(sequence){x1，x2，…，xk}可对应于S的一个r组合 。 2.因此，不难构造一个双射f: ｛x1·a1，x2·a2，x3·a3…..xk·ak｝ → ｛x1，x2，x3…..xk｝ (这个两个大括号里面的元素考虑顺序) 因此，我们可以把这个多重集合的问题转化成不定方程的问题。 传送门1

Chapter 3

不定方程的非负整数解（3.2.4） 引理：设S是有k种类型对象的多重集合，每种元素均具有无限的重复数。那么S的r组合的个数等于C(r+k-1,k-1)（=C(r+k-1,r)）传送门1 转化后的问题： x1+x2+…+xk=r（1）的非负整数解个数。 证明： 隔板法之0-1序列： 00..00100….001….100…00 (2) x1个 x2个 xk个 （ ∑ xi=r） 构造0-1序列1，共有r个0，k-1个1.将第一个1前面的0的数量记做x1,第i个记做xi。 因此有x1+x2+…+xk=r。因此｛x1，x2，x3…..xk｝ 是（1）的非负整数解。这样，我们在方程(1)的非负整数解构成的集合与恰有r个0，（k-1）个1的0-1序列构成的集合之间建立了双射。 而这个0-1序列可由如下方式给定：先在r+k-1个位置上选r个位置安排0，然后其余位置放1. 因此，这样的0-1序列共有C(k+r-1,r)个。因此(1)的非负整数解共有C(k+r-1,r)个。 (当然也可以先选1的位置，这样的结果是C(r+k-1,k-1)，根据我们还剩下的组合知识，显然相等。) 好吧，首先，我先岔开来讲一个问题，这个问题你们刚刚应该听过/xk。就当我强化一下印象。 传送门2

不定方程的正整数解（3.2.5） Surjective functions from N to X, up to a permutation of N 对于S=｛ ∞ ·a1， ∞ ·a2， ∞ ·a3….. ∞ ·ak｝这个多重集合r组合子集si= ｛x1·a1，x2·a2，x3·a3…..xk·ak｝，其中∑xi=r，并且xi为正整数(xi≧1). 铺垫了那么多，来开始我应该讲的内容。

不定方程的正整数解（3.2.5） 问题：对于S=｛ ∞ ·a1， ∞ ·a2， ∞ ·a3….. ∞ ·ak｝这个多重集合r组合子集si= ｛x1·a1，x2·a2，x3·a3…..xk·ak｝，其中∑xi=r，并且xi为正整数(xi≧1). 转化后的问题： x1+x2+…+xk=r的正整数解个数。 解:(1)已知xi≧1，因此xi-1≧0. 令yi=xi-1.因此y1+y2+…+yk=r-k. 而yi是非负整数，自然而然的转化成(3.2.4) 传送门2 因此，共有C(r-1,r-k),或者C(r-1,k-1) 铺垫了那么多，来开始我应该讲的内容。 (2)如果r=k=0,就会产生矛盾。因为C(-1，0)=1;C(-1,-1)=0。前者正确还是后者正确？ 相当于空集里面取子集，有一种取法，就是取空集！ 因此前者正确

不定方程的有限制整数解（3.2.5.X） 不妨引入新变量y1=x1-3，y2=x2-1，y3=x3，y4=x4-5 此时方程变为 问题：方程x1+x2+x3+x4=20的整数解的个数是多少? 其中x1≥3，x2≥1，x3≥0，x4≥5 不妨引入新变量y1=x1-3，y2=x2-1，y3=x3，y4=x4-5 此时方程变为 y1+y2+y3+y4=11 根据3.2.4的结论，C(11+4-1,11)=C(14,11)=364

Thanks!