组合

集合的组合(子集)
设S是n元素集合。集合S的一个组合通常表示集合S的元素的一个无序选择。这样一个选择的结果是S的元素构成的一个子集。因此，S的一个组合就是S的子集的一个选择。因此，术语组合与子集本质上是可以互换的，通常我们使用更熟悉的子集而不使用略显笨拙的组合，除非要强调选择的过程。

我们用 表示n元素集合的r子集的数目。显然还有，容易看出，对于每一个非负整数n，下述事实成立。

特别地。下面的定理给出r子集数目的基本公式。

定理：
对于。

例子
在平面上给出25个点使得没有3个点共线。这些点确定多少条直线？确定多少个三角形？
有15个人选修了一门数学课程，但在给定的一天恰有12位学生听课，选出12名学生的不同方法数是多少？如果教室内有25个座位，那么这12名学生可能就座的方法数目是多少？
推论
对于 。

定理(帕斯卡公式)
对于所有满足 的整数n和k，有 。

定理
对于 。

多重集合的组合
如果S是多重集合，那么S的r组合是S中r个对象的无序选择。因此，S的一个r组合本身也是一个多重集合，它是一个大小为r的S的多重子集，或者简单说来，是一个多重r子集。如果S有n个对象，那么S只有一个n组合，即S自己。如果S含有k种不同类型的对象，那么S就有k个1组合。与集合的组合不同，通常我们使用组合而不是多重子集。
定理
设S是有k种类型对象的多重集合，每种元素具有无限的重复数，那么S的r组合的个数等于。

对于 ,S任意r组合均呈的形式，其中皆为非负整数，且。反过来，每个满足的非负整数序列 ，对应于S的一个r组合。因此，S的r组合的个数等于方程的非负整数解的个数。

例子
项取自1,2,…,k的长度为r的非递减序列的个数是多少？
设S是有4种对象a,b,c,d的多重集每一种类型的对象至少出现一次的S的10组合的个数有多少？

带重复的组合
我们已经把多重集合的r组合的数目确定为两个“极端”的情况：

2 

对于一般的情形任然有效。