文献あり

Schröder数の畳み込みと一階差分は等しい

非負整数 $n$ に対してサイズ $n$ のSchröder路とは，ベクトル $A ≜ (1, 1), B ≜ (2, 0), C ≜ (1, - 1)$ の有限列 $ω = (ω_{1}, \dots, ω_{r}) (ω_{i} \in {A, B, C})$
であって，

全ての部分和 $ω_{1} + \dots + ω_{i} = (x_{i}, y_{i}) (0 \leq i \leq r)$ について $y_{i}$ が非負，
$ω_{1} + \dots + ω_{r} = (2 n, 0)$

を満たすものである．
サイズ $n$ のSchröder路の数 $s_{n}$ はSchröder数といい，
$\begin{array}{r} (s_{n})_{n = 0}^{\infty} = (1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, \dots) \end{array}$
である [1]．

Schröder数の一階差分はSchröder数の畳み込みに等しいことが知られている [2]．つまり，以下の定理が成り立つ．

任意の非負整数 $n$ に対して
$s_{n + 1} - s_{n} = \sum_{i = 0}^{n} s_{i} s_{n - i}$ 　 (1)
が成り立つ．

サイズ $n + 1$ のSchröder路のうち先頭が $B$ でないものの集合を $T_{n + 1}$ とする．
すると， $| T_{n + 1} | = s_{n + 1} - s_{n}$ である．
サイズ $n$ のSchröder路の集合を $S_{n}$ とかく．
定理を示すには，全単射 $T_{n + 1} \to ⨆_{i = 0}^{n} S_{i} \times S_{n - i}$ を作ればよい．

Schröder路 $ω \in T_{n + 1}$ には，原点を出発したあと初めて $x$ 軸上に戻ってくる点が存在する．
その前後で
$ω = A ω^{'} C ω^{″}$
と二つのSchröder路の組 $(ω^{'}, ω^{″})$ に一意的に分解することができる．
この分解 $ω \to (ω^{'}, ω^{″})$ は可逆であり所望の全単射を与える．

この性質を使って，Schröder数の母関数を求めることができる．
Schröder数の母関数を $S (x) ≜ \sum_{n = 0}^{\infty} s_{n} x^{n}$ とする．
式 (1)の両辺に $x^{n}$ をかけて $n$ にわたって足すと，
$\begin{array}{r} \sum_{n = 0}^{\infty} (s_{n + 1} - s_{n}) x^{n} = \sum_{n = 0}^{\infty} \sum_{i = 0}^{n} s_{i} s_{n - i} x^{n} \end{array}$
式変形して
$\begin{array}{r} \frac{S (x) - 1}{x} - S (x) = {S (x)}^{2} \end{array}$
$S (x)$ について解くと，
$\begin{array}{r} S (x) = \frac{1 - x - \sqrt{x^{2} - 6 x + 1}}{2 x} . \end{array}$