スターリング数の恒等式Σc(n,k)2^k=(n+1)!のシンプルな証明

前回の記事（第一種スターリング数の恒等式 Σc(n,k)2^k=(n+1)!の三通りの証明 - 数学の命題示しました）では、第一種スターリング数の恒等式
$\displaystyle\sum_{k=0}^nc(n,k)2^k=(n+1)!$
に二通りの全単射的証明をつけた。

今回は、
Amazon | Proofs that Really Count: The Art of Combinatorial Proof (Dolciani Mathematical Expositions) | Benjamin, Arthur T., Quinn, Jennifer J. | Logic
という本の106ページに、この恒等式のよりきれいな証明を見つけたので、紹介する。
まず、全単射の構成に必要な「標準サイクル記法」について説明する。

置換の標準サイクル記法

（サイクル記法を一意的に定める方法は目的によって色々あり，前の記事で紹介した「標準サイクル記法」と以下で述べるものは別であることに注意．）
置換をサイクルの積として書く書き方の中で

各サイクルの先頭要素は、そのサイクルの中の最大要素である。
サイクルは、先頭要素が小さい順に並んでいる。

をみたすものは一意的に定まり、標準サイクル記法という。
例えば、置換 $\sigma = (5)(364)(12)(78)$ の標準サイクル記法は $\sigma=(21)(5)(643)(87)$ である。

ちなみに、置換を標準サイクル記法により書いた場合、サイクルの区切りを表すカッコ「 $(,)$ 」は書かなくてもよくなる。
なぜなら、標準サイクル記法 $\sigma=(21)(5)(643)(87)$ において、サイクルの区切りは今までで最大の数が出現する場所として同定できるからである。
そのため、 $21564387$ と書いてもよい。
標準サイクル記法からカッコを除いてできるワードを置換のワード記法と見れば、これは $\mathfrak{S}_n$ から自身への全単射を定める。
詳しくは
Amazon | Enumerative Combinatorics (Cambridge Studies in Advanced Mathematics, Series Number 49) | Stanley, Richard P. | Pure Mathematics
に書いてある。

全単射的証明

示すべき等式をもう一度書いておく．
$\displaystyle\sum_{k=0}^nc(n,k)2^k=(n+1)!$

左辺は $n$ の置換を標準サイクル記法で書き、各サイクルごとに色 $\{赤、青\}$ を定めたものの集合の濃度である。式で書くと、 $\#\{(\sigma,f)\mid\sigma\in\mathfrak{S}_n,f\colon(\sigma{\rm のサイクルの集合})\to\{赤、青\}\}$ である。
右辺は、 $\mathfrak{S}_{n+1}$ の濃度である。

よって以下の全単射を作ればよい。
$\{(\sigma,f)\mid\sigma\in\mathfrak{S}_n,f\colon(\sigma{\rm のサイクル}の集合)\to\{赤、青\}\}\to \mathfrak{S}_{n+1}$

以下で全単射の構成を例を交えながら述べる：
まず左辺の元、例えば「(21)(5)(643)(87)」をとる。
赤いサイクルはそのまま残し、青いサイクルは並び順を保ったまま連結してひとつのサイクルにして先頭に「9」をつける。最後に色をなくす。
結果的に「(5)(643)(92187)」が得られる。
但し、すべてのサイクルが赤い場合は、単にサイクル「(9)」を加えて色をなくす。
この対応は可逆である。
（証明終わり）