Schröder数の畳み込みと一階差分は等しい
非負整数$n$に対してサイズ$n$のSchröder路とは，ベクトル$\mathsf{A}\triangleq(1,1),\mathsf{B}\triangleq(2,0),\mathsf{C}\triangleq(1,-1)$の有限列$\omega=(\omega_1,\ldots,\omega_r)\quad (\omega_i\in\{\mathsf{A,B,C}\})$
であって，
- 全ての部分和$\omega_1+\cdots+\omega_i=(x_i,y_i)\ (0\leq i\leq r)$について$y_i$が非負，
- $\omega_1+\cdots+\omega_r=(2n,0)$
を満たすものである．
サイズ$n$のSchröder路の数$s_n$はSchröder数といい，
\begin{align}
(s_n)_{n=0}^\infty=(1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098,\ldots)
\end{align}
である [1]．
Schröder数の一階差分はSchröder数の畳み込みに等しいことが知られている [2]．つまり，以下の定理が成り立つ．
任意の非負整数$n$に対して
$s_{n+1}-s_n=\sum_{i=0}^ns_is_{n-i}$ (1)
が成り立つ．
サイズ$n+1$のSchröder路のうち先頭が$\mathsf{B}$でないものの集合を$\mathcal{T}_{n+1}$とする．
すると，$|\mathcal{T}_{n+1}|=s_{n+1}-s_n$である．
サイズ$n$のSchröder路の集合を$\mathcal{S}_n$とかく．
定理を示すには，全単射$\mathcal{T}_{n+1}\to\bigsqcup_{i=0}^n\mathcal{S}_i\times\mathcal{S}_{n-i}$を作ればよい．
Schröder路$\omega\in\mathcal{T}_{n+1}$には，原点を出発したあと初めて$x$軸上に戻ってくる点が存在する．
その前後で
$\omega=\mathsf{A}\omega'\mathsf{C}\omega''$
と二つのSchröder路の組$(\omega',\omega'')$に一意的に分解することができる．
この分解$\omega\to(\omega',\omega'')$は可逆であり所望の全単射を与える．
この性質を使って，Schröder数の母関数を求めることができる．
Schröder数の母関数を$S(x)\triangleq\sum_{n=0}^\infty s_nx^n$とする．
式 (1)の両辺に$x^n$をかけて$n$にわたって足すと，
\begin{align}
\sum_{n=0}^\infty(s_{n+1}-s_n)x^n=\sum_{n=0}^\infty\sum_{i=0}^ns_is_{n-i}x^n
\end{align}
式変形して
\begin{align}
\frac{S(x)-1}{x}-S(x)=\{S(x)\}^2
\end{align}
$S(x)$について解くと，
\begin{align}
S(x)=\frac{1-x-\sqrt{x^2-6x+1}}{2x}.
\end{align}
