#### 期刊菜单

The New Equation Deduces the Counting Formula of Repeatable Combination under Arbitrary Conditions
DOI: 10.12677/AAM.2019.89182, PDF, HTML, XML, 下载: 815  浏览: 1,389

Abstract: Repeatable combination counting is an important content in combinatorial mathematics that has not been solved for hundreds of years. It is still controversial to prove the counting formulas under arbitrary conditions by using principle of inclusion and exclusion. In this paper, according to some new equations found, the counting formulas of repeatable combination under arbitrary conditions are derived. It is pointed out that there are a lot of similar equations. According to the set given by equality, the deficiency of this kind of problem proved by the principle of inclusion and exclusion is analyzed. A conjecture is given on the basis of a corollary.

1. 引言

2. 理论探讨

……

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{1}$ 的每一组非负整数解， ${x}_{1}$ 的值加 ${p}_{1}$ 可得到 $\left(\begin{array}{c}n+k-1-{p}_{1}\\ k-1\end{array}\right)$ 组不同的新解。

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{2}$ 的每一组非负整数解， ${x}_{2}$ 的值加 ${p}_{2}$ 可得到 $\left(\begin{array}{c}n+k-1-{p}_{2}\\ k-1\end{array}\right)$ 组不同的新解。

……

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{k}$ 的每一组非负整数解， ${x}_{k}$ 的值加 ${p}_{k}$ 可得到 $\left(\begin{array}{c}n+k-1-{p}_{k}\\ k-1\end{array}\right)$ 组不同的新解。

${s}_{1}=\left(\begin{array}{c}n+k-1-{p}_{1}\\ k-1\end{array}\right)+\left(\begin{array}{c}n+k-1-{p}_{2}\\ k-1\end{array}\right)+\cdots +\left(\begin{array}{c}n+k-1-{p}_{k}\\ k-1\end{array}\right)$ ，有 $\left(\begin{array}{c}k\\ 1\end{array}\right)$ 个式子相加，任意两个式子之间都可能存在相同的新解。

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{1}-{p}_{2}$ 的每一组非负整数解， ${x}_{1}$ 的值加 ${p}_{1}$${x}_{2}$ 的值加 ${p}_{2}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{1}-{p}_{2}\\ k-1\end{array}\right)$ 组不同的新解。 ${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{2}-{p}_{3}$ 的每一组非负整数解， ${x}_{2}$ 的值加 ${p}_{2}$${x}_{3}$ 的值加 ${p}_{3}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{2}-{p}_{3}\\ k-1\end{array}\right)$ 组不同的新解。

……

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{k-1}-{p}_{k}$ 的每一组非负整数解， ${x}_{k-1}$ 的值加 ${p}_{k-1}$${x}_{k}$ 的值加 ${p}_{k}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{k-1}-{p}_{k}\\ k-1\end{array}\right)$ 组不同的新解。

${s}_{2}=\left(\begin{array}{c}n+k-1-{p}_{1}-{p}_{2}\\ k-1\end{array}\right)+\left(\begin{array}{c}n+k-1-{p}_{2}-{p}_{3}\\ k-1\end{array}\right)+\cdots +\left(\begin{array}{c}n+k-1-{p}_{k-1}-{p}_{k}\\ k-1\end{array}\right)$ ，有 $\left(\begin{array}{c}k\\ 2\end{array}\right)$ 个式子相加，任意两个式子之间都可能存在相同的新解。

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{1}-{p}_{2}-{p}_{3}$ 的每一组非负整数解， ${x}_{1}$ 的值加 ${p}_{1}$${x}_{2}$ 的值加 ${p}_{2}$${x}_{3}$ 的值加 ${p}_{3}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{1}-{p}_{2}-{p}_{3}\\ k-1\end{array}\right)$ 组不同的新解。

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{2}-{p}_{3}-{p}_{4}$ 的每一组非负整数解， ${x}_{2}$ 的值加 ${p}_{2}$${x}_{3}$ 的值加 ${p}_{3}$${x}_{4}$ 的值加 ${p}_{4}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{2}-{p}_{3}-{p}_{4}\\ k-1\end{array}\right)$ 组不同的新解。

……

${x}_{1}+{x}_{2}+\cdots +{x}_{k}=n-{p}_{k-2}-{p}_{k-1}-{p}_{k}$ 的每一组非负整数解， ${x}_{k-2}$ 的值加 ${p}_{k-2}$${x}_{k-1}$ 的值加 ${p}_{k-1}$${x}_{k}$ 的值加 ${p}_{k}$ ，可得到 $\left(\begin{array}{c}n+k-1-{p}_{k-2}-{p}_{k-1}-{p}_{k}\\ k-1\end{array}\right)$ 组不同的新解。

${s}_{3}=\left(\begin{array}{c}n+k-1-{p}_{1}-{p}_{2}-{p}_{3}\\ k-1\end{array}\right)+\left(\begin{array}{c}n+k-1-{p}_{2}-{p}_{3}-{p}_{4}\\ k-1\end{array}\right)+\cdots +\left(\begin{array}{c}n+k-1-{p}_{k-2}-{p}_{k-1}-{p}_{k}\\ k-1\end{array}\right)$ ，有 $\left(\begin{array}{c}k\\ 3\end{array}\right)$ 个式子相加，任意两个式子之间都可能存在相同的新解。

……按照上述方法直到求出 ${s}_{b}$ 中的 $\left(\begin{array}{c}k\\ b\end{array}\right)$ 个式子相加，任意两个式子之间都可能存在相同的新解。在实际中 ${s}_{1},{s}_{2},\cdots ,{s}_{b}$ 都可能存在没有意义的式子，这样的式子等于零，没有意义的式子对应的方程没有非负整数解。

……

1)

2)

3)

……

b)

，有个式子相加。

，有个式子相加。

……

2)

3. 猜想

，有个式子相加。，有个式子相加。

，有个式子相加。

……

4. 容斥原理证法分析和问题推广应用

，从b个集合中取m个集合的交集之和是，m等于分别代入此式，或其它的式子，从不定方程解的数量可知与本文b个等式类似的等式大量存在 [7] 。b个等式就是一组方程，其解是唯一的，组成的b个集合也是唯一的，b个集合的交集是多样的，现在容斥原理证明与本文类似的问题时，没有给出具体的集合 [6] ，交集特征的描述也比较单一 [6] ，对应的集合是否存在还有疑问。容斥原理证明的过程中 [6] ，本文的理论却是否定的，集合中不存在两个x值不满足要求的解，但是组不同的新解中却存在。交集之和一般都存在多个相同的元素，交集之和的值中是否对应存在还需证明，容斥原理没有这方面的证明 [6] 。

5. 结论

 [1] 卢开澄, 卢华明. 组合数学[M]. 北京: 清华大学出版社, 2016. [2] [美]罗森(Rosen, K.H.). 离散数学及其应用[M]. 袁崇义, 屈婉玲, 王捍贫, 刘田, 译. 北京: 机械工业出版社, 2007. [3] [美]格里马迪(Grimaldi, R.). 离散数学与组合数学[M]. 林永钢, 译. 北京: 清华大学出版社, 2007. [4] 柯召, 魏万迪. 组合论(上) [M]. 北京: 科学出版社, 2010. [5] 谢胜利, 虞铭才, 黄月华. 离散数学基础[M]. 北京: 清华大学出版社, 2012. [6] 赵玉怀, 刘晓妮. 重复数有限的重复组合[J]. 榆林学院学报, 1992(4): 98-101. [7] 黄友谊. 特殊条件下可重复组合的计数[J]. 数学学习与研究, 2015(11): 98-99.