极值组合学
极值组合数学是组合数学的一个领域，它本身就是数学的一部分。极值组合数学研究有限对象（数字、图形、向量、集合等）的集合在满足某些限制的情况下可以有多大或多小。 极值组合数学大部分都与集合类有关；这就是所谓的极值集合论。例如，在一个n元素集合的子集中，可以成对相交的k元素子集的最大数量是多少？最多能选取有多少个没有包含关系的子集？后一个问题由Sperner 定理回答，最大数量为\binom{n}{\lceil \frac{n}{2} \rc…
标签：#组合数学
共 58 篇文章
乘法原理
乘法原理是組合計數的基本計數原理。簡而言之，「若有a種方法做某事，b種方法做另一事，則合共有a\cdot b種方法做此兩件事。」 舉例 設在港式粉麵店要點一碗湯粉麵，主食有三種：粗麵、幼麵、河粉，要選恰好一款；而配料有兩種選擇：雲吞、牛腩，亦要選恰好一款。問可選配搭數為何。 使用乘法原理，答案是3 \times 2 = 6，總共有六種配搭。 抽象一點，考慮從A, B, C三件物件選一，再從X, Y兩件物件選一。使用乘法原理，可知總共有3…
博苏克-乌拉姆定理
博苏克-乌拉姆定理表明，任何一个从n维球面到欧几里得n维空间的连续函数，都一定把某一对对蹠点映射到同一个点。 n = 2的情形，就是说在地球的表面上，一定存在一对对蹠点，它们的温度和气压相同。这里假设了温度和气压的变化是连续的。 这个定理首先由乌拉姆猜想。1933年，Karol Borsuk证明了该定理。从博苏克-乌拉姆定理可以推出布劳威尔不动点定理。 一个关于博苏克-乌拉姆定理的更强的陈述，是每一个保持对蹠点的映射 :f:\mathb…
無窮元組合學
數學分支無窮元組合學（infinitary combinatorics），又稱組合集合論（combinatorial set theory），是將組合學的想法推廣到無窮集。研究對象有連續圖、集合論的樹、拉姆齊定理在無窮集的推廣、馬丁公理。在2010年，本分支的開展的研究還有：連續統上的組合學、後繼上的組合學。 無窮集的拉姆齊理論 設\kappa,\ \lambda為序數，m為基數，n為正整數。引入記號 :\kappa\rightarro…
卡塔兰常数
{{Infobox number | name=卡塔兰常数 | number=0.915965594 | symbol=G | OEIS=A006752 | 發現者= | other name= | type= | define=G = \beta(2) = \sum_{n=0}^{\infty} \frac{(-1)^{n}}{(2n+1)^2} | root of= | 連分數= | series= | basedata = }} …
集合划分
表示。]] 在数学中，集合X的划分是把X分割到覆盖了X的全部元素而又不重叠的“部分”或“块”或“单元”中。更加形式的说，这些“单元”對于被划分的集合是既全无遗漏又互斥的。 定义 集合X的划分是X的非空子集的集合，使得每個X的元素x都只包含在这些子集的其中一个内。 等价的说，X的子集的集合P是X的划分，如果 P的元素都不是空集。（注：某些定义不需要这个要求） P的元素的并集等于X。（我们称P的元素覆盖X。） P的任何两个元素的交集为空。（…
多重指标
多重指標是數學中一種方便的表示法，它將指標中的單個整數推廣為多個整數，它可以簡化多元微積分、偏微分方程與分佈理論中的計算，也便於操作冪級數。 定義與運算 一個n-維多重指標是一個由整數構成的向量 :\alpha = (\alpha_1, \alpha_2,\ldots,\alpha_n) 設\alpha, \beta為多重指標，定義： :\alpha \pm \beta:= (\alpha_{1} \pm \beta_{1},\,\al…
范德蒙恒等式
范德蒙恒等式(英文：Vandermonde's Identity)是一个有关组合数的求和公式。 : \binom {n+m}k = \sum_{i=0}^k \binom ni \binom m{k-i} 证明 组合方法 甲班有 m个同学，乙班有 n个同学，从两个班中选出 k個同學有\binom {n+m}k种方法。 从甲班选 k-i名，从乙班选 i名有\binom ni \binom m{k-i}种方法，考虑所有情况i=0,1,\ld…
渗流
。不溶于水的物质（以及颗粒）会留在咖啡滤纸上。]] 在物理、化學和材料科學中，渗流（从拉丁语Percōlāre而来，意为“过滤”或“涓流”）指的是液体通过多孔材料时的运动和过滤行为。 背景 在过去数十年中，对渗流现象进行的数学研究（即渗流理论），给包括物理学、材料科学、复杂网络、流行病学中的多个课题提供了新的理解和技术工具。例如，在地质学中，渗流指的是水通过土壤和可渗透性岩石的过滤行为。通过水的流动。含水层中的地下水得到补给。在计划建设…
插空法
在组合数学中，插空法是排列组合的推广，主要用于解决不相邻组合与追加排列的问题。 插空法与隔板法的原理一样。 例子 若有A,B,C,D,E五个人排队，要求A和B两个人必须不站在一起，则有多少种排队方法？ 首先将CDE三个人排列，有P_3^3=6种排法，若排成DCE，□D□C□E□有4个空，让A,B插空有P_2^4=12种排法，总排法为P_3^3P_2^4=72 在一张节目单中原有6个节目，若保持这些节目相对顺序不变，再添加进去3个节目，则…
捆绑法
在组合数学中，捆绑法是排列组合的推广，主要用于解决相邻组合与不相邻组合的问题。 例子 若有A,B,C,D,E五个人排队，要求A和B两个人必须站在相邻位置，则有多少种排队方法？ 将A和B两个人捆绑，对(A,B),C,D,E进行排列，(A,B)有P_2^2种排法，(A,B),C,D,E有P_2^2\times P_4^4=2!4!=48种排法。 若有A,B,C,D,E五个人排队，要求A和B两个人必须不站在一起，则有多少种排队方法？ 所有排法…
算兩次
在數學中，算兩次是一個常用的證明技巧，常在證明恆等式時被提到。其思想是，對一個具體的量用方法甲來計算，得到的答案是A，而用方法乙則得到B，那麼等式A = B成立。此思想雖然明顯，但在實際使用時由於方法甲與方法乙通常有明顯的差異，因此能把兩個表面上相去甚遠的式子聯繫起來。算兩次產生過很多漂亮的證明。 組合恆等式 组合數學中的算兩次是一种组合证明方法。我們可以對同一個組合計數問題從兩個不同的方面去觀察，從而得到兩個表達式，其值卻相同。例如以…
帕斯卡矩阵
帕斯卡矩阵是以组合数为元素的矩阵。 其中S_n=L_n U_n 性质 帕斯卡对称矩阵S_n的元素为： :S_{ij} = \binom {i+j-2}{i-1} S_n的迹为： :tr(S_n) = \sum^n_{i=1} \frac{ [ 2(i-1) ] !}{[(i-1)!]^2} = \sum^{n-1}_{k=0} \frac{ (2k) !}{(k!)^2} （A006134） 帕斯卡下三角矩阵L_6的逆为： :\begi…
Q-模拟
在数学里，尤其是组合数学和特殊函数领域，一个定理、等式或者表达式的*q-模拟*是指在引入一个新的参数q后当q→1时原定理、等式或表达式的极限。最早地研究得较为深入的q-模拟是 19世纪被引入的基本超几何级数。 q-模拟在包括分形、多重分形, 混沌动力系统的熵表达在内的多个研究领域都有应用。另外，在量子群 和 q-变形 代数的研究中也有应用。 "经典" q-模拟开始于莱昂哈德·欧拉的研究工作，后来由F. H. Jackson 以及其他人所…
帕斯卡法則
帕斯卡法則是組合數學上的一個關於二項式係數的恆等式。它說明對於正整數n,k（k \le n）， : {n-1\choose k} + {n-1\choose k-1} = {n\choose k} 。 組合數學上的意義和證明 {n\choose k}表示在有n個元素的集內，有k個元素的子集的數目。其實這些子集之中，可分為包含第一個元素的和不含第一個元素的。包含第一個元素的子集有{n-1\choose k-1}個，不含的有{n-1\cho…
最长公共子串
在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。 样例 字符串"ABABC"，"BABCA"以及"ABCBA"的最长公共子串是"ABC"。其他的公共子串包括"A"、"AB"、"B"、"BA"、"BC"以及"C"。 ABABC ||| BABCA ||| ABCBA 问题定义 给定两个字符串，长度为m的字符串S以及长度为n的字符串T，求最长的子串…
幻圆
幻圆是组合数学的一个分枝，将自然数排列在多个同心圆或多个连环圆上，使各圆周上数字之和相同，几条直径上的数字和也相同。著名的同心幻圆有南宋数学家杨辉的攒九图和丁易东的太衍五十图。 杨辉幻圆 楊辉《续古摘奇算法》有聚五图，聚六图，聚八图，攒九图，八阵图，连环图。 攒九图 楊辉《续古摘奇算法》中的攒九图以自然数1至33构成，9在圆心，其余排列在四个同心圆上，每圈8个数。杨辉有如下攒九图奇妙特点； 四条直径上数字之和是147， 28+5+11+…
二項式變換
在組合數學中，二項式變換是一種，可計算一個計算序列的有限差分。二項式變換和歐拉變換有關，歐拉變換是有關二項式變換前後的序列其普通母函數之間的關係。 定義 一個序列 \{a_n\} 的二項式變換（T）是序列\{s_n\}： :s_n = \sum_{k=0}^n (-1)^k {n\choose k} a_k.