組合技巧
證明組合學的結論時，常用到組合技巧。 一類是計數原理，如加法原理、乘法原理、容斥原理，常用於解決組合計數問題。另一類則是證明技巧，如双射法用於證明某兩類物件的數目一樣多，而抽屜原理則能保證某些物件存在，也用作確定離散物件數目的最大或最小值，還有算兩次和能證明許多組合恆等式。 母函数和遞歸關係也是很強的工具，能巧妙操作數列，描述許多組合問題的情景，甚至將之解決。 計數原理 加法原理 加法原理是以下直觀結論：若有兩類方法做某事，甲類a種，乙…
标签：#组合数学
共 58 篇文章
謝麗爾的生日
雪莉的生日（）是一個数学问题的非正式名稱，是新加坡及亞洲中學數學奧林匹克競賽的題目，在2015年4月10日由江堅文（Kenneth Kong）貼上Facebook，之後在網路上爆紅，已獲得《紐約時報》、《衛報》、英国广播公司（BBC）的報導，出題者也相當意外。 在題目中，名叫雪莉（Cheryl）的女生給了她剛認識的朋友艾伯特（Albert）和柏納（Bernard）一些有關她生日的資訊，讀者要根據這些資訊及她朋友的回覆判斷雪莉的生日。 起…
组合数学
组合数学（），在总體上是一门研究可數或离散对象的科学。它可分为廣義上的和狭義上的兩種層面，若是前者 (廣義的组合数学) ，其相当于离散数学，而后者 (狭义的组合数学) 則是组合计数、图论、代数结构、数理逻辑等的总称，但这只是不同学者在稱謂上的区别。而随着计算机科学日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题…
自然密度
自然密度（），又称渐进密度（），是数论中度量自然数子集大小的工具之一。 简介 以平方数集和自然数集的大小关系为例： : 平方数集与自然数集都是可数无穷集，我们能够在两个集合间建立一一映射（对于任意的自然数n都可以找到对应的平方数n^2与之对应，反之亦然），即两个集合是等势的。 : 然而，这种基于基数的大小比较违反了自然数多于平方数的直观认识，因为所有平方数都是自然数，而却有许多自然数不是平方数，且随着自然数的增大平方数会变得越来越稀少。…
杨表
在数学中，杨表（），又称杨氏矩阵，是组合表示理论和舒伯特演算領域的常用工具。在對稱群和一般线性群性質的研究中，楊表提供了一個方便的方式来描述的它們的群表示。杨表由剑桥大学数学家 在 1900 年提出。接著於 1903 年被弗罗贝尼乌斯应用于对称群的研究中。他们的理论由许多数学家进一步发展，包括、威廉·瓦伦斯·道格拉斯·霍奇、G. de B. Robinson、吉安-卡洛·羅塔、Alain Lascoux、Marcel-Paul Schü…
遞迴關係式
递推关系（），是一種递推地定義一個序列的方程式：序列的每一項目是定義為前若干項的函數。 像斐波那契数即為递推关系 :x_{n+2} = x_{n+1} + x_{n} 某些簡單定義的遞迴關係式可能會表現出非常複雜的（混沌的）性質，他們屬於數學中的非線性分析領域。 所謂解一個遞迴關係式，也就是求其解析解，即關於n的非遞迴函數。 遞迴關係式的例子 等差數列 :x_0=1,x_{n+1}=x_n+2為等差數列1,3,5,7,..... :一般…
杨辉三角形
》一页：杨辉引用贾宪《释锁算书》中的贾宪三角形]] 杨辉-{}-三角形，又称帕斯-{}-卡三角形、賈憲三角形、海亚姆三角形、巴斯-{}-卡三角形，是二项式系數的一种写法，形似三角形，在中国首现于南宋杨辉的《詳解九章算法》得名，其在书中说明是引自贾宪的《释锁算书》，故又名贾宪三角形。前9行写出来如下： \begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \qu…
最长递增子序列
在计算机科学中，最长递增子序列（）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的時間複雜度，这里n表示输入序列的规模。 例子 对于以下的原始序列 :0, 8, 4, 12, 2, 10, 6, 14, 1…
李善兰恒等式
李善兰恒等式为组合数学中的一个恒等式，由中国清代数学家李善兰于1859年在《垛积比类》一书中首次提出，因此得名。 有幂级数和概率两种证明方法。 表达式 {\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k} 其中{\binom {k}l}=\frac{k!}{l!(k-l)!} 与超几何函数的关系 李善兰恒等式是薩爾許茨定理（Saalschütz's theore…
希臘拉丁方陣
希臘拉丁方陣（）為兩個拉丁方陣相正交所得到的方陣。 \begin{bmatrix} a\beta & b\gamma & c\alpha \\ b\alpha & c\beta & a\gamma \\ c\gamma & a\alpha & b\beta \\ \end{bmatrix} \begin{bmatrix} a\gamma & b\alpha & c\beta \\ b\beta & c\gamma & a\alpha \…
圆排列
數學中，特別是群論中，圆排列（），又稱圆周排列、环状排列、循环排列，直觀地，是指从n个不同元素中选出r个元素排列成一个圆的形狀。 定義 圓排列並沒有統一的精確定義。有些作者對圓排列的定義是僅有一個輪換的排列。其他作者則使用更寬鬆的定義，允許不動點的存在。 例如排列 \begin{pmatrix} 1 &2 &3 &4 &5 &6 &7 &8 \\ 4 &2 &7 &6 &5 &8 &1 &3 \end{pmatrix} = \begin…
整數分拆
一個正整數可以寫成一些正整數的和。在數論上，跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數（）。其中最常見的問題就是給定正整數n，求不同數組(a_1,a_2,...,a_k)的數目，符合下面的條件： a_1 + a_2 + ... + a_k = n （k的大小不定） a_1 \ge a_2 \ge ... \ge a_k > 0 其他附加條件（例如限定「k是偶數」，或「a_i不是1就是2」等） 分割函數p(n)是…
对称函数
数学中，若n元函数无论变量顺序如何，值都相同，就称之为对称函数。例如，二元函数f\left(x_1,x_2\right)，当且仅当\forall x_1,\ x_2,\ \left(x_1,x_2\right),\ \left(x_2,x_1\right)\in {\rm dom}(f),\ f\left(x_1,x_2\right) = f\left(x_2,x_1\right)，f是对称函数。最常见的对称函数类型是多项式函数，由对称…
任务分配问题
任务分配问题是在加权二分图中寻找最大（或最小）加权匹配的问题，也称二分图最佳带權匹配问题或二分图最优匹配。此类问题通常使用匈牙利算法（KM算法）或转换为一个网络费用流问题进行求解。 详述 分为以下几类： 线性任务分配问题：P是二元组(a, b)的集合，其中a和b分别是集合A和B中的元素。C是某一函数，并满足特定约束条件，例如：A的每一个元素必须在P中出现一次，或者B的每一个元素必须在P中出现一次，或者以上二者都必须满足。线性任务分配问题…
无偏博弈
在组合博弈论裡，无偏博弈是一类任意局势对于游戏双方都是平等的回合制双人游戏。这里平等的意思是所有可行的走法仅仅依赖于当前的局势，而与现在正要行动的是哪一方无关。换句话说，两个游戏者除了先后手之外毫无区别。此外，它们还要满足一些组合游戏的基本条件： 完全信息，所有游戏者都能看到整个局势。这排除了桥牌一类的游戏。 无随机行动。所有行动都确定性地将目前局势转变到下一个局势。 在有限步行动之后按照规则游戏必将终止，此时有唯一的一方成为赢家。 即…
组合拓扑
组合拓扑是代数拓扑的一个较早名称，可追溯到空间的拓扑不变量（如贝蒂数）被视为从空间的组合分解（如分解为单纯复形）中导出的时期。在单纯逼近定理得到证明后，这种方法变得更加严谨。 名称的改变反映了将循环-模-便捷等拓扑类明确组织为阿贝尔群的举动，这种观点通常归功于埃米·诺特，名称的改变可能反映了她的影响。这一转变也归功于受诺特影响的海因茨·霍普夫的工作，及独立定义同调的Leopold Vietoris和Walther Mayer。 尼古拉·…
完美尺
完美尺是一个有整数刻度a_1=0的尺子，符合以下条件：对于任意的整数0，都存在唯一的i,j使得k=a_i-a_j。这样的尺子被称为m-完美尺。 对于给定的m,n，长度l最小的m-完美尺被称为最优完美尺。 例子 一个长度为7的4-完美尺的例子是(0,1,3,7)。对于所有不超过4的正整数，都有唯一的表示方法如下： 1=1-0 2=3-1 3=3-0 4=7-3 参考文献
尼姆数
组合博弈论引入了一类数学对象，称为尼姆数，它们被定义为尼姆堆的值。但是由于斯普莱格–格隆第定理，它们可以用于一大类游戏的研究。事实上，尼姆数是在序数的真类上赋予尼姆加法和尼姆乘法的运算之后形成的概念。这些运算和通常施行于序数类上的加法和乘法并不相同。 尼姆数的特点 斯普莱格–格隆第定理指出：每个无偏博弈等价于一个特定大小的尼姆堆。尼姆数的加法运算（叫做尼姆加法）可以用于计算等价于多个堆的单一尼姆堆大小。这被定义为 :\alpha + \…
希洛西七面體
{{Infobox polyhedron | name = 希洛西七面體 | polyhedron = 希洛西七面體 | imagename = Szilassi polyhedron.svg | rotating = Szilassi polyhedron.gif | rinfo = （-{zh-tw:點選檢視; zh-cn:点击查看}-旋轉模型） | Type = | Face = 7 | Edge = 21 | Vertice =…
稀疏尺
稀疏尺（Sparse ruler）指的是去掉了一些刻度的尺子。抽象来说，一个长度为L，有m个刻度的稀疏尺可以被记为整数序列a_1, a_2, ..., a_m(0 = a_1 )。刻度a_1和a_m对应尺子的首尾。为了能够测量长度K（0\le K\le L），我们需要存在刻度a_i,a_j使得a_j-a_i=K 。 如果一个稀疏尺能够测量不超过它的长度的任意整数长度，称这个稀疏尺是完全的。对于一个完全稀疏尺，如果不存在另一个长度相同但刻…