IB Math: Path Counting Methods | IB数学：路径计数问题解法

📚 IB Math: Path Counting Methods | IB数学：路径计数问题解法

Path counting problems are a staple of IB Mathematics, appearing in both Analysis & Approaches (AA) and Applications & Interpretation (AI) at Higher Level. These problems elegantly combine combinatorics with geometric intuition, making them a favorite for examiners to test deeper mathematical thinking.

路径计数问题是IB数学中的经典题型，在分析与方法（AA）和应用与解释（AI）的高级课程中都会出现。这类问题巧妙地将组合数学与几何直觉相结合，是考官测试深层数学思维的常用工具。

In this comprehensive guide, we will explore the essential techniques for solving path counting problems, from the fundamental counting principle to advanced dynamic programming approaches. By mastering these methods, you will be well-equipped to handle any path counting question the IB exam throws at you.

在本指南中，我们将系统探讨解决路径计数问题的核心技巧，从基本计数原理到高级动态规划方法。掌握这些方法后，你将能够从容应对IB考试中出现的各类路径计数题目。

1. The Fundamental Counting Principle | 基本计数原理

Before diving into path-specific problems, we must establish the foundational tool: the Fundamental Counting Principle (FCP). This principle states that if one event can occur in m ways and a second independent event can occur in n ways, then the two events together can occur in m × n ways.

在深入路径特定问题之前，我们必须建立基础工具：基本计数原理（FCP）。该原理指出，如果某一事件有m种发生方式，另一个独立事件有n种发生方式，那么两个事件同时发生共有m × n种方式。

For example, if you need to choose one of 3 shirts and one of 4 pairs of pants, the total number of outfits is 3 × 4 = 12. This simple rule extends naturally to paths: if reaching point A has 5 routes and going from A to B has 3 routes, then reaching B via A has 5 × 3 = 15 routes.

例如，如果你需要从3件衬衫和4条裤子中各选一件，总搭配数为3 × 4 = 12。这条简单规则自然延伸到路径问题：如果到达A点有5条路线，从A到B有3条路线，那么经由A到达B共有5 × 3 = 15条路线。

Total Routes = Routes₁ × Routes₂ × … × Routesₖ

This multiplicative principle serves as the backbone for all path counting methods we will discuss. When paths must pass through multiple intermediate points, we simply multiply the number of ways to traverse each segment.

这条乘法原理是我们将要讨论的所有路径计数方法的基石。当路径必须经过多个中间点时，我们只需将各段的通行方式数相乘即可。

2. Grid Path Problems | 网格路径问题

The most classic form of path counting problems involves moving on a rectangular grid. Consider a grid with m rows and n columns. A common question asks: how many distinct paths exist from the top-left corner to the bottom-right corner, moving only right (R) and down (D)?

最经典的路径计数问题涉及在矩形网格上移动。考虑一个m行n列的网格。常见的问题是：从左上角到右下角，只能向右（R）和向下（D）移动，共有多少条不同的路径？

Since every path consists of exactly (m-1) down-moves and (n-1) right-moves, the total number of moves is (m-1) + (n-1) = m + n – 2. The problem reduces to choosing positions for the down-moves among all moves:

由于每条路径恰好包含(m-1)次向下移动和(n-1)次向右移动，总移动次数为(m-1) + (n-1) = m + n – 2。问题转化为在所有移动中选择向下移动的位置：

Number of Paths = C(m+n-2, m-1) = C(m+n-2, n-1)

For instance, on a 3 × 4 grid, the number of paths from top-left to bottom-right is C(3+4-2, 3-1) = C(5, 2) = 10. Let us verify this: with 3 rows and 4 columns, we need 2 down-moves and 3 right-moves, giving us C(5,2) = 10 distinct sequences.

例如，在一个3 × 4的网格上，从左上角到右下角的路径数为C(3+4-2, 3-1) = C(5, 2) = 10。让我们验证一下：3行4列的网格需要2次向下和3次向右，因此得到C(5,2) = 10种不同序列。

It is crucial to recognize that the binomial coefficient C(n, k) counts the number of ways to choose k positions from n total positions. In our context, we choose which of the total moves will be “down” (or equivalently, which will be “right”).

关键在于认识到二项式系数C(n, k)表示从n个总位置中选择k个位置的方法数。在我们的情境中，我们是选择总移动中哪些是”向下”（或者等价地，哪些是”向右”）。

3. Pascal’s Triangle Connection | 帕斯卡三角的联系

Path counting problems have a beautiful connection to Pascal’s Triangle. When we label each lattice point with the number of paths reaching it, the resulting array is precisely Pascal’s Triangle rotated. Each entry equals the sum of the entry above it and the entry to its left.

路径计数问题与帕斯卡三角有着优美的联系。当我们用到达每个格点的路径数来标记它时，得到的阵列恰好是旋转后的帕斯卡三角。每个条目等于其上方条目与其左侧条目之和。

This additive property arises because any path reaching a point (i, j) must come from either (i-1, j) via a down-move or from (i, j-1) via a right-move. Therefore:

这种加法性质源于到达点(i, j)的任何路径必然来自(i-1, j)（通过向下移动）或来自(i, j-1)（通过向右移动）。因此：

P(i, j) = P(i-1, j) + P(i, j-1)

Let us construct a small grid to illustrate this. Starting with P(0,0) = 1 (the starting point), we can fill in the number of paths to each point:

让我们构建一个小网格来说明这一点。从P(0,0) = 1（起点）开始，我们可以填写到达每个点的路径数：

1	1	1	1
1	2	3	4
1	3	6	10
1	4	10	20

Notice how the numbers in this 4 × 4 grid form a segment of Pascal’s Triangle. The value at the bottom-right corner, 20, equals C(6,3) = 20, which matches our formula since m + n – 2 = 6 and we choose 3 down-moves.

注意这个4 × 4网格中的数字如何构成帕斯卡三角的一段。右下角的数值20等于C(6,3) = 20，与我们的公式吻合，因为m + n – 2 = 6，我们选择3次向下移动。

The dynamic programming recurrence P(i, j) = P(i-1, j) + P(i, j-1) is the mathematical engine behind all grid path enumeration. Understanding this recurrence deeply will help you adapt to more complex variants.

动态规划递推式P(i, j) = P(i-1, j) + P(i, j-1)是所有网格路径枚举背后的数学引擎。深入理解这个递推关系将帮助你适应更复杂的变体。

4. Paths with Obstacles | 含障碍物的路径

A common twist in IB exam questions involves forbidden cells within the grid. When certain points cannot be visited, we subtract the paths that pass through these obstacles from the total count.

IB考试中的常见变体涉及网格中的禁止单元格。当某些点不能经过时，我们需要从总数中减去经过这些障碍物的路径。

The standard approach uses the Inclusion-Exclusion Principle. First, compute the total paths without restrictions. Then, for each forbidden point, compute paths passing through it by multiplying paths to that point by paths from that point to the destination. Finally, subtract these from the total, being careful not to double-count paths passing through multiple obstacles.

标准方法是使用容斥原理。首先计算无限制时的总路径数。然后，对每个禁止点，计算经过它的路径数——即到达该点的路径数乘以从该点到终点的路径数。最后从总数中减去这些路径，注意不要重复计算经过多个障碍物的路径。

Valid Paths = Total Paths − Paths through Obstacles (with adjustments)

For example, consider a 3 × 3 grid with one forbidden point at position (1,1). Total unrestricted paths from (0,0) to (2,2) is C(4,2) = 6. Paths passing through (1,1) equal C(1+1,1) × C(1+1,1) = 2 × 2 = 4. Therefore, valid paths = 6 − 4 = 2.

例如，考虑一个3 × 3网格，其中(1,1)位置有一个禁止点。从(0,0)到(2,2)的无限制总路径数为C(4,2) = 6。经过(1,1)的路径数等于C(1+1,1) × C(1+1,1) = 2 × 2 = 4。因此，有效路径为6 − 4 = 2。

When dealing with multiple obstacles, be cautious: if paths can pass through two obstacles, those paths are counted twice in the simple subtraction. The inclusion-exclusion formula handles this systematically, adding back paths through pairs of obstacles that lie on the same increasing path.

处理多个障碍时需谨慎：如果一条路径可能经过两个障碍点，那么在简单减法中该路径会被重复扣除。容斥公式系统性地处理这个问题，将同时经过两个障碍点（且在同一递增路径上）的路径加回来。

5. The Shortest Path Problem | 最短路径计数问题

When the grid has weighted edges, the question may shift from “how many paths exist” to “how many shortest paths exist.” In an unweighted grid where each move costs 1 unit, all monotone paths (only right and down) are automatically shortest paths.

当网格具有加权边时，问题可能从”有多少条路径存在”转变为”有多少条最短路径存在”。在无权重网格中，如果每次移动的代价为1个单位，所有单调路径（只向右和向下）自然都是最短路径。

However, consider a grid where some moves are blocked or have different costs. The number of shortest paths can be computed using a modified dynamic programming approach: track not only the minimum distance to each cell but also the number of ways to achieve that minimum.

然而，考虑某些移动被阻挡或具有不同代价的网格。最短路径数可以通过改进的动态规划方法计算：不仅跟踪到达每个单元格的最小距离，还要跟踪达到该最小值的路径数量。

At each cell, compare the distances from its possible predecessors. If a predecessor offers a strictly shorter distance, update the distance and set the path count to that predecessor’s count. If it offers an equal distance, add its count to the current cell’s count.

在每个单元格处，比较来自其可能前驱的距离。如果某个前驱提供严格更短的距离，则更新距离并将路径数设置为该前驱的路径数。如果提供相等距离，则将其路径数加到当前单元格的路径数中。

dist[v] = min(dist[u] + w(u,v)) over all predecessors u

ways[v] = sum(ways[u]) for all u achieving the minimum

This dual-tracking dynamic programming technique is powerful and general. It extends naturally to arbitrary graphs, not just grids, making it valuable for IB Math AI students who encounter network optimization problems.

这种双跟踪动态规划技术强大且通用。它自然扩展到任意图，而不仅仅是网格，这使得它对遇到网络优化问题的IB数学AI考生尤其有价值。

6. Combinatorial Identities via Paths | 通过路径理解组合恒等式

Path counting provides elegant visual proofs of many combinatorial identities. One famous example is Vandermonde’s Identity. Consider a grid path from (0,0) to (m+n, r+s) that must pass through the point (m, r).

路径计数为许多组合恒等式提供了优雅的视觉证明。一个著名的例子是范德蒙德恒等式。考虑从(0,0)到(m+n, r+s)的网格路径，它必须经过点(m, r)。

On one hand, the total number of paths is C(m+n, r+s). On the other hand, we can split the path at (m, r): the first segment has C(m, r) choices and the second segment has C(n, s) choices. By the multiplication principle, the total is C(m, r) × C(n, s). But this only counts paths through a specific point. Summing over all possible r values gives:

一方面，总路径数为C(m+n, r+s)。另一方面，我们可以在(m, r)处拆分路径：第一段有C(m, r)种选择，第二段有C(n, s)种选择。根据乘法原理，总数为C(m, r) × C(n, s)。但这只计算通过特定点的路径。对所有可能的r值求和得到：

C(m+n, r+s) = Σₖ C(m, k) × C(n, r+s−k)

This is precisely Vandermonde’s Identity. Similarly, the identity C(2n, n) = Σₖ [C(n, k)]² emerges from counting paths on an n × n grid by splitting at the midpoint. These connections demonstrate the unity of mathematics — combinatorics, algebra, and geometry all speaking the same language.

这正是范德蒙德恒等式。类似地，恒等式C(2n, n) = Σₖ [C(n, k)]² 通过在n × n网格上按中点拆分路径而得出。这些联系展示了数学的统一性——组合学、代数和几何都在说着同一种语言。

For IB students, recognizing these identities can simplify calculations dramatically. When you spot the structure of a known identity in a problem, you can apply the formula directly without lengthy enumeration.

对于IB学生来说，识别这些恒等式可以大大简化计算。当你在问题中发现已知恒等式的结构时，可以直接套用公式，无需冗长的枚举。

7. Paths on Other Lattices | 其他格点上的路径

Not all path problems live on rectangular grids. Triangular lattices, hexagonal lattices, and even three-dimensional grids appear in extension questions on the IB syllabus. The key insight is to decompose each step into its component directions.

并非所有路径问题都发生在矩形网格上。三角形格点、六边形格点甚至三维网格都会出现在IB教学大纲的扩展题中。关键的洞察是将每一步分解为其构成方向。

On a triangular lattice, you might move in directions such as east, northwest, and southwest. The number of paths to a given point equals a trinomial coefficient rather than a binomial coefficient. This generalizes the binomial case: instead of choosing positions for two types of moves, we count arrangements of three types.

在三角形格点上，你可能会向东、西北和西南方向移动。到达给定点的路径数等于三项式系数而不是二项式系数。这是二项式情况的推广：不再是选择两种移动的位置，而是计算三种移动的排列。

For three-dimensional grids, the formula extends straightforwardly. A path in a box of dimensions a × b × c, moving only in the positive x, y, and z directions, has length a + b + c. The number of distinct paths is:

对于三维网格，公式直接推广。在a × b × c的盒子的坐标轴上仅沿正方向移动的路径，其长度为a + b + c。不同路径的数量为：

Number of Paths = (a+b+c)! ⁄ (a! · b! · c!)

The multinomial coefficient counts ways to partition the total moves into groups labeled x, y, and z. This formula is the direct analogue of the binomial case, replacing the denominator’s two factorials with three.

这项式系数计算将总移动分组成标记为x、y和z的类别的方法数。这个公式是二项式情况的直接类比，将分母中的两个阶乘替换为三个。

When facing unusual lattice structures, always ask yourself: what are the basic move types, and how many of each type does a complete path require? The answer immediately reduces the problem to a multinomial counting exercise.

面对不寻常的格点结构时，始终问自己：基本移动类型是什么？一条完整路径需要每种类型多少次移动？答案立即将问题简化为多项计数练习。

8. Dynamical Programming Approach | 动态规划方法

Dynamic programming (DP) is the most versatile method for path counting, especially when the grid has irregular constraints. The essence of DP is to break the problem into overlapping subproblems and store their solutions to avoid redundant computation.

动态规划（DP）是路径计数最通用的方法，特别是当网格有不规则限制时。DP的本质是将问题分解为重叠的子问题，并存储其解以避免冗余计算。

The DP recurrence for path counting is deceptively simple. Let ways[i][j] represent the number of ways to reach cell (i, j). For an unrestricted grid with moves right and down:

路径计数的DP递推看似简单。设ways[i][j]表示到达单元格(i, j)的方式数。对于可向右和向下移动的无限制网格：

ways[i][j] = ways[i−1][j] + ways[i][j−1]

with base cases ways[0][j] = 1 and ways[i][0] = 1, since there is exactly one path along each edge. The bottom-right corner of the table contains the answer.

其中基础情况为ways[0][j] = 1和ways[i][0] = 1，因为沿每条边恰好有一条路径。表格的右下角就是答案。

DP shines when obstacles exist. Simply set ways[i][j] = 0 for forbidden cells. With weighted edges, modify the recurrence to incorporate weights. With “teleport” edges that jump across cells, add extra terms. The flexibility of DP makes it a must-have tool in your IB exam arsenal.

DP在存在障碍时尤为出色。只需对禁止单元格设置ways[i][j] = 0。对于加权边，修改递推以包含权重。对于跨单元格跳跃的”传送”边，增加额外项。DP的灵活性使其成为IB考试工具箱中必备的工具。

9. Common IB Exam Question Types | IB考试常见题型

Understanding typical exam question formats is key to performing well. Based on past IB papers, here are the most frequently encountered path counting scenarios:

理解典型的考试题型是取得好成绩的关键。根据历年IB试卷，以下是最高频出现的路径计数情境：

Type 1 — Simple grid counting: Count paths from one corner to another with unrestricted movement.
Type 1 — 简单网格计数：计算从一个角到另一个角的无限制移动路径数。

Type 2 — Blocked cells: Count paths avoiding one or more forbidden points.
Type 2 — 受阻单元格：计算避开一个或多个禁止点的路径数。

Type 3 — Paths with conditions: Require the path to pass through a specified point or avoid a specified region.
Type 3 — 带条件的路径：要求路径经过指定点或避开指定区域。

Type 4 — Application problems: Real-world contexts such as arranging schedules, distributing items, or navigating city streets.
Type 4 — 应用题：实际背景，如安排日程、分配物品或城市街道导航。

For Type 3, use the factorization method: count paths from start to the required point, then from that point to the end, and multiply. For avoiding a region, compute total paths and subtract those entering the forbidden region.

对于类型3，使用分解法：计算从起点到要求的点的路径数，再计算从该点到终点的路径数，然后相乘。对于避开区域的问题，计算总路径数并减去进入禁止区域的路径数。

10. Common Pitfalls and How to Avoid Them | 常见错误及规避方法

Path counting problems may look straightforward, but subtle mistakes are common even among top students. Here are the most frequent pitfalls encountered in IB exams:

路径计数问题看似简单，但即使是顶尖学生也常犯微妙错误。以下是IB考试中最常见的陷阱：

Pitfall 1 — Confusing rows and columns: In an m × n grid, the number of down moves is m−1, not m. Always subtract one from each dimension.

错误1 — 混淆行和列：在m × n网格中，向下移动次数为m−1，而不是m。务必从每个维度减去1。

Pitfall 2 — Forgetting to divide: When using multinomial formulas, ensure all factorial divisions are correct. C(4,2) = 4!⁄(2!·2!) = 6, not 4!⁄2! = 12.

错误2 — 忘记除法：使用多项式公式时，确保所有阶乘除法正确。C(4,2) = 4!⁄(2!·2!) = 6，而不是4!⁄2! = 12。

Pitfall 3 — Double subtraction with multiple obstacles: As discussed in the inclusion-exclusion section, subtract paths through each obstacle, then add back paths through both.

错误3 — 多个障碍时重复扣除：如容斥章节所讨论，先减去经过每个障碍的路径，再把同时经过两个障碍的路径加回来。

Pitfall 4 — Ignoring the condition of monotonicity: The binomial formula counts only monotone paths. If diagonal or backward moves are allowed, the formula changes completely.

错误4 — 忽略单调性条件：二项式公式只计算单调路径。如果允许对角线或向后移动，公式将完全不同。

To avoid these pitfalls, always articulate clearly what one valid path looks like, write out the move sequence, and check small cases by hand enumeration before applying a formula.

要避免这些错误，始终清楚描述一条有效路径是什么样，写出移动序列，并在应用公式前手工枚举小规模情况来验证。

11. Worked Examples | 完整例题解析

Let us now apply our methods to exam-style problems with fully worked solutions, demonstrating the step-by-step reasoning expected in IB mark schemes.

现在让我们将上述方法应用于考试风格的问题，提供完整的解答过程，展示IB评分标准所期望的分步推理。

Example 1: A 5 × 5 grid has one blocked cell at position (2, 2). Count the number of monotone paths from the top-left to the bottom-right corner.

例题1：在5 × 5网格中，位置(2, 2)处有一个受阻单元格。计算从左上角到右下角的单调路径数量。

Solution: Total paths without obstacles = C(5+5−2, 5−1) = C(8, 4) = 70. Paths through (2,2): C(2+2−2, 2−1) × C((5−2)+(5−2), 5−2) = C(2,1) × C(6,3) = 2 × 20 = 40. Valid paths = 70 − 40 = 30.

解答：无障碍总路径数 = C(5+5−2, 5−1) = C(8, 4) = 70。经过(2,2)的路径数：C(2+2−2, 2−1) × C((5−2)+(5−2), 5−2) = C(2,1) × C(6,3) = 2 × 20 = 40。有效路径 = 70 − 40 = 30。

Example 2: In a 4 × 6 grid, how many paths pass through the point (2, 3)?

例题2：在4 × 6网格中，有多少条路径经过点(2, 3)？

Solution: Paths to (2,3) = C(2+3, 2) = C(5, 2) = 10. Paths from (2,3) to (4,6) = C((4−2)+(6−3), 4−2) = C(5, 2) = 10. Total = 10 × 10 = 100.

解答：到达(2,3)的路径 = C(2+3, 2) = C(5, 2) = 10。从(2,3)到(4,6)的路径 = C((4−2)+(6−3), 4−2) = C(5, 2) = 10。总数 = 10 × 10 = 100。

Example 3: A 3 × 3 grid allows diagonal moves (down-right) in addition to right and down moves. Count all paths from (0,0) to (3,3).

例题3：在3 × 3网格中，除了向右和向下移动外，还允许对角线移动（右下）。计算从(0,0)到(3,3)的所有路径数。

Solution: Let d be the number of diagonal moves, r the right moves, and w the down moves. We need r = 3 − d and w = 3 − d, with d ranging from 0 to 3. For a fixed d, the number of sequences is (r+w+d)! ⁄ (r!·w!·d!). Summing:

解答：设d为对角线移动次数，r为向右次数，w为向下次数。需要r = 3 − d且w = 3 − d，其中d从0到3。对于固定d，序列数为(r+w+d)! ⁄ (r!·w!·d!)。求和：

Σ_{d=0}^{3} (6−d)! ⁄ ((3−d)!·(3−d)!·d!) = 1 + 6 + 30 + 20 = 63

The binomial coefficients here are generalized to multinomial counts. This example illustrates the flexibility needed when adapting to non-standard move sets.

这里的二项式系数被推广到多项式计数。这个例子说明了在适应非标准移动集合时所需的灵活性。

12. Exam Strategy and Practice Tips | 应试策略与练习建议

To excel at path counting problems in the IB exam, adopt a structured strategy. First, identify the grid dimensions and the allowed moves. Second, determine whether obstacles or constraints exist. Third, choose the appropriate formula or method.

要在IB考试中出色的完成路径计数问题，应采用结构化策略。首先，确定网格尺寸和允许的移动方式。其次，判断是否存在障碍或约束。第三，选择适当的公式或方法。

Memorize the fundamental formulas but, more importantly, understand their derivations. If you can derive C(m+n−2, m−1) from first principles during the exam, you will never misapply it. Practice with a variety of problems to build pattern recognition.

记忆基本公式，但更重要的是理解其推导过程。如果你能在考试中从基本原理推导出C(m+n−2, m−1)，你就永远不会误用。练习多种类型的问题以建立模式识别能力。

When checking your answers, always test small cases. If your formula gives the correct answer for a 1 × 1 and a 2 × 2 grid, it is likely correct. Also, verify that the numbers you compute are integers and reasonable in magnitude.

检查答案时，始终测试小规模情况。如果你的公式对1 × 1和2 × 2网格给出正确答案，那很可能是正确的。此外，验证计算出的数字是整数且在合理范围内。

Finally, be mindful of the marks allocated. In a 6-mark question, you are expected to show intermediate steps. Write down the binomial coefficients explicitly, show the arithmetic, and clearly state your final answer with proper units if applicable.

最后，注意分值的分配。在6分题中，你需要展示中间步骤。明确写出二项式系数，展示算术过程，并清晰地陈述最终答案（如适用需带上正确的单位）。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB Math: Path Counting Methods | IB数学：路径计数问题解法