组合数量 (Permutation & Combination)

Scoutfai

问题是：
有n个东西，全部可以分成k个组，每个组里的东西的数量是：

第1组有m_1个东西
第2组有m_2个东西
第3组有m_3个东西
。。。 。。。
第k组有m_k个东西

就是说 m_1 + m_2 + m_3 + ... ... + m_k = n

每个组里的东西都是一样的。

那么，要在这n个东西里，
1）排出r个东西来（permutation, order important），有多少排法？
2）选出r个东西来（combination，order unimportant），有多少选法？

涉及的未知数都是非负整数（这说出来好像有点多余，但纯粹为严谨起见）。

嗯，用一个较容易想象的例子来示范一次：
有10个英文字母，能分成5组，亦即字母A有1个，字母B有1个，字母C有2个，字母D有3个，字母E有3个， （ABCCDDDEEE），从这10个英文字母里，
（1）若要排出4个字母，有多少排法？
（2）若要选出4个字母，有多少选法？

两题我都没有答案。例子可以不必回答，只是示范而已，重要的是一般公式。

我相信这种问题，应该有数学家已经在很久以前导出了答案，但我没接触过，也不知道这属于数学里的什么范围了。普通书里的permutation & combination 的项目没有讨论到如此复杂的情况。

各位指教了。

mathlim

这类题目我做过。
我没有办法导出一般的情况。
你给题目我就有办法解答。

Scoutfai

这类题目我做过。
我没有办法导出一般的情况。
你给题目我就有办法解答。
mathlim 发表于 9-12-2010 07:53 AM

我也做过这类型的特定题目（没有未知数）。嗯，我遇到过的题目是最多只有两种同样东西的情况，而这两种东西的各自的数目也不多，一两个，或三个而已。所用的方法是设定排法或选法里只有一个这种东西的时候，计算会有多少排法；然后设定排法或选法里只有两个这种东西的时候，计算会有多少排法；这样继续设定下去直到全部可能性被列出，然后将每个案例的答案总和起来，就拿到最后答案。

不知道你用的方法是不是这类型的？
如果是别的，可以用我附上的例子，示范一次吗？

mathlim

有10个英文字母，能分成5组，亦即字母A有1个，字母B有1个，字母C有2个，字母D有3个，字母E有3个， （ABCCDDDEEE），从这10个英文字母里，
（1）若要排出4个字母，有多少排法？
（2）若要选出4个字母，有多少选法？

（1）分四种情况：
Ⅰ。三个相同
2C1×3C1

Ⅱ。两个两个相同
3C2

Ⅲ。两个相同两个不同
3C1×4C2

Ⅳ。四个不同
5C4

（2）只要乘上排列数即可
Ⅰ。三个相同
2C1×3C1×(4!/3!)

Ⅱ。两个两个相同
3C2×(4!/2!2!)

Ⅲ。两个相同两个不同
3C1×4C2×(4!/2!)

Ⅳ。四个不同
5C4×(4!)

puangenlun

回复 4# mathlim


   是不是1和2次序調轉了？

Scoutfai

有10个英文字母，能分成5组，亦即字母A有1个，字母B有1个，字母C有2个，字母D有3个，字母E有3个， （ABCCDD ...
mathlim 发表于 10-12-2010 06:49 AM

不知道你认不认为这类方法有缺点？
那就是，当数目越来越大的时候，就会超出人的直觉范围，到最后也不敢肯定是对或错（因为无法保证每一种情况都被考虑到）。
当数目小时，还可以很直觉的肯定会有什么样的情况发生。

还是你已经发展出了一套方法，无论数目多大，你都有能力肯定每一种情况都被考虑到？若是，可否分享一下。

mathlim

回复 5# puangenlun


是啊！的确是对调了！通常我们先处理选法，再考虑排列数。谢谢！

mathlim

回复 6# Scoutfai


排列组合，要的就是掌握规律。
掌握规律，就不会重复，也不会遗漏。
比如选8个，规律如下：
8
71
62
611
53
521
5111
44
431
422
4211
41111
332
3311
3221
32111
311111
2222
22211
221111
2111111
11111111

Scoutfai

回复  Scoutfai


排列组合，要的就是掌握规律。
掌握规律，就不会重复，也不会遗漏。
比如选8个，规 ...
mathlim 发表于 10-12-2010 06:20 PM

这个数阵是怎样用的？

mathlim

回复 9# Scoutfai

8：8个相同
71：7个相同1个不同
62：6个相同2个相同
...
...
32111：3个相同2个相同3个不同
...
...
221111：2个相同2个相同4个不同
...
...
11111111：8个不同

Scoutfai

回复  Scoutfai

8：8个相同
71：7个相同1个不同
62：6个相同2个相同
...
...
32111：3个相同2个相 ...
mathlim 发表于 11-12-2010 12:14 PM

明白了。谢谢。
这个逻辑，理应可以沿用到一般情况去，可是就怎么找不到头绪！？
你是正在读纯数学系的吗？有没有讲师是这领域的专家？

mathlim

我是数学系毕业的。
目前是一个中学老师。

Scoutfai

我是数学系毕业的。
目前是一个中学老师。
mathlim 发表于 13-12-2010 06:35 AM

原来是为人师表了。你还有跟大学里的这方面的讲师有联系吗？如果有，可否帮我询问他们？

Scoutfai

其他人不知道有什么想法呢？
难道这种问题也和大多数的Differential Equation一样，只有numerical solution，没有analytical solution?

mathlim

回复 13# Scoutfai

我在大学混了四年，数学知识没有什么增加，只是某些老师给了我一些启示。
我也没有再跟大学联系，大部分老师也换了！

Scoutfai

看来这一题是解不开谜底了。

尽善尽美

这一题应该是中学题吧

我试试看

1. 10P4/（2！*3！*3！）
2. 10C4/（2！*3！*3！）

Scoutfai

这一题应该是中学题吧

我试试看

1. 10P4/（2！*3！*3！）
2. 10C4/（2！*3！*3！）
尽善尽美 发表于 22-12-2010 02:11 AM

国中的课程纳要是不会给太多duplicates的。独中可能会有吧。到国立中六就有时会遇到两种或三种duplicates的题目。
若是有给数目，确实不会难，顶多是过程长吧了。但现在我要求的是general formula，难度提高了很多哦。

不好意思，你的答案不正确，方法应和上面讲的一样。必须case by case处理，也就是我会说过程长的原因。