排列组合（Combinatorics）是组合数学中的基础概念，主要研究从给定有限集合中选取元素的方法以及这些方法的计数问题。排列与组合的核心区别在于是否考虑元素的顺序：排列强调元素的顺序性，而组合则不考虑元素的顺序。

排列组合的思想源远流长，其早期萌芽可见于不同文明的数学实践中。

在《易经》的八卦、六十四卦中，蕴含着组合的思想。古代的河图洛书也体现了数理组合的萌芽。南宋数学家秦九韶在其著作《数书九章》中提出了“叠积术”，用于解决组合问题，与组合数计算密切相关。

公元6世纪，印度医学家苏什鲁塔（Sushruta）在其医学著作《苏什鲁塔本集》（Sushruta Samhita）中讨论了六种不同味道（甜、酸、咸、苦、辣、涩）的组合问题，这被认为是世界上最早的组合计数记录之一。印度数学家婆罗摩笈多（Brahmagupta）在其著作中也讨论了组合问题，并给出了类似组合数公式的计算方法。

中世纪时期，印度和阿拉伯数学家继续对排列组合公式进行研究。例如，在13世纪，波斯数学家纳西尔丁·图西（Nasir al-Din al-Tusi）在其著作中详细讨论了组合数，并给出了帕斯卡三角的早期形式。

17世纪，法国数学家布莱兹·帕斯卡（Blaise Pascal）和皮埃尔·德·费马（Pierre de Fermat）在研究“赌博问题”时，通过通信交流，共同奠定了概率论和组合数学的基础，并系统地发现了帕斯卡三角（杨辉三角）的性质。德国数学家戈特弗里德·威廉·莱布尼茨（Gottfried Wilhelm Leibniz）在其1666年出版的《论组合的艺术》（Dissertatio de Arte Combinatoria）中，首次将排列组合理论作为一个独立的数学分支进行探讨。

18世纪，莱昂哈德·欧拉（Leonhard Euler）在图论、整数划分等领域对组合数学做出了巨大贡献。雅各布·伯努利（Jacob Bernoulli）在其《猜度术》（Ars Conjectandi）中系统阐述了排列组合理论，并将其应用于概率论。现代组合数学已发展成为一个庞大且活跃的数学分支，与计算机科学、统计学等领域的联系日益紧密。

计数原理是排列组合问题的基础，主要包括加法原理、乘法原理。

完成一件事情有类不同的方法，且这类方法中的任意两类都不能同时发生(即相互独立),如果第 1 类方法有种，第 2 类方法有种，...,第类方法有种，那么完成这件事情的总方法数为种。

加法原理适用于解决分类问题，即当一个任务可以通过几种互斥的途径完成时，总方法数是各途径方法数之和。常与逻辑连接词“或”相关联。

从 A 地到 B 地，可以选择乘坐火车、轮船或飞机。若有 7 班火车、6 班轮船和 5班飞机，则从 A 地到 B 地共有种不同的走法。

完成一件事情需要经过个步骤，且每个步骤都必须完成(即各步骤相互依赖), 如果完成第 1 个步骤有种方法，完成第 2 个步骤有种方法，..., 完成第个步骤有种方法，那么完成这件事情的总方法数为种。

乘法原理适用于解决分步问题，即当一个任务需要连续完成多个步骤时，总方法数是各步骤方法数之积。常与逻辑连接词“且”相关联。

从 A 地经 B 地到 C 地，若 A 到 B 有 3 条不同的路，B 到 C 有 2 条不同的路，则从A 地经 B 地到 C 地共有种不同的走法。

阶乘是数学中的一个运算符号，表示一个正整数的阶乘是所有小于及等于的正整数的积，写作。其定义为：

为了数学公式的自洽性，特别规定。这一规定在组合数和排列数的公式中尤为重要，确保了当或时的公式普遍适用性。

从个不同的元素中，取出个元素，并按照一定的顺序排成一列， 所得到的不同排列方法数称为排列。排列强调元素的顺序性，即元素的选择及其在序列中的位置都影响最终结果。因此，当“顺序重要”时，应使用排列来计数。

排列数通常用符号(国内常用)或表示。其中，代表元素的总数，代表每次取出的元素个数。

从个不同元素中取出个元素进行排列，可以分步完成：

1.选择第一个元素有种方法。

2. 选择第二个元素有种方法(因为已取出一个)。

3. ……

4.选择第个元素有种方法。

根据乘法原理，总的排列方法数为：

将上述乘积形式用阶乘表示，得到排列数公式：

定义：从个不同元素中取出全部个元素，按照一定的顺序排成一列，所得到的排列称为全排列。

公式：全排列是排列数公式中的特殊情况。

定义：从个不同元素中，每次允许重复选取元素，取出个元素进行排列。

公式：由于每次选取都有种选择，且可以重复，根据乘法原理，可重复排列的公式为：

举例：用 0-9 这 10 个数字组成一个 4 位数的密码，数字可以重复，则共有种不同的密码。

定义：在个元素中，若有种不同类型的元素，其中第一种类型有个相同元素，第二种类型有个相同元素，...，第种类型有个相同元素，且。求这个元素进行全排列的方法数。

公式：

举例：单词 success 共有 7 个字母，其中s有3个，c有2个，u有1个，e有 1个。则这些字母可以组成的不同排列数为种。

定义：将个不同元素排成一个圆圈，由于旋转后视为同一种排列，因此圆排列的计数方式与直线排列不同。

公式：

定义：将个元素进行排列，使得每个元素都不在它原来的位置上，这样的排列称为错位排列。通常用表示。

递推公式：

错位排列的递推公式可以按照如下思路推导：第个元素不能放在它原本的位置(位置)，因此它只能选择位置1到位置中的任意一个 (如放在位置)；此时分两种情况，一是将原位置的元素放在位置，剩余个元素错位排列(对应)，二是原位置的元素不放在位置，此时等效于个元素错位排列(对应)；两种情况总和乘以(即第个元素的选择数)，即得个元素的错位排列数：

，其中。

由递推公式可得：

通项公式：

由递推公式可推导出错位排列的通项公式：

举例：有封信和个信封，每封信都有其对应的正确信封。如果要求每封信都装错了信封，则共有种装法。

从个不同的元素中，取出个元素，不考虑顺序地并成一组，所得到的不同选取方法数称为组合。组合强调元素的集合性，即只关注选择了哪些元素而不关心它们的排列次序。因此，当“顺序不重要”时，应使用组合来计数。

组合数通常用符号或表示。其中，代表元素的总数，代表每次取出的元素个数。读作“选”。

从个不同元素中取出个元素的排列数，可以看作是先从个元素中选出个元素(组合),然后再将这个元素进行全排列。因此，排列数等于组合数乘以个元素的全排列数：

由此可得组合数公式：

将排列数公式代入，得到组合数公式：

从个元素中选取个元素组成一个组合，等价于从个元素中选取个元素舍弃。因此，选取个元素的组合数与选取个元素的组合数相等。

帕斯卡恒等式揭示了组合数之间的递推关系，是构造杨辉三角 (Pascal's Triangle)的基础。

证明：考虑从个元素中选取个。可以将这个元素中的某一个特定元素分为两类情况：

1. 选取的个元素中包含元素：此时还需要从剩下的个元素中选取个，方法数为。

2. 选取的个元素中不包含元素：此时需要从剩下的个元素中选取个，方法数为。

根据加法原理，总的组合数为。

从个元素中选取任意数量的元素 (包括不选和全选)的所有组合数之和为。

证明：考虑一个有个元素的集合，每个元素都有“选中”或“不选中”两种状态。因此，总共有种不同的子集(组合)选择方式。

定义：从种不同元素中，允许重复选取，取出个元素组成一个组合。

公式(隔板法)：可重复组合数可以通过“隔板法”转化为普通组合问题。将个待选元素看作个“球”, 将种不同元素之间的界限看作个“隔板”。问题转化为将个球和个隔板进行排列，总共有个位置，从中选择个位置放球(或选择个位置放隔板)。

举例：将5个完全相同的苹果分给 3个不同的人，每人至少可以分到 0 个苹果，则共有种分法。

排列与组合的核心区别在于有序性。排列考虑元素的顺序，而组合不考虑元素的顺序。简而言之，当“顺序重要”时，是排列问题；当“顺序不重要”时，是组合问题。二者的区别举例如下：

排列与组合之间存在密切关系：一个排列可以看作是先进行组合，再进行全排列。即先从个元素中选出个元素(组合)，然后将这个元素进行全排列。

排列组合是计算古典概型中事件发生概率的基础工具，用于确定样本空间中基本事件的总数（作为分母）和特定事件所包含的基本事件数（作为分子）。

一个袋中有 5 个红球和 3 个白球，从中任取 2 个球。求恰好取到 1 个红球和 1 个白球的概率。

总事件数：从8个球中任取 2个，不考虑顺序，为种。

特定事件数：从 5 个红球中取 1 个()且从 3 个白球中取 1 个()，根据乘法原理，为种。

概率：。

某彩票从 36 个号码中选择 7 个作为中奖号码。计算中得头奖（7 个号码全中）的概率。

总事件数：从 36 个号码中选 7 个，不考虑顺序，为种。

特定事件数：中得头奖只有 1 种情况。

概率：。

5 个人排队，其中甲和乙必须站在一起。将甲和乙看作一个整体“捆绑”,则相当于4 个元素进行全排列，有种排法。同时，甲和乙内部可以互换位置， 有种排法。根据乘法原理，总排法数为种。

5 个人排队，其中甲和乙不能站在一起。可以先将除了甲乙之外的3 人排好，有种排法。这 3 人之间及两端共有 4 个空位，将甲和乙插入这 4 个空位中的 2 个，有种排法。根据乘法原理，总排法数为种。

有5个人，要坐到8个不同的座位上，每人一个座位。这相当于从8个座位中选出 5 个进行排列，有种坐法。

将 5 本不同的书分给 3 个不同的人，每人至少分一本。这是一个复杂的分配问题，通常需要结合容斥原理或分步讨论。例如，可以先将 5 本书分成 3 组，再将这 3 组书分给 3 个人。分组方式有: (3,1,1) 和 (2,2,1)。

(3,1,1) 分组：种。再分给 3 人，有种。

(2,2,1) 分组: 种。再分给 3 人，有种。

总计种分法。

将6名学生分成3组：

平均分配：分成 3 组，每组 2人。先选组，再选组，最后组。由于组间无序，需要除以。所以有种分法。

不平均分配：分成 3 组，分别为 1 人、2 人、3 人。先选人，再选人，最后人。由于组间有明确的人数区分，组间有序，不需要除以。所以有种分法。

将 10 个相同的苹果分给 3 个小朋友，每个小朋友至少分到一个苹果。这相当于在10 个苹果之间的 9 个空隙中插入个隔板，将苹果分成 3 份。方法数为种。

在一个的棋盘格上，从左下角走到右上角，每次只能向上或向右走一步，求最短路径数。总共需要走步向右和步向上，总步数为步。

问题转化为从步中选择步向右（或步向上）的位置。方法数为或。

平面上有个点，其中任意三点不共线。求这些点能确定多少条直线和多少个三角形。

直线条数：每两点确定一条直线，顺序不重要，所以是条。

三角形数：每三点确定一个三角形，顺序不重要，所以是个。

二项式定理揭示了展开式的系数与组合数的关系。展开式中的每一项的系数正是，表示从个因子中选择个(或个) 的组合数。

例如，求展开式中的系数。根据二项式定理，该项系数为。

组合数学 (Combinatorics)是数学的一个分支，主要研究离散对象的计数、构造、存在性和优化问题。排列组合是组合数学最基本和核心的组成部分。

鸽巢原理(PigeonholePrinciple)(或抽屉原理)是组合数学中一个简单而重要的原理。它指出，如果将个物品放入个盒子中，且，那么至少有一个盒子包含不止一个物品。该原理常用于证明某些数学结论的存在性。

容斥原理 (Inclusion-Exclusion Principle)是一种用于计算多个集合并集大小的计数方法。它通过对各个集合的大小以及它们两两、三三等交集的大小进行加减运算，来避免重复计数，从而得到准确的并集大小。其一般形式为：

生成函数 (Generating Function)是解决组合计数问题的一种代数工具。它将一个数列（例如，某种组合问题的解的个数）编码为一个形式幂级数的系数。通过对生成函数进行代数运算，可以推导出数列的性质、递推关系或通项公式。