查看源代码：
reflect-counting.md

---
title: 反射计数
createTime: 2025/12/6
categories:
    - study
tags:
    - maths
    - OI
---

:::warning
我们将使用 $\displaystyle\binom{n}{m}$ 而不是 $\mathrm{C}_n^m$。
:::

## 问题引入

:::problem Catlan 数问题
长度为 $2n$ 的合法括号序列有多少个？
:::

这是经典的 Catlan 数问题。若把 $1\sim i$ 的左括号个数记作 $x_i$，右括号个数记作 $y_i$，则可以转化成以下问题：

:::problem Catlan 数问题（路径计数版）
每次只能沿坐标轴正方向移动一格，从 $S(0,0)$ 走到 $T(n,n)$，不接触 $l: y=x+1$ 的路径有多少？
:::

让我们来研究一个更一般的问题：

:::problem 有封顶的路径计数问题
每次只能沿坐标轴正方向移动一格，从 $S(0,0)$ 走到 $T(x,y)$，不接触 $l: y=x+b \ \ (b>0)$ 的路径有多少？
:::

## 反射计数

很容易证明以下结论：

:::lemma 普通路径计数
网格上从 $S(0,0)$ 到 $T(x,y)\ \ (x,y \ge 0)$ 的最短路径有 $\displaystyle\binom{x+y}{x}$ 条。
:::

这很容易证明，相当于从 $(x+y)$ 步里面取 $x$ 步向右，$y$ 步向上。

加上了封顶之后，考虑正难则反：接触了 $l$ 的路径有多少条呢？

记路径第一次接触 $l$ 的点为 $P$（考虑第一次是去重的常用手法），将 $S$ 到 $P$ 的路径以 $l$ 为轴作对称，$S$ 的对应点为 $S'(-b,b)$。

:::center
![图](reflect-counting/image.svg){width=500px}
:::

不难证明这样的反射是一一对应的，于是从 $S$ 到 $T$ 经过 $l$ 的路径与 $S'$ 到 $T$ 的路径一一对应，共有 $\displaystyle\binom{x+y}{x+b}$ 条。

于是答案为

$$
\binom{x+y}{x} - \binom{x+y}{x+b}
$$

## 反射容斥

AFO 了，加上目前流感中，先鸽了，有时间再写。