第一種スターリング数の恒等式 Σc(n,k)2^k=(n+1)!の三通りの証明

追記：よりシンプルな証明を本で見つけたので、記事にしました。
iwalion.hatenablog.com

ツイッターで「スターリング数」で検索してみると、次のようなツイートを見かけた。

第1種スターリング数（n個の数をkこの巡回列に分解する方法の場合の数）のこの性質、1つ目は直感的に理解できるんだけど2つ目のこれどうやっても直感的に理解できない pic.twitter.com/tqqum01I2Q
— さかな (@Enjapma_kyopro) 2019年9月22日

消えたときのためにもう一度書いておくと
命題１
$\displaystyle\sum_{k=0}^n2^kc(n,k)=(n+1)!$

をどう示すか、という問題である。（上記の $c(n,k)$ は第一種スターリング数。）

この記事では、この式について代数的証明、全単射的証明その１、全単射的証明その２をつける。
命題１を直感的に理解したいという元のツイートの趣旨を、全単射的証明により叶えられたらよいと思っている。

全単射的証明その２では第一種スターリング数 $c(n,k)$ を「 $n$ の置換でサイクル数 $k$ なものの数」として理解するのではなく、「0-1タブロー」と呼ばれるオブジェクトとして扱う。
（見方を変えただけでやっていることは全単射的証明その１と一緒な気はする。）

代数的証明

第一種スターリング数の定義は色々あるが、例えば
(式０)： $\displaystyle x(x+1)\cdots(x+n-1)=\sum_{k=0}^n c(n,k)x^k$
を満たす数 $c(n,k)$ と定義される。
つまり、左辺 $\prod_{i=0}^{n-1}(x+i)$ を展開したときの $x^k$ の係数が第一種スターリング数 $c(n,k)$ である。
（例えばWikipediaを参照: スターリング数 - Wikipedia）
式０に $x=2$ を入れれば、命題１が示される。（証明終わり）

全単射的証明その１

以下のことを示す。
(式１)： $\displaystyle(n+1)\sum_{k=0}^{n-1}c(n-1,k)2^k=\sum_{k=0}^nc(n,k)2^k$ .
式１が示せれば、帰納法により命題１が示される。
式１を全単射的に示すために、「色付き置換」というオブジェクトを考える。
（これについては、以前の記事で述べたものと同じであるがもう一度書いておく。）
「色付き置換」の集合 $\mathcal{S}_n$ を
$\displaystyle\mathcal{S}_n\triangleq\left\{(\sigma,f)\mid \sigma\in\mathfrak{S}_n,\ f\colon (\sigma {\rm のサイクルの集合}) \to \{0,1\}\right\}$
と定める。つまり色付き置換とは、置換をサイクル分解してサイクルごとに色 $\{0,1\}$ を決めたものである。
式１を示すには、以下のような全単射 $\varphi$ を構成すればよい。
$\varphi\colon \{0,\ldots,n\}\times \mathcal{S}_{n-1}\to\mathcal{S}_{n}$ .

全単射 $\varphi$ は次のように構成できる。
$(\sigma,f)\in\mathcal{S}_{n-1}$ と $i\in\{0,\ldots,n\}$ とをとったとき、 $\mathcal{S}_n$ の元を次のように定める。

$i=0,1$ のとき、色 $i$ をもつ新しいサイクル $(n)$ を色付き置換 $(\sigma,f)$ に追加する。
$i=2,\ldots,n$ のとき、色付き置換 $(\sigma,f)$ には要素 $i-1$ を含むサイクルが存在する。要素 $i-1$ の前に要素 $n$ を追加する。

この対応は全単射的である。
（証明終わり）

全単射的証明その２

この証明ではまず、置換を全単射的に「0-1タブロー」というオブジェクトにに変換する。

「0-1タブロー」はLeroux [1]により導入されたオブジェクトで、ここでは次のように定義する。
分割 $\lambda=(\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_r\geq0)$ は次の条件を満たすとする。

$\lambda_1=n$ である。
転置をとった分割 $\lambda'$ は要素がすべて異なる、つまり $\lambda'=(\lambda_1'\gt\lambda_2'\gt\cdots)$ を満たす。

このような分割 $\lambda$ のヤング図形の各列に一個づつ $1$ を入れ、残りの場所に $0$ を入れたものを「0-1タブロー」といい、その集合を ${\rm Td}(r,n)$ とかく。
例：
f:id:iwalion:20210527132423j:plain

以下に見るように、この「0-1タブロー」を使って第一種スターリング数を表すことができる。
補題
下式が成立する。
$\#{\rm Td}(n-1,n-k)=c(n,k)$ .

補題を証明する前に、置換の「標準サイクル記法」について説明する。
標準サイクル記法とは、置換をサイクル分解したあと、各サイクルを先頭が最も小さい巡回置換として書き、それらの巡回置換を先頭要素が小さい順に一列に並べたものである。
つまり、置換
$\sigma=(65)(8)(47213)$
の標準サイクル記法は
$\sigma=(13472)(56)(8)$
である。

補題の証明
この証明はde Médicis [2]から引用している。
$n$ 文字の置換でサイクル数 $k$ のものと、集合 ${\rm Td}(n-1,n-k)$ との間に全単射 $\varphi$ を作ることができる。
全単射は以下のように帰納的に構成する。
まず、1文字の置換 $\sigma=(1)$ は、空の0-1タブローに対応するとする。
つまり、 $\varphi( (1) )\triangleq\emptyset$ .
次に置換 $\sigma$ が $n$ 文字の置換であるとき、文字 $n$ を抜いて $n-1$ 文字の置換 $\sigma'$ を作る。
置換 $\sigma'$ に対しては、0-1タブロー $T$ がもうすでに構成されているとする。
その上で、

文字 $n$ が置換 $\sigma$ において、サイクル $(n)$ に含まれるとき：

$\varphi(\sigma)\triangleq T$ とする。

文字 $n$ が置換 $\sigma$ において、 $(n)$ でないあるサイクルに含まれるとき：

置換 $\sigma$ の標準サイクル記法において、文字 $n$ が左から $i$ 番目にあるとする。
このとき、タブロー $T$ の先頭の列に $n-1$ 個の箱を追加し、上から $i-1$ 番目の箱に「1」を入れ、他の箱には「0」を入れる。
こうして構成された0-1タブローを $\varphi(\sigma)$ の値とする。

この対応は全単射的である。
（証明終わり）

対応の例：
f:id:iwalion:20210527132517j:plain

対応の例（順を追ってタブローを構成する様子）：
f:id:iwalion:20210527132555j:plain

以上の準備により、命題１を示すための全単射を構成できる。
命題２
以下の全単射 $\psi$ が構成できる。
$\displaystyle \psi\colon\bigsqcup_{k=0}^{n}{\rm Td}(n-1,n-k)\times\{0,1\}^k\to {\rm Td}(n+1,n+1)$ .