全単射証明

組み合わせ論において、全単射証明とは、 2つの集合が等しい数の要素を持つこと、あるいは2つの組み合わせクラスに属する集合のサイズが等しいことを証明する手法であり、一方の集合を他方の集合に1対1で対応させる全単射関数を見つけることによって行われます。この手法は、特定の集合の要素数を求める公式を見つける方法として有用であり、要素数をより容易に数えられる他の集合と対応させることで、その数を求めることができます。さらに、全単射の性質自体が、それぞれの集合、あるいは両方の集合に関する強力な洞察を与えてくれることも少なくありません。

全単射証明が可能な問題は、二項係数恒等式に限らない。問題の複雑さが増すにつれて、全単射証明は非常に高度なものになる可能性がある。この手法は、組み合わせ論、グラフ理論、数論といった離散数学の分野で特に有用である。

組み合わせ論における全単射証明の最も古典的な例としては、以下のようなものがある。

• Prüfer シーケンスは、ラベル付き木の数に関するCayley の公式の証明を与えます。
• ロビンソン・シェンステッドアルゴリズムは、対称群に対するバーンサイドの公式の証明を与える。
• ヤング図の共役により、特定の整数分割の数に関する古典的な結果の証明を与える。
• 五角数定理の全単射証明。
• カタラン数の公式の全単射証明。

• 二項定理
• シュレーダー・ベルンシュタインの定理
• 二重計上（証明手法）
• 組み合わせ原理
• 組み合わせ論的証明
• 分類

• Loehr, Nicholas A. (2011). Bijective Combinatorics . CRC Press . ISBN 143984884XISBN ​ 978-1439848845。

• 「3による除算」 - ドイルとコンウェイ著。
• 「フックの長さの公式の直接的な全単射証明」 – Novelli、 Pak、Stoyanovsky著
• 「全単射的センサスと、指定された頂点次数を持つオイラー平面マップのランダム生成」 – ジル・シェーファー著。
• 「キャシー・オハラによるガウス多項式の単峰性に関する構成的証明」 -ドロン・ツァイルベルガー著。
• 「分割全単射、概説」 –イゴール・パク著。
• ガルシア＝ミルンの対合原理– MathWorldより。