二重計上（証明手法）

これは、幼い子供に掛け算を教える際によく用いられる、二重数えの簡単な例です。この文脈では、自然数の掛け算は繰り返し足し算として導入され、長方形のグリッドに配置されたアイテムの数を2つの異なる方法で数えることによって交換法則が成り立つことが示されます。グリッドが${\displaystyle n}$行と${\displaystyle m}$列。まず、合計して項目を数えます。${\displaystyle n}$列${\displaystyle m}$それぞれの項目を合計し、2回目は合計します${\displaystyle m}$列${\displaystyle n}$それぞれ項目、したがって、これらの特定の値に対して${\displaystyle n}$そして${\displaystyle m}$、${\displaystyle n\times m=m\times n}$。

二重カウントは、二項係数に関連する以下の恒等式を証明するためにも使用できます。

$${\displaystyle {\binom {n}{k}}={\binom {n}{nk}}}$$

どこ${\displaystyle 0\leq k\leq n}$仮に、${\displaystyle n}$赤または青に塗られる同一のボールがあり、塗られていないボールは残らない。${\displaystyle k}$赤い塗料で着色するボールの数、その他${\displaystyle nk}$ボールは青く塗らなければならない（各ボールを塗らなければならず、使用できる色は2色しかないため）。言い換えれば、選択のプロセスは${\displaystyle k}$オブジェクトは、他のものを選択するのと同じです${\displaystyle nk}$廃棄される物体。定義により、${\displaystyle k}$赤いボール${\displaystyle n}$使用可能なボールは${\displaystyle {\tbinom {n}{k}}}$同様に、絵を描く方法の数も${\displaystyle nk}$青いボール${\displaystyle n}$使用可能なボールは${\displaystyle {\tbinom {n}{nk}}}$両方のプロセスは同じものであるため、 $${\displaystyle {\binom {n}{k}}={\binom {n}{nk}}.}$$ 実際、同様の推論を用いて二項定理を証明することができる。

二重カウント方法の一例として、委員会を編成する方法の数を数える方法がある。${\displaystyle n}$人々、任意の人数（0人でも可）が委員会に参加できる。つまり、委員会に参加できる部分集合の数を数える。${\displaystyle n}$要素セットには、次のものが含まれる可能性があります。委員会を形成する1つの方法は、各人に委員会に参加するかどうかを選択するように求めることです。各人は、はいまたはいいえの2つの選択肢を持ち、これらの選択は他の人の選択とは独立しています。したがって、次のものが含まれます。$2×2×…2=2ⁿ$可能性。あるいは、委員会の規模は0から${\displaystyle n}$それぞれのサイズについて${\displaystyle k}$委員会が${\displaystyle k}$人々は形成されうる${\displaystyle n}$人々は二項係数です$${\displaystyle {n \choose k}.}$$ したがって、可能な委員会の総数は、二項係数の合計である。${\displaystyle k=0,1,2,\dots ,n}$2つの式を等しくすると、次の恒等式が得られます。$${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n},}$$二項定理 の特殊な場合。同様の二重計数法を用いて、より一般的な恒等式^{[ 2 ]を証明することができる。}$${\displaystyle \sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}}$$

二重計数論法でよく証明されるもう一つの定理は、無向グラフには次数が奇数の頂点が偶数個含まれるというものである。つまり、奇数個の辺を持つ頂点の数は偶数でなければならない。より分かりやすく言えば、握手をする人々の集まりでは、偶数人の人が奇数人の人と握手をしたことになる。このため、この結果は「握手の補題」として知られている。

これを二重カウントで証明するには、${\displaystyle d(v)}$頂点の次数とする${\displaystyle v}$グラフにおける頂点と辺の連結数は、2つの異なる方法で数えることができます。頂点の次数を合計する方法と、辺ごとに2つの連結を数える方法です。したがって $${\displaystyle \sum _{v}d(v)=2e}$$ どこ${\displaystyle e}$は辺の数です。したがって、頂点の次数の合計は偶数になります。これは、頂点の次数が奇数である場合には起こり得ません。この事実と証明は、グラフ理論の研究の始まりとなったレオンハルト・オイラーの1736年の論文「ケーニヒスベルクの七つの橋」に記されています。

番号は何ですか${\displaystyle T_{n}}$さまざまな木から形成できる${\displaystyle n}$異なる頂点？ケイリーの公式が答えを与える${\displaystyle T_{n}=n^{n-2}}$アイグナーとジーグラー（1998）はこの事実の証明を4つ挙げており、ジム・ピットマンによる4つ目の二重計数証明について「それらの中で最も美しい」と述べている。^{[ 3 ]}

ピットマンの証明は、空のグラフに追加できる有向エッジの異なるシーケンスの数を 2 つの異なる方法で数えています。${\displaystyle n}$頂点から根付き木を形成します。有向辺は根から離れる方向を向いています。このようなシーケンスを形成する1つの方法は、${\displaystyle T_{n}}$根付かない木の可能性、その中から1つを選びます${\displaystyle n}$頂点をルートとして、${\displaystyle (n-1)!}$追加可能なシーケンス${\displaystyle n-1}$（有向）エッジ。したがって、このようにして形成できるシーケンスの総数は${\displaystyle T_{n}n(n-1)!=T_{n}n!}$[ ^{3 ]​}

これらのエッジシーケンスを数えるもう1つの方法は、空のグラフにエッジを1つずつ追加し、各ステップで利用可能な選択肢の数を数えることです。${\displaystyle n-k}$既にエッジが存在するため、これらのエッジによって形成されるグラフは、根付きフォレストである。${\displaystyle k}$木々があります${\displaystyle n(k-1)}$次に追加するエッジの選択肢：開始頂点は次のいずれかになります。${\displaystyle n}$グラフの頂点であり、その終点となる頂点は、${\displaystyle k-1}$開始頂点を含む木の根以外の根。したがって、最初のステップ、2番目のステップなどの選択肢の数を掛け合わせると、選択肢の総数は $${\displaystyle \prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.}$$ 辺列の数に関するこれら2つの式を等しいとおくと、ケイリーの式が得られる。 $${\displaystyle \displaystyle T_{n}n!=n^{n-2}n!}$$ そして $${\displaystyle \displaystyle T_{n}=n^{n-2}.}$$ アイグナーとジーグラーが説明するように、この公式と証明は、根付き森林の数を数えるために一般化することができ、${\displaystyle k}$木々、どんな${\displaystyle k}$[ ^{3 ]​}

• ヴァンデルモンドの恒等式は、二重カウントによって証明できる二項係数の和に関する別の恒等式である。^{[ 4 ]}
• 正四角錐数。最初の数の合計の等式${\displaystyle n}$平方数と三次多項式は、3つの数の組を二重に数えることによって示すことができる。${\displaystyle x}$、${\displaystyle y}$、 そして${\displaystyle z}$どこ${\displaystyle z}$他の2つの数値よりも大きい。
• ルベル・ヤマモト・メシャルキン不等式。集合族に関するこの結果のルベルの証明は、等式ではなく不等式を証明するために用いられる、順列に関する二重計数論法である。
• エルデシュ・コー・ラドの定理は、集合の交差族の上限であり、二重計数不等式を用いてギュラ・OH・カトナによって証明された。 ^{[ 3 ]}
• フェルマーの小定理の証明。二重計数による整除性の証明：任意の素数に対して${\displaystyle p}$および自然数${\displaystyle A}$、 がある${\displaystyle A^{p}-A}$長さ-${\displaystyle p}$言葉を超えて${\displaystyle A}$-2つ以上の異なる記号を持つ記号アルファベット。これらは、${\displaystyle p}$循環シフトによって互いに変換できる単語。これらのセットはネックレスと呼ばれます。したがって、${\displaystyle A^{p}-A=p\cdot {}}$（ネックレスの数）で割り切れる${\displaystyle p}$[ ^{4 ]​}
• 二次相互性の証明。アイゼンシュタインによる証明は、三角形の格子点を二重に数えることによって、もう一つの重要な数論的事実を導き出している。

• 全単射証明。二重計数では1つの集合を2通りの方法で数えるのに対し、全単射証明では2つの集合の要素が1対1で対応していることを示すことで、2つの集合を1通りの方法で数える。
• 包含排除原理とは、集合の和集合の大きさを表す公式であり、同じ和集合を表す別の公式と併せて、二重計数論の一部として用いられることがある。