排列与组合
排列计算对象的有序排列，组合计算无序选择；它们共同构成了枚举学的基础核心。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
集合的排列是其元素的有序排列（或集合到自身的双射）；组合是从集合中选出固定数量元素的无序选择。
Scope
本主题阐述了排列（有重复和无重复）和选择的计数及其细化，包括错排、圆排列和受限位置排列。它介绍了排列统计量，如降序、逆序和循环结构，这些将基本计数与更丰富的现代对称群理论联系起来。
Core questions
- How many ways can n distinct objects be ordered, and how many ways can r of them be ordered?
- How do repetition and indistinguishability change the count of arrangements?
- What are derangements, and how often does a random permutation fix no element?
- Which statistics on permutations are equidistributed?
Key concepts
- 阶乘和下降阶乘
- 有重复和无重复的排列
- 错排
- 圆排列
- 逆序和降序
- 斯特林数
Key theories
- 排列的循环分解
- 每个排列都可以唯一分解为不相交的循环；通过循环类型对排列进行计数受第一类斯特林数支配，并构成了对称群的基础结构。
- 错排枚举
- 没有不动点的排列数量，通过容斥原理得出，趋近于n!/e，经典结果表明大约37%的排列是错排。
Clinical relevance
排列和组合计数出现在概率论（等可能结果）、排序和洗牌算法、实验设计以及密码密钥空间中，其中排列空间的大小决定了难度和安全性。
History
排列组合学通过麦克马洪（MacMahon）20世纪初关于组合分析的工作而系统化，后来通过现代排列统计理论得到深化。
Key figures
- Percy MacMahon
- Richard P. Stanley
Related topics
Seminal works
- stanley2011
Frequently asked questions
- 一个包含n个元素的集合有多少种排列？
- 它有n!种排列，即所有小于等于n的正整数的乘积，因为n个位置中的每一个都由一个不同的剩余元素填充。
- 什么是错排？
- 错排是一种排列，其中没有元素停留在其原始位置，例如重新洗牌后没有信件回到自己的信封中。