列举法 (集合论)
列举法是集合论（或者类的理论）中表示集合（或类）的一种方法。 如果已知集合（或类）的每一个元素，而且元素个数“相当有限”，我们可以通过“列举”其所有元素的方法来表示这个，如：{1,2,3}、{a}、{A,B,C,D,E}等。一对花括号“{ }”是集合（或类）表示法的特征符号。 如果集合（或类）的元素有“很多”甚至“无限多”以至于很难或无法将其所有元素一一列出，但其元素又具有很明显的“规律”，可以用“…”略过规律性比较明显的大量元素，如用…
标签：#组合计数
共 9 篇文章
波利亞計數定理
波利亚计数定理（，简称PET）用来研究不同着色方案的计数问题，它是组合数学中的一个重要的计数公式，是伯恩赛德引理的一般化，由波利亞·哲爾吉在1937年的论文中提出并被广泛应用，该结果首先由John Howard Redfield在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换群G，用t种颜色着色的不同方案数为： : l = \frac{1}\sum_{g \in G} t^{c(a_g)} 其中 …
伯特兰投票问题
在组合数学中，伯特兰投票问题（）是指，在一场选举中候选人A得到了p张选票，而候选人B得到了q张选票（p>q），那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是 : \frac{p-q}{p+q} 这个结果首次由威廉·亚伦·维特沃斯（W·A·Whitworth）于1878年发布，但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。 举例 假设有5名选民，其中3名候选人投票给A，2名候选人投票给B（即p = …
八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵列、正斜线或反斜线。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。 历史 八皇后问题最早是由西洋棋棋手（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺…
形式幂级数
形式幂级数(formal power series)是一个数学中的抽象概念，是从幂级数中抽离出来的代数对象。形式幂级数和从多项式中剥离出来的多项式环类似，不过允许（可数）无穷多项因子相加，但不像幂级数一般要求研究是否收敛和是否有确定的取值。形式幂级数在代数和组合理论中有广泛应用。 简介 形式幂级数和多项式的形式定义有类似之处。对于熟悉幂级数的读者，也可以将其看作是不讨论幂级数敛散性，也就是将其中的不定元仅仅看作是一个代数对象，而不是任何…
超排列
在组合数学中，n个符号的超排列（）是一个字符串，使得n个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在1≤n≤5时，n个符号的最小超排列的长度是1!+2!+...+n!，分别是1、3、9、33和153，与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 12345123415…
双射法
双射法是组合数学中的一种重要的证明方法，用来证明两个有限集合A和B的元素数目相等。证明的思路是构造一个双射映射f : A → B，于是根据双射的性质，A和B的元素数目就是相等的。这个证明是构造法证明的一种。由于双射法是给出具体的映射构造，而不是分别点算两个集合，所以不需要知道两个集合的元素个数。这种证明可以用于难以直接对两个集合或其中一个集合进行计数的情况。此外，双射法也可以用来计算一个集合（难以直接计算时），方法是将它映射到一个可以拆…
排容原理
排容原理（inclusion-exclusion principle）又称-{zh-hans:容斥原理;zh-hant:容斥原理;zh-cn:排容原理;zh-sg:排容原理}-、取捨原理，在組合數學裏，其說明若A_1, \cdots, A_n 為有限集，則 \begin{align} \left|\bigcup_{i=1}^n A_i\right| = {} & \sum_{i=1}^n |A_i| - \sum_{1 \le i 其中…
组合计数
组合计数是组合数学中最基本也是最古老的内容之一。研究的最基本问题是：满足特定条件下的计数对象的数目。所运用的方法，较古典的有生成函数、组合双射、分析等，近代则有大量概率论、现代代数结构的方法。