1维随机游走 返回起点 路线数

hbghlyj

IMC 2022 Day 1第3题:
令 p 为质数。跳蚤起初在实轴的 0 处。每分钟，跳蚤都有三种可能性：留在原位，或向左或向右移动 1。
p − 1 分钟后，它返回到 0。用 f(p) 表示它可能的路线数（例如，f(3) = 3：它可能在整个时间里都停留在 0；或者向左走，然后向右；或向右走，然后向左）。求 f(p) mod p。
提示：找到 $f(p)$ 的递归式，或使用生成函数。
答案：$f(p)\bmod 3=\begin{cases}0&p=3\\1&p=3 k+1\\-1&p=3 k-1\end{cases}$

Solution 1

The case $p=3$ is already considered, let further $p \neq 3$. For a residue $i$ modulo $p$ denote by $a_i(k)$ the number of Flea strategies for which she is at position $i$ modulo $p$ after $k$ minutes. Then $f(p)=a_0(p-1)$. The natural recurrence is $a_i(k+1)=a_{i-1}(k)+a_i(k)+a_{i+1}(k)$, where the indices are taken modulo $p$. The idea is that modulo $p$ we have $a_0(p) \equiv 3$ and $a_i(p) \equiv 0$. Indeed, for all strategies for $p$ minutes for which not all $p$ actions are the same, we may cyclically shift the actions, and so we partition such strategies onto groups by $p$ strategies which result with the same $i$. Remaining three strategies correspond to $i=0$. Thus, if we denote $x_i=a_i(p-1)$, we get a system of equations $x_{-1}+x_0+x_1=3, x_{i-1}+x_i+x_{i+1}=0$ for all $i=1, \ldots, p-1$. It is not hard to solve this system (using the 3-periodicity, for example). For $p=3 k+1$ we get $\left(x_0, x_1, \ldots, x_{p-1}\right)=(1,1,-2,1,1,-2, \ldots, 1)$, and $\left(x_0, x_1, \ldots, x_{p-1}\right)=(-1,2,-1,-1,2, \ldots, 2)$ for $p=3 k+2$.

Solution 2

Note that $f(p)$ is the constant term of the Laurent polynomial $(x+1+1 / x)^{p-1}$ (the moves to right, to left and staying are in natural correspondence with $x, 1 / x$ and 1 .) Thus, working with power series over $\mathbb{F}_p$ we get (using the notation $\left[x^k\right] P(x)$ for the coefficient of $x^k$ in $P$ )
\[
\begin{gathered}
f(p)=\left[x^{p-1}\right]\left(1+x+x^2\right)^{p-1}=\left[x^{p-1}\right]\left(1-x^3\right)^{p-1}(1-x)^{1-p}=\left[x^{p-1}\right]\left(1-x^3\right)^p(1-x)^{-p}\left(1-x^3\right)^{-1}(1-x) \\
=\left[x^{p-1}\right]\left(1-x^{3 p}\right)\left(1-x^p\right)^{-1}\left(1-x^3\right)^{-1}(1-x)=\left[x^{p-1}\right]\left(1-x^3\right)^{-1}(1-x),
\end{gathered}
\]
and expanding $\left(1-x^3\right)^{-1}=\sum x^{3 k}$ we get the answer.

(算法竞赛向)形式 Laurent 级数

hbghlyj

A002426: Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.
1, 3, 7, 19, 51, 141, 393, 1107, 3139...
Number of paths of length n with steps U = (1,1), D = (1,-1) and H = (1,0), running from (0,0) to (n,0) (i.e., grand Motzkin paths of length n). For example, a(3) = 7 because we have HHH, HUD, HDU, UDH, DUH, UHD and DHU.

hbghlyj

在Solution 1中,

The idea is that modulo $p$ we have $a_0(p) \equiv 3$ and $a_i(p) \equiv 0$.

这是怎么得到的呢