塞邁雷迪定理
在中，塞邁雷迪定理（）是個關於自然數集子集中的等差数列的結論。1936年，艾狄胥·帕爾和圖蘭·帕爾猜想：若整數集 A 具有正的自然密度，則對任意的正整數 k, 都可以在 A 中找出一個 k 項的等差數列。匈牙利數學家塞迈雷迪·安德烈於1975年證明了此結論。 定理敍述 若自然数集的子集 A 滿足 :\limsup_{n \to \infty}\frac{n} > 0, 則稱 A 具有正的上密度。塞邁雷迪定理斷言，若自然數集的一個子集具有…
标签：#组合数学
共 58 篇文章
五色定理
五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比四色定理弱，也比四色定理更容易证明。1879年，给出了四色定理的一个证明，当时为人所接受，但11年后，珀西·约翰·希伍德却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。 证明 以下是对五色定理的证明。 给定n阶平面图G，我们对G的阶数进行归纳证明。 当n\leq 5时，正确性显然。 …
布鲁克斯定理
图论中，布鲁克定理（） 描述了图的着色数与图中最大度数的关系，提供了图着色数的一个上界。定理斷言，若连通图G中，每個頂點都不多於Δ個鄰居，且G不是完全图或奇环，则G可以被Δ-着色，即G可以被染成Δ种颜色，使得相邻点颜色互不相同。 背景 图染色数 考慮為G的頂點染色，而使每邊的兩端不同色。以符號表示，條件是：对于图G中任意两个顶点u,v，如果uv\in E(G)，那么u,v所染成的颜色不同。 对于图G，如果存在一个k种颜色的恰当染色方案，…
塞邁雷迪正則性引理
數學上，塞邁雷迪正則性引理（Szemerédi regularity lemma）斷言，給定任意一個足夠大的圖，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明塞邁雷迪定理，後來再於 1978 年證明了完整的版本。 及其合作者和高爾斯將正則性方法推廣到超圖上。 定義和引理敍述 塞邁雷迪正則性引理的嚴格敍述須…
組合
在組合數學，一個集的元素的組合是一個子集。S的一個k-組合是S的一個有k個元素的子集。若兩個子集的元素完全相同並順序相異，它仍視為同一個組合，這是組合和排列不同之處。 表示方式 从 n 个不同元素中取出 k 个元素的所有不同组合的个数，稱為从 n 个不同元素中取出 k 个元素的组合数，记做：C (n, k)、{}_{n}C_{k}、{}^{n}C_{k}、C^n_k（英语、香港、台灣）、C_n^k（法语、罗马尼亚语、俄语、中國內地、波兰…
八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵列、正斜线或反斜线。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。 历史 八皇后问题最早是由西洋棋棋手（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺…
贝克-坎贝尔-豪斯多夫公式
在数学中，贝克-坎贝尔-豪斯多夫公式（）指的是下列方程中Z的解： e^Xe^Y=e^Z 其中，X和Y是李群李代数中的非对易元素。贝克-坎贝尔-豪斯多夫公式有很多种写法，下列是最常见的一种： Z=X+Y+\frac{1}{2}[X,Y]+\frac{1}{12}[X,[X,Y]]+\frac{1}{12}[Y,[Y,X]]+\cdots 这里的\cdots表示还应有高阶项。 外部链接 , [http://www.hep.anl.gov/c…
母函数
在数学中，某个无穷序列(a_n)_{n \in \mathbb{N}} 的母函数（又称生成函数，）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。母函数一般用有关原始序列进行操作后得到的封闭形式表示，而非一个序列。 母函数可分为很多种，包括普通母函数、指数母函数、朗伯级数、贝尔级数和狄利克雷级数。对任何序列理论上都可以写出以上每个类型的一个母函数（除了朗伯级数和狄利克雷级数需要序列从a_1而非a_0开始），但是选用不同形式来…
加法原理
加法原理（rule of sum或addition principle）是組合計數的基本組合原理。簡單而言，若有A種方式做某事，又有B種方式做另一件事，且恰好要做其中之一，則總共有A+B種方案。 嚴格化的數學中，加法原理是有關集合大小的事實，斷言任意有限多個兩兩互斥的集合大小之和，等於其聯集的大小。以符號表示為，若集合S_1, S_2, \ldots, S_n兩兩互斥，則有 :|S_{1}|+|S_{2}|+\cdots+|S_{n}|…
背包问题
背包问题（）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。 背包问题历史悠久，甚至可以追溯到1897年。“背包问题”…
倒數和發散
数学中，倒數和發散的正整數集 :S = \{s_0,s_1,s_2,s_3,\dots\} \subseteq \mathbb N 是元素倒數的級數和發散的集合，即滿足 :\frac{1}{s_0}+\frac{1}{s_1}+\frac{1}{s_2}+\frac{1}{s_3}+\cdots = \infty. 下文簡稱「大集」。與之相反，倒數和收斂的集合，元素倒數和有限，下文簡稱「小集」。 如此區分集合的大小，見於和埃尔德什等差数…
隔板法
隔板法（又稱插板法）是组合数学中一種基礎計數方法，主要用於解決將 n 個相同元素分配至 k 個不同容器的組合問題。 該方法可進一步轉化為求解不定方程整數解個數的問題，並可與母函数結合，處理更一般的分配與計數模型。 隔板法与插空法的原理一样。 例子 现在有10个球，要放进3个盒子里 :●●●●●●●●●● 隔2个板子，把10个球被隔开成3个部份 :●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|…
逆序对
在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。 定義 逆序 設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ， 這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。 逆序集是所有逆序的集合。一個排列 \ \pi \ 的使用基于位置表示法…
鴿巢原理
鴿籠原理，又名狄利克雷抽屜原理、鴿巢原理。 其中一種簡單的表述法為： 若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。 另一種為： 若有n個籠子和kn+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少k+1隻鴿子。 集合论的表述如下： 若A是n+1元集，B是n元集，則不存在從A到B的單射。 拉姆齐定理是此原理的推廣。 例子 雖然鴿巢原理看起來很容易理解，但有時使用鴿巢原理會得到一些有趣…
约瑟夫斯问题
約瑟夫斯置換是一個出現在計算機科學和數學中的問題。在計算機編程的算法中，類似問題又被稱為約瑟夫環。 人們站在一个等待被處決的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，處刑下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。 问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。 历史 这个问题是以-{zh-hant…
階乘
在數學中，正整数的階乘（）是所有小於等於該數的正整數的積，记作n!，例如5的階乘表示為5!，其值為120： : 並定義，1的階乘1!和0的階乘0!都為1，其中0的階乘表示一個空積。 除外{{notetag|例如：1! = 0! = 1\,，(-0.5)! = \sqrt{\pi}，0.5!=0.5\sqrt{\pi}.}}]] 1808年，基斯頓·卡曼引進這個表示法：n!=\prod_{k=1}^n k \quad\forall n\g…
惠特尼连通性定理
图论中，惠特尼连通性定理（），简称惠特尼定理（），是美國數學家哈斯勒·惠特尼于1932年提出的关于2连通图等价性质的定理，该定理提供了关于2连通图的不同点对之间的连通性质刻画，描述了2连通图的特殊性质。 定理陈述 对一个图G，若G至少存在3个点，则G是2连通的当且仅当对G中任意两个点u, v，G中至少存在连接u, v的2条内部不相交路径，即除首尾相同（皆為u, v）外，沒有其他公共頂點的路徑。 定理证明 必要性 因为任意两点之间均存在路…
二項式係數
]] 在數學上，二項式係數是二項式定理中各項的係數。一般而言，二項式係數由兩個非負整數n和k為參數決定，寫作 \tbinom nk ，定義為 (1+x)^n的多項式展開式中，x^k項的係數，因此一定是非負整數。如果將二項式係數 \binom{n}{0},\binom{n}{1},\dots ,\binom{n}{n}寫成一行，再依照 n=0,1,2,\dots順序由上往下排列，則構成帕斯卡三角形。 二項式係數常見於各數學領域中，尤其是組…
最长公共子序列
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 定義 一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已…
惠特尼不等式
在图论中，惠特尼不等式 (英：Whitney's connectivity inequalities or Whitney's inequalities)，又称为惠特尼连通性不等式，是关于图的连通度的重要不等式，几乎出现于任何一本图论教科书中。该不等式明确地指出了图的点连通度与边连通度以及与图最小度之间的大小关系。但目前关于该定理的提出者是否是哈斯勒·惠特尼还没有统一定论。 叙述 对于任何一个非平凡图G，均满足 \kappa(G)\le…