双射
两个集合的元素之间的一一配对，使每个集合的每个元素都恰好与对方集合的一个元素对应。只要存在双射，两个集合的元素个数就相同——于是可以通过数一个容易数的集合，来数一个难数的集合。许多精巧的计数论证本质上都是双射。
用例 元集合的子集个数等于 ：把每个子集与它对应的、由 个 和 组成的特征序列配对，这显然是一一对应。
注意双射必须既单射又满射。例如把每个三角形对应到它最长的那条边就不是双射，因为不同的三角形可能共享同一条最长边。
术语表
解答真正依赖的那些词，附带用例与常见误用。
卡特兰数
第 个卡特兰数为 ，当 时依次为 。它计数的是：把 对东西排成一列，使任何前缀中后一种的个数都不超过前一种的排法数。这个条件在计票问题、括号化和格点路径中反复出现。
用例 正好数出由五个 A 与五个 B 组成、且在计票过程中 A 从不落后的序列数，也等于给六个因子的乘积加括号的方式数。
注意下标偏移是常见错误来源：，不是 。使用前先对着数列 核一遍。
顶点的度
图中与某个顶点相连的边数。在简单图里没有自环；而在由现实关系抽象出来的图中，各顶点的度往往由问题本身决定，而不是可以自由选择的。把所有顶点的度相加，等于每条边在两端各被数了一次，由此得到握手引理：所有度数之和必为偶数。
用例在七桥问题的图中，四块陆地的度分别是 ，四个都是奇数，因此不存在把每座桥恰好走一遍的路线。
注意一个看起来完全合理的度序列，未必能由简单图实现——例如只有一个度为 的顶点，而其余顶点度数全为 ，这是不可能的。
弗罗贝尼乌斯数
对一组硬币面值，弗罗贝尼乌斯数指不能用它们恰好凑出的最大金额。当只有两种互素的面值 、 时，它等于 ，而无法凑出的正整数恰好有 个。面值在三种或以上时，目前没有已知的封闭公式。
用例用 分和 分邮票时，弗罗贝尼乌斯数为 ：从 起的所有金额都能凑出，而 不能。无法凑出的恰好有 个，即 。
注意这个公式只适用于互素的面值。若用 分和 分，像 这样的金额永远凑不出，此时根本不存在「最大的不可凑出金额」。
不变量
在允许的操作下保持不变的量。如果某个候选终态的不变量取值与初态不同，那么无论怎样操作都到不了它。不变量把「这件事可不可能」变成了两个数字的比较。
用例把棋盘按通常方式交替染色。每块骨牌覆盖一个浅色格和一个深色格，所以「浅色格数减深色格数」始终为 。若剪掉的是两个同色的角，这个差变成 ，于是无法铺满。
注意不变量只能证明「不可能」，永远不能证明「可能」。两个状态共享同一个不变量，并不等于你能走过去——要证明可达，必须真的给出操作序列。
格点
坐标为整数的点，也就是通常整数网格上的点。顶点落在格点上的图形有很好的性质：面积、边界点数和内部点数由 Pick 定理联系起来，即 ，其中 是内部格点数， 是边界格点数。
用例对顶点为 、、 的三角形，边界点数为 ，面积为 ，故内部格点数 。
注意Pick 定理要求多边形不自交且顶点都是格点。自交的多边形、带洞的多边形，以及顶点不是格点的多边形，都会让这个公式失效。
数学归纳法
针对以自然数编号的命题的证明方法。先证明最小的情形成立（基础步），再证明「若对某个 成立，则对 也成立」（归纳步）。两者合起来覆盖了所有取值。强归纳法允许归纳步假定所有小于 的值都成立，而不只是 。
用例前 个奇数之和等于 ： 时 成立；把下一个奇数 加到 上得到 ，正是 时的命题。
注意两部分缺一不可。漏掉基础步是经典错误：「所有马都是同一种颜色」这个命题有一个看起来很像样的归纳步，但从 起就是错的。
模运算
用余数而不是完整的数来做运算。当 整除 时，称整数 与 模 同余，记作 。通常的加减乘都照常成立，因为若 且 ，则 、。除法是例外：只有当被约去的因子与模数互素时才能约。
用例求 的个位数，只需模 。 的幂以 为周期循环，周期为 ，而 ，故 ，个位是 。
注意不检查互素就乱约分是最典型的错误。由 不能约去 得到 —— 那是错的。
单调量
在允许的操作下只朝一个方向变化的量——要么总在增大，要么总在减小。由于非负整数不可能无限减小，单调量可以用来证明某个过程必然会终止。它是证明贪心算法或博弈会结束的标准工具。
用例在一个有限博弈中，若每走一步都严格减少棋盘上的棋子总数，那么博弈至多进行「初始棋子数」步就会结束，因为这个计数是非负整数且每回合都在下降。
注意这个量必须有下界（或上界）才有用。像 这样严格递减的实数序列永远不会终止，所以单调量论证需要取整数值，或者给出明确的界。
奇偶性
一个整数是奇数还是偶数——也就是它模 的值。奇偶性是最廉价的不变量：它在加减乘下的表现完全可预测，因为和的奇偶性等于奇数项个数的奇偶性，而积只有所有因子都是奇数时才为奇数。
用例聚会上握了奇数次手的人数总是偶数。把所有人的握手次数相加，等于把每次握手在两端各数一次，所以总和是偶数；而总和为偶数就要求奇数项有偶数个。
注意只看奇偶性常常不足以区分情形。若两个状态奇偶性相同，奇偶性就无法区分它们，此时需要更精细的不变量——模 、模 ，或者一个完整的染色方案。
抽屉原理
把 个物体放进 个盒子，必有一个盒子至少装了两个。一般形式是：把 个物体放进 个盒子，必有一个盒子至少装了 个。它只证明存在性，不构造任何东西——这既是它好用的原因，也是它让人不满足的原因。
用例任意 个人中必有两人出生在同一个月： 个人放进 个月，必然重复。同样的论证可以证明：任意 个整数中必有两个之差是 的倍数。
注意它不告诉你**哪个**盒子装满了，也不告诉你怎样找到那一对。真正的难点在于把盒子划在哪里，计数本身是平凡的。
韦达跳跃
一种处理「关于某个变量是二次的」丢番图方程的递降技巧。固定你想研究的量，把方程看作关于某个未知数的二次方程，再利用两根之和与两根之积都是整数这一事实，说明另一根也是整数；然后证明另一根更小，与最小性假设矛盾。矛盾所排除的，正是你想要的结论。
用例若 整除 ，则商是完全平方数。把商记为 、把关系式看成关于 的二次方程，就能造出一个更小的正整数解，递降最终迫使 。这正是 IMO 1988 年第 6 题的解法。
注意递降要能落地，必须有一个良序结构。你得证明新解是正的且严格更小，否则论证什么也说明不了——最常见的失误就是忘了排除那个负根。