2
大学数学基礎解説
文献あり

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

82
0
$$$$

非負整数$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}

参考文献

投稿日:2023227

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Do everything bijectively.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中