要素が全部1のヘッセンベルグ行列のn乗の(1,1)成分はカタラン数

対角成分の一つ上まで非零要素が入っていてよいような行列をヘッセンベルグ行列という．
行列 $A\triangleq(\chi_{i+1\geq j})_{i,j=1}^{\infty}$

をここでは「要素が全部1のヘッセンベルグ行列」と呼ぶ．（ $\chi_P$ は命題 $P$ の特性関数．）

命題
$n$ は自然数とする．
行列 $A^n$ の $(1,1)$ 成分はカタラン数である．つまり
$\displaystyle\left[A^n\right]_{1,1} =C_n=\frac{1}{n+1}\binom{2n}{n}$ が成り立つ．
証明
有向グラフ $G\triangleq(V,E)$ を $V\triangleq\mathbb{N}=\{1,2,\ldots\}$ と
$\displaystyle E\triangleq\bigcup_{i=1}^\infty\bigcup_{j=1}^{i+1}\{(i,j)\}$
により定義すると，行列 $A$ はグラフ $G$ の隣接行列である．
よって， $A^n$ の $(1,1)$ 成分は $G$ の節点 $1$ から節点 $1$ への，長さ $n$ の歩道の数である．
ここで，グラフ $G$ の全ての節点は節点1への枝を持つので，上記の歩道の数は節点 $1$ を始点とする長さ $n-1$ の歩道の数に等しい．

そのような歩道を，訪れた順に節点を並べることにより
$(a_1,a_2,\ldots,a_n)$ という節点の列として表記する．
（ $a_1=1$ である．また，歩道の長さが $n-1$ なので，この列の長さは $n$ なことに注意．）
するとグラフの作り方から $1\leq a_i\leq a_i+1$ が成り立つ．

例：長さの歩道は

の５通り．

このような列から「サイズ $n$ のballot sequence」への全単射を構成する．
サイズ $n$ のballot sequenceとは， $n$ 個の $1$ と $n$ 個の $-1$ からなる長さ $2n$ の列で，すべての部分和が非負なものである．
サイズ $n$ のballot sequenceの数はカタラン数 $C_n$ であることが知られている．
（例えば [1]の問77を見よ．）

例：サイズのballot seqenceは

の５通り．

長さ $n$ の歩道からサイズ $n$ のballot sequenceへの全単射は以下のように作る．（[1]の問80より．）
$a_{n+1}\triangleq 1, b_i\triangleq a_i-a_{i+1}+1$ とする．
歩道 $(a_1,\ldots,a_n)$ の各 $a_i$ を， $1,-1^{b_i}$ に置き換える．
（ $-1^{b_i}$ は， $b_i$ 個の $-1$ を表す．）