組み合わせ論的証明

数学において、組み合わせ証明という用語は、次の2種類の数学的証明のいずれかを意味するためによく用いられる。

• 二重計数による証明。組み合わせの恒等式は、慎重に選ばれた集合の要素数を2つの異なる方法で数え、恒等式の異なる式を得ることによって証明されます。これらの式は同じ対象を数えているため、互いに等しくなければならず、したがって恒等式が確立されます。
• 全単射による証明。2つの集合が同じ数の要素を持つことは、それらの間に全単射、つまり1対1の対応関係が存在することを示すことによって証明される。

「組み合わせ論的証明」という用語は、組み合わせ論におけるあらゆる種類の初等的な証明を指すために、より広く使用されることもあります。しかし、グラス（2003）がベンジャミン＆クイン（2003） （組み合わせ論的証明に関する書籍）のレビューで述べているように、これら2つの単純な手法は、組み合わせ論と数論における多くの定理を証明するのに十分です。

二重計数に関する典型的な証明は、数に関するよく知られた公式である。${\displaystyle {\tbinom {n}{k}}}$n個の要素からなる集合のk個の組み合わせ（つまり、サイズkの部分集合）について：

${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k(k-1)\cdots 1}}.}$

ここでは直接的な全単射証明は不可能です。なぜなら、恒等式の右辺は分数であるため、明らかに分数で数えられる集合が存在しないからです（分母が常に分子を割り切ることにも、少し考える必要があります）。しかし、分子はサイズn、n − 1、...、n − k + 1のk個の有限集合の直積を数え、分母はk個の要素からなる集合の順列を数えます（分母で最も明らかに数えられる集合は、別のk個の有限集合の直積です。必要であれば、明示的な全単射によって順列をその集合にマッピングできます）。ここで、S を、n個の要素からなる集合から重複なく選択されたk個の要素の列の集合とします。一方、Sと分子に対応する直積との間には、容易な全単射が存在します。${\displaystyle n(n-1)\cdots (n-k+1)}$一方、k個の組み合わせとkの置換σのペアの集合CからSへの全単射が存在する。これは、 Cの要素を昇順に取り、この数列をσで置換してSの要素を得ることによって得られる。この 2 つの数え方から、次の式が得られる。  

${\displaystyle n(n-1)\cdots (n-k+1)={\binom {n}{k}}k!,}$

そしてk !で割ると、次の式が得られます。${\displaystyle {\tbinom {n}{k}}}$一般に、計数式に除算が含まれる場合、同様の二重計数論証（存在する場合）によって、最も直接的な組み合わせ論的証明が得られますが、二重計数論証は、式がこの形式である場合に限定されるものではありません。

以下に、同じ恒等式をより簡潔かつ非公式に組み合わせ論的に証明したものを示します。

${\displaystyle {\binom {n}{k}}k!(nk)!=n!}$

n人が博物館に入りたいとしますが、博物館にはk人しか入るスペースがありません。まず、n人の中からk人を入場させます。${\displaystyle {\tbinom {n}{k}}}$定義により、これを行う方法は複数あります。次に、k人を一列に並べて、一人ずつ支払えるようにします。このk個の集合を並べ替える方法はk ! 通りあります。次に、外に残らなければならないn − k人を一列に並べて、他の人が出て行くときに一人ずつ入れるようにします。これを行う方法は ( n − k )! 通りあります。しかし、これで n 人のグループ全体を並べ替えたことになります。これはn ! 通りの方法で行うことができます。したがって、両辺ともn人を並べる方法の数を数えています。割り算によって、よく知られた公式が得られます。     ${\displaystyle {\tbinom {n}{k}}}$。

スタンレー (1997) は、組み合わせ列挙問題 ( n個の項目の集合から形成できるk個の部分集合S ₁、S ₂、 ... S _kのシーケンスの数を数える問題で、すべての部分集合の共通部分が空集合となるもの) の例を、その解法の 2 つの異なる証明とともに示しています。組み合わせ的ではない最初の証明は、数学的帰納法と生成関数を使用して、このタイプのシーケンスの数が (2 ^k − 1) ⁿであることを示しています。2 番目の証明は、集合 {1, 2, ..., k }の適切な部分集合が 2 ^k − 1個あり、集合 {1, 2, ..., n } から {1, 2, ..., k }の適切な部分集合の族への関数が (2 ^k − 1) ^{n 個}あるという観察に基づいています。数えるべきシーケンスは、これらの関数と 1 対 1 で対応付けることができ、与えられた部分集合のシーケンスから形成される関数は、各要素iを集合 { j | i ∈ S _j }。       

スタンレーは次のように書いています。「上記の組み合わせ論的証明は、以前の証明よりもはるかに短いだけでなく、単純な答えの理由も完全に明確になっています。ここで起こったように、最初に思いついた証明は面倒で洗練されていないことがよくあるのですが、最終的な答えは単純な組み合わせ論的証明を示唆しているのです。」組み合わせ論的証明は、非組み合わせ論的証明よりも洗練されていることが多く、また、記述する構造に対するより深い洞察を与えてくれるため、スタンレーは、組み合わせ論的証明は他の証明よりも優先されるべきであるという一般的な原則を定式化し、他の方法で真であることがわかっている数学的事実の組み合わせ論的証明を見つける多くの問題を練習問題として挙げています。

スタンレーは全単射証明と二重計数証明を明確に区別しておらず、両方の例を挙げているが、組み合わせ証明の2つのタイプの違いは、アイグナーとジーグラー（1998）が提示した、与えられたn個のノードの集合からn ^{n − 2}種類の異なる木を形成できるというケイリーの公式の証明の例で見ることができる。アイグナーとジーグラーはこの定理の4つの証明を挙げているが、最初の証明は全単射で、最後の証明は二重計数論法である。彼らはまた、5番目の全単射証明についても言及しているが、その詳細は説明していない。  

この公式の全単射証明を見つける最も自然な方法は、n個のノードを持つ木と、n-2個の要素を持つオブジェクトの集合（^{例えば、1}  からnまでの範囲のn - 2個の値のシーケンス）との間の全単射を見つけることです。このような全単射は、各木のプリューファーシーケンスを使用して得ることができます。任意の木は一意にプリューファーシーケンスにエンコードでき、任意のプリューファーシーケンスは一意に木にデコードできます。これら2つの結果を合わせると、ケイリーの公式の全単射証明が得られます。   

アイグナーとジーグラーが提示し、アンドレ・ジョヤルに帰属させた別の全単射証明は、一方では2 つの指定ノード (互いに同じである可能性がある) を持つnノード木と、他方ではnノードの有向擬似森林との間の全単射を伴う。T n _n ノード木が存在する場合、2 つの指定ノードを持つ木はn ² T _n存在する。擬似森林は、各ノードについて、そのノードから外側に伸びるエッジの終点を指定することによって決定できる。単一のエッジの終点にはn通りの選択肢があり (自己ループを許容)、したがってn ⁿ通りの擬似森林が存在する。ラベル付きノードが 2 つある木と擬似森林との間の全単射を見つけることにより、ジョヤルの証明はT _n = n ^{n − 2}であることを示している。    

最後に、アイグナーとジーグラーが提示したケイリーの公式の4番目の証明は、ジム・ピットマンによる二重計数証明です。この証明で、ピットマンは、n個のノードを持つ空のグラフに追加して単一の根付き木を形成できる有向エッジのシーケンスを考察し、そのようなシーケンスの数を2つの異なる方法で数えます。木、木の根、および木内のエッジの順序を選択することによって、このタイプのシーケンスを導出する方法を示すことで、このタイプの可能なシーケンスがT _n n !個あることを示します。また、部分シーケンスを単一のエッジで拡張できる方法を数えることで、可能なシーケンスがn ^{n − 2}   n !個あることを示します。同じエッジシーケンスの集合のサイズに関するこれら2つの異なる公式を等しくし、共通因子n !を消去すると、ケイリーの公式が得られます。

• 組み合わせ論的証明で用いられる二重計数と全単射の原理は、鳩の巣原理などの他の概念も含む、より大きな組み合わせ論的原理のファミリーの例と見なすことができる。
• 組み合わせ論的に恒等式を証明することは、数を集合に置き換えることで恒等式に構造を追加することと見なすことができる。同様に、分類とは集合をカテゴリーに置き換えることである。

• アイグナー、マーティン。Ziegler、Günter M. (1998)、Proofs from THE BOOK、Springer-Verlag、pp. 141–146、ISBN  3-540-40460-0。

• Benjamin, Arthur T. ; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof , Dolciani Mathematical Expositions, vol.  27, Mathematical Association of America , ISBN 978-0-88385-333-7。

• グラス、ダレン（2003）、『これを読んでください：本当に重要な証明』、アメリカ数学協会。

• スタンレー、リチャード P. (1997)、『列挙的組合せ論、第 I 巻』、ケンブリッジ高等数学研究、第 49 巻、ケンブリッジ大学出版局、11-12頁、ISBN  0-521-55309-1。