Question

排列组合：给定n个相同的集合，每个集合中有m个元素，从每个集合中任意选一元素，这些元素的组合数是多少

例如：n = 2， m = 2 ，假设集合S = {a, b} 时，一共有 aa，ab，bb，这3种不同的组合。求通式和过程

Answer 1

设这 m 个元素分别是 x1，x2，。。。，xm ，
考察 (x1+x2+....+xm)^n 的展开式，每一项对应一个组合 。

展开式的每一项都形如 (x1^i1)*(x2^i2)*....*(xm^im) ，其中 i1+i2+...+im=n ，
因此，所求的组合数就是方程 i1+i2+....+im=n 的非负整数解数。

考虑 m+n-1 个并排排列的石头子，任选其中 m-1 个做上标记 。这些标记把石头子隔成了 m 段（允许有的段中无石头子），各段的石头子数的和恰为 n 。
由此得，方程 i1+i2+...+im=n 的非负整数解数等于从 m+n-1 个元素里取 m-1 个元素的组合数，
即 C(m+n-1，m-1) 。
这就是你所要的答案 。它等于 (m+n-1)!/[(m-1)!*n!] 。