📚 Counting Paths | 路径计数
Counting paths is a fundamental topic in combinatorics and discrete mathematics, which appears frequently in the IB Mathematics curriculum. Whether you are navigating a grid of city streets, moving through a network graph, or solving probability problems, the ability to count the number of distinct routes between two points is an essential skill. This article explores the core techniques used to count paths, from simple shortest-path grids to more advanced constraints such as obstacles, diagonal boundaries, and graph-based walks.
路径计数是组合数学和离散数学中的基本主题，在IB数学课程中经常出现。无论你是在城市街道网格中导航，还是在网络图中移动，或者解决概率问题，计算两点之间不同路径数量的能力都是必不可少的技能。本文探讨了用于计数的核心技术，从简单的网格最短路径到更高级的约束条件，例如障碍物、对角线边界以及基于图的行走。
1. Shortest Paths on a Rectangular Grid | 矩形网格的最短路径
f ways to choose which m of the steps are to the right (or equivalently which n are upward). This gives the binomial coefficient C(m + n, m) = (m + n)! / (m! n!). For example, in a 2 × 2 grid, there are C(4, 2) = 6 possible routes.
考虑一个 m × n 的街道网格。要从左下角到右上角，且只允许向右和向上移动，任何最短路径都恰好包含 m 次右移和 n 次上移。总步数为 m + n，不同路径的数量就是从 m + n 步中选择哪 m 步为右移（或等价选择哪 n 步为上移）的方法数。这给出了二项式系数 C(m + n, m) = (m + n)! / (m! n!)。例如，在 2 × 2 网格中，共有 C(4, 2) = 6 条可能路线。
Number of shortest paths = C(m + n, m) = C(m + n, n)
2. Visualising with Pascal's Triangle | 利用杨辉三角可视化
There is a beautiful link between grid path counts and Pascal' where i and j represent the number of right and up steps to reach that point. The number of ways to arrive at (i, j) is exactly C(i + j, i). If you rotate the grid 45 degrees, these numbers align with the entries of Pascal' ds to increasing the total step count. This connection helps you compute path counts recursively: each interior point's count is the sum of the counts of the point to its left and the point below it.
网格路径计数与帕斯卡三角（杨辉三角）之间存在着美妙的联系。用坐标 (i, j) 标记 m × n 网格的交叉点，其中 i 和 j 分别表示到达该点所需的右移和上移步数。到达 (i, j) 的方法数恰好是 C(i + j, i)。如果将网格旋转45度，这些数字就对应着帕斯卡三角的项。顶点对应 (0, 0)，向下移动一行对应总步数增加。这种联系有助于递归地计算路径计数：每个内部点的计数值是其左侧点和下方点计数值之和。
3. Including Must-Pass and Avoided Points | 必经点与避开的点
Often problems add conditions such as "must pass through a specific intersection" or "must avoid a certain point" number of paths that go through that point from the unrestricted total. This simple multiplicative and subtractive reasoning handles most constrained path problems on grids.
问题中常常会增加条件，例如“必须经过某个特定交叉点”或“必须避开某个点”。对于一个必经中间点 P，总路线数是起点到 P 的路径数乘以 P 到终点的路径数。例如，在一个 4 × 4 网格中，如果必须经过 (2, 2)，则计数为 C(4, 2) × C(4, 2) = 6 × 6 = 36。如果要避开某个点，只需从无限制的总数中减去经过该点的路径数。这种简单的乘法和减法推理可以处理网格上大多数受约束的路径问题。
4. Diagonal Constraints and Catalan Numbers | 对角线约束与卡特兰数
umbers also count ballot sequences, valid parentheses, and many other combinatorial objects. The reflection principle can be used to prove this elegant formula, by subtracting paths that touch or cross the diagonal from the total.
当路径不允许穿过主对角线 y = x 时，计数问题变得更加微妙。一个经典的场景是从 (0, 0) 到 (n, n)，移动方式为向右和向上，且永远不越过对角线上方。这种单调路径的数量是第 n 个卡特兰数：Cₙ = (1/(n+1)) × C(2n, n)。卡特兰数同样可以计数选票序列、有效的括号组合以及许多其他组合对象。反射原理可以用于证明这个简洁的公式，即从总数中减去接触或穿过对角线的路径。
Cₙ = (1/(n+1)) × C(2n, n)
5. Paths in Graphs and Adjacency Matrix Powers | 图中的路径与邻接矩阵的幂
and 0 otherwise), then the (i, j)-entry of Aᵏ gives exactly the number of walks of length k from vertex i to vertex j. This powerful technique is especially useful when solving problems about connectivity or finding the number of routes with a fixed number of steps in a network. For instance, if a graph has three vertices and you compute A², the entries reveal all 2-step walks between vertices.
除网格之外，路径计数还可以扩展到一般图。如果 A 是有向图的邻接矩阵（若从 i 到 j 存在有向边，则 A[i][j] = 1，否则为 0），那么 Aᵏ 的 (i, j) 元就给出了从顶点 i 到顶点 j 的长度为 k 的行走数量。这一强大技术在解决有关连通性或计算网络中固定步数的路线数时特别有用。例如，如果一个图有三个顶点，你计算 A²，其中的元就能揭示所有顶点之间的 2 步行走。
Aᵏ[i][j] = number of walks of length k from i to j
6. Dynamic Programming with Obstacles | 含障碍物的动态规划
nd up). If a cell is blocked, dp[i][j] = 0. This bottom-up approach efficiently handles irregular grids. For example, a 3 × 3 grid with the centre cell (1, 1) blocked yields only 2 possible paths instead of C(4, 2) = 6.
当网格中包含阻塞的格子时，组合公式便不再直接适用。此时我们可以使用动态规划。定义 dp[i][j] 为从起点到达格子 (i, j) 的方法数。对于无障碍的格子，dp[i][j] = dp[i−1][j] + dp[i][j−1]（假设只能向右和向上移动）。若某个格子被阻塞，则 dp[i][j] = 0。这种自底向上的方法能高效处理不规则网格。例如，一个 3 × 3 网格且中心格子 (1, 1) 被阻塞时，只会得到2条可行路径，而不是 C(4, 2) = 6 条。
7. Using Reflection for Bounded Regions | 利用反射处理有界区域
and counting all paths from that reflected point to (a, b). This trick generalises to other linear boundaries and provides a purely combinatorial derivation without recursion.
另一个处理路径必须保持在边界线以下的优雅方法是反射原理。对于从 (0, 0) 到 (a, b) 且 a > b 的路径，不穿过直线 y = x 的路径数为 C(a+b, a) − C(a+b, a+1)。减去的项是通过将起点关于直线 y = x+1 反射，然后计数从该反射点到 (a, b) 的所有路径而得到的。这一技巧可以推广到其他线性边界，并提供了无需递推的纯组合推导。
8. Common Mistakes and How to Avoid Them | 常见错误与如何避免
One typical error is confusing permutations with combinations: remember that the order of identical steps (a sequence of R and U) does not matter when choosing positions. Another pitfall is double-counting when using the multiplication principle; always ensure that the sub-paths are independent. When subtracting blocked paths, be careful not to subtract paths that pass through multiple restricted points multiple times – inclusion-exclusion may be needed. Finally, in dynamic programming, initialise boundary rows and columns correctly (only one way to reach a cell if moving along an edge, provided no obstacles block it).
一个典型的错误是将排列与组合混淆：记住，在选择位置时，相同步骤的顺序（一串 R 和 U）是不重要的。另一个陷阱是在使用乘法原理时发生重复计数；务必确保子路径是相互独立的。当减去经过阻塞点的路径时，注意不要多次减去经过多个限制点的路径——此时可能需要用到容斥原理。最后，在动态规划中，要正确初始化边界行和列（如果沿着边缘移动，只要没有障碍物阻挡，到达一个格子只有一种方式）。
9. Applications in Probability and Games | 概率与博弈中的应用
Path counting extends naturally to probability. If each step is chosen uniformly at random among available directions, the probability of reaching a destination is the number of favourable paths divided by the total number of paths. In a grid, this can give the likelihood of a random walk staying within certain bounds. These ideas are also seen in game theory, such as counting winning sequences in a tournament or modelling stock price movements in a binomial tree (Cox-Ross-Rubinstein model). Mastery of path counting thus has direct relevance beyond pure combinatorics.
路径计数自然地延伸到概率。如果每一步在可取方向中均匀随机选择，那么到达某个目的地的概率就是有利路径数除以总路径数。在网格中，这可以给出随机游走保持在特定界限内的可能性。这些思想也出现在博弈论中，例如计算锦标赛中的获胜序列，或是在二叉树模型（Cox-Ross-Rubinstein模型）中建模股价变动。因此，掌握路径计数与纯组合学以外的问题直接相关。
10. Worked Example and Practice Problem | 例题与练习
Let's solve a typical IB-style problem: " 5 grid, find the number of shortest paths from (0,0) to (5,5) that avoid the point (2,3)." 5, 2) = 10. Therefore, paths through (2,3) = 10 × 10 = 100. The answer is 252 − 100 = 152.
我们来解决一个典型的 IB 风格问题：“在一个 5 × 5 网格中，求从 (0,0) 到 (5,5) 避开点 (2,3) 的最短路径数量。”无限制的路径总数 = C(10, 5) = 252。经过 (2,3) 的路径：从 (0,0) 到 (2,3) 为 C(5, 2) = 10，从 (2,3) 到 (5,5) 需要3次右移和2次上移，即 C(5, 2) = 10。因此，经过 (2,3) 的路径 = 10 × 10 = 100。答案为 252 − 100 = 152。
Try this practice: " ing right or up. How many paths avoid the main diagonal (never going above the line y = x)?" (Hint: use Catalan numbers or reflection. Answer: C₃ = 5.)
试试这道练习题：“一只蚂蚁在 3 × 3 网格的边上从左下角移动到右上角，只能向右或向上走。有多少条路径避开主对角线（从不越过直线 y = x）？”（提示：使用卡特兰数或反射。答案：C₃ = 5。）
11. Key Ideas to Remember | 核心要点回顾
To summarise, the fundamental tool for shortest grid paths is the binomial coefficient C(m+n, m). Constraints like must-pass points are handled by multiplying independent sub-paths, while avoided points require subtraction. Diagonal restrictions lead to Catalan numbers via the reflection principle. For arbitrary graphs, use adjacency matrix powers Aᵏ. When obstacles are present, dynamic programming provides a robust solution. Always double-check your approach against overcounting and misinterpretation of step order.
总结一下，网格最短路径的基本工具是二项式系数 C(m+n, m)。必经点等约束通过独立子路径的乘法处理，而必须避开的点则需要减法。对角线限制经由反射原理导出卡特兰数。对于任意图，使用邻接矩阵的幂 Aᵏ。当存在障碍物时，动态规划给出了稳健的解决方案。务必反复检查你的方法，避免重复计数和步骤顺序的误解。
12. Further Exploration and Extensions | 拓展与延伸
Once you are comfortable with 2D grids, try extending to 3D grids or paths with diagonal moves allowed. Problems may also involve weighted paths where each step has a cost and you need to count the number of optimal-cost paths. In IB exams, you might see path counting combined with binomial expansions or probability distributions. Building a strong intuition for combinatorial choices will serve you well in topics such as the binomial theorem, random walks, and Markov chains.
一旦你熟悉了二维网格，可以尝试拓展到三维网格或允许对角线移动的路径。问题也可能涉及带有权重的路径，每一步具有某种成本，你需要计算最优成本路径的数量。在 IB 考试中，你可能会看到路径计数与二项式展开或概率分布结合。培养对组合选择的扎实直觉，将有利于你学习二项式定理、随机游走和马尔可夫链等主题。
Published by TutorHao | IB Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图