塞邁雷迪定理
在中，塞邁雷迪定理（）是個關於自然數集子集中的等差数列的結論。1936年，艾狄胥·帕爾和圖蘭·帕爾猜想：若整數集 A 具有正的自然密度，則對任意的正整數 k, 都可以在 A 中找出一個 k 項的等差數列。匈牙利數學家塞迈雷迪·安德烈於1975年證明了此結論。 定理敍述 若自然数集的子集 A 滿足 :\limsup_{n \to \infty}\frac{n} > 0, 則稱 A 具有正的上密度。塞邁雷迪定理斷言，若自然數集的一個子集具有…
标签：#組合數學定理
共 7 篇文章
波利亞計數定理
波利亚计数定理（，简称PET）用来研究不同着色方案的计数问题，它是组合数学中的一个重要的计数公式，是伯恩赛德引理的一般化，由波利亞·哲爾吉在1937年的论文中提出并被广泛应用，该结果首先由John Howard Redfield在1927年发表，但当时很少有人能理解，十年后由波利亚独立重新发现。对于含n个对象的置换群G，用t种颜色着色的不同方案数为： : l = \frac{1}\sum_{g \in G} t^{c(a_g)} 其中 …
朱世杰恒等式
朱世杰恒等式是组合数的一阶求和公式。元朝數學家朱世傑在《四元玉鑒》中，利用垛積術、招差術給出： :\sum_{i = a}^n \binom{i}{a} = \binom{n + 1}{a+1}， 或以m-1代n再與上式作差，寫成： : \sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1} 。 证明 递归方法 欲證 : \binom {m}{a+1} + \binom …
伯特兰投票问题
在组合数学中，伯特兰投票问题（）是指，在一场选举中候选人A得到了p张选票，而候选人B得到了q张选票（p>q），那么在整个点票过程中A的票数都严格大于B的概率是多少。这个问题的答案是 : \frac{p-q}{p+q} 这个结果首次由威廉·亚伦·维特沃斯（W·A·Whitworth）于1878年发布，但最终以在1887年重新发现这个问题的约瑟·伯特兰的名字命名。 举例 假设有5名选民，其中3名候选人投票给A，2名候选人投票给B（即p = …
塞邁雷迪-特羅特定理
塞邁雷迪－特羅特定理為組合幾何的定理，其斷言給定歐氏平面上任意n個點和m條直線，至多發生 :O \left ( n^{\frac{2}{3}} m^{\frac{2}{3}} + n + m \right ) 次重合（incidence，即二元組(p, \ell)，其中p為一點，\ell為直線，且p在\ell上）。 此上界已經是最優的上界了，唯一的改進只可能出現在大O符號中隱藏的常數倍數。 考慮隱藏常數的話，、拉多什·拉多伊契奇（Rad…
狄尔沃斯定理
在数学中，在序理论和组合学领域，狄尔沃斯定理通过将集合划分为数目最少的链来量化地描述任何有限偏序集的宽度。它以数学家 命名。 偏序集中的反链是其元素两两不可比的子集，而链是其元素两两可比的子集。链分解是将偏序集中的元素划分为若干无交的链。狄尔沃斯定理指出，有限偏序集合中，包含元素最多反链的元素数等于包含链数最少的链分解的链数，这个量被定义为该偏序集的宽度。 将这个定理推广到无限偏序集：如果存在有限多个链的分解，或当反链的大小有有限的上界…
霍爾婚配定理
数学上，霍爾婚配定理（）是菲利浦·霍爾最先證明的圖論定理，又稱霍爾定理，描述二分图中，能將一側全部頂點牽線匹配到另一側的充要條件。定理另有一個等價的組合敍述，確定一族有限集合在何種充要條件下，可自每個集合各揀選一個元素，而使所選元素兩兩互異（即沒有元素是重復的）。 集族表述 設 S 為 X 的有限子集組成的有限多重族。 S 的一個'是 S 至 X 的單射，且該單射 f 將族中任意集合 s\in S 映至該集合的某元素 f(s)。換言之，…