# 数え上げ ## 定義 数え上げ(counting)は、ある集合の要素数(濃度)を具体的に求める技法の総称である。第14章の基本戦略は「未知の集合Tのサイズを直接数える代わりに、Tから数えやすい数列の集合Sへの全単射(またはk-to-1写像)を見つけ、Sのサイズから|T|を導く」というものであり、全単射の規則(Bijection Rule)がその出発点になる。この戦略の上に、複数の基本規則が積み重ねられる。積の規則(直積のサイズは各成分のサイズの積)・和の規則(互いに素な集合の和集合のサイズは各サイズの和)・一般化積の規則(数列の各成分の選択肢数が先行成分に依存してよい場合への拡張)は、いずれも数列を直接数えるための道具である。除法の規則(f: A → Bがk-to-1ならば|A|=k・|B|)は、対象を区別できるものとして過剰に数えたのち、同一の対象に対応する重複度で補正するという定石を与え、部分集合の規則(二項係数、[[二項係数]] を参照)・簿記の規則(多項係数)を含む本章の主要な結果の大半がこの技法に依拠する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.1〜§14.6) ## 横断的知見 - 数え上げの出発点である全単射の規則は、第4章の有限集合の[[濃度]]比較の枠組み(Mapping Rule、定理4.5.4の全単射版)をそのまま流用したものである。第4章は「AとBの濃度が等しいことをどう定義し、どう証明するか」という抽象的な問いに答えたのに対し、第14章はその同じ全単射版の規則を「未知の集合を数えやすい数列に帰着させる」という具体的な数え上げ戦略の道具として再利用する。第4章が確立した抽象的な比較の枠組みが、第14章で初めて実践的な計算技術へ転用される、という章をまたいだ構成の連続性が見える。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]], [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.1.1) - 第14章はn要素集合の順列の数がn!であることを一般化積の規則から導き(§14.3.3)、「順列が至るところに現れるからこそ階乗が頻出し、Stirlingの近似公式を教えた」と明言する。一方、第13章(Sums and Asymptotics)は積分限界法により ln(n!) の上下限を導出し、より精密なStirlingの公式を証明なしに引用する([[和の近似]] を参照)。両章を突き合わせると、第13章が「n!という量をどう近似計算するか」という解析的な問いに答えたのに対し、第14章は「そもそもなぜn!という量が数え上げにおいて中心的に現れるのか(順列の数え上げの帰結として)」という組合せ論的な起源を与えており、n!という同一の量について解析的側面と組合せ論的側面が相補的に揃うことになる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]], [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.3.3) - **除法の規則(第14章)と畳み込み則(第15章、[[母関数]])は、同じ「複合的な選択の数え上げ」という問題を異なる原理で解く**。第14章の除法の規則は、写像 f: A → B が一様にk-to-1であることを事前に確認できる場合にのみ適用でき、確認を誤ると過剰計数につながる(Two Pairsの例で強調される制約)。これに対し第15章の畳み込み則は、対象を「chocolate donutsの選び方」「plain donutsの選び方」のように独立な部品ごとの母関数として符号化し、それらの積の係数として合成問題の答えを取り出す。この経路では、事前にk-to-1性を検証する必要がない。実際、第15章§15.2.6の「リンゴは偶数個・バナナは5の倍数個・オレンジは最大4個・洋梨は最大1個」という複雑な制約付き数え上げは、各制約を個別の母関数(1/(1-x^2)、1/(1-x^5)、(1-x^5)/(1-x)、1+x)にエンコードして掛け合わせるだけで解け、除法の規則が要求するような一様な写像の構成は一切登場しない。逆に、第15章§15.2.4は k 種類のフレーバーからの選択(ドーナツ数え上げ)の母関数 1/(1-x)^k の係数が、第14章の簿記の規則(bookkeeper rule、多項係数の帰結)と同じ式 C(n+k-1, n) を与えることを確認しており、母関数による経路と第14章の数え上げ規則による経路は、単純な問題では同じ答えに収束することも分かる。両者を合わせると、除法の規則は「対称性のある過剰計数を一様な補正係数で割る」という限定的だが直接的な技法であるのに対し、畳み込み則は「個々の部品ごとの制約を代数的対象(母関数)にエンコードし、積の係数抽出によって合成する」というより一般的な技法であり、第14章の枠組みでは扱いにくい非一様な制約の組み合わせ(偶数個・5の倍数・上限付きなど、部品ごとに異なる形の制約)にも対応できる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] §14.2〜§14.6, [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] §15.2.2〜§15.2.6) ## 未解決の問い - 第14章の除法の規則は「写像がちょうどk-to-1であること」を事前に確認できる場合にのみ適用できる(ポーカーのTwo Pairsの例のように、この確認を誤ると過剰計数になる)。写像の逆像のサイズが一様でない一般の場合(k-to-1ではない写像)を扱う数え上げ技法は、第14章の範囲外である。包除原理([[包除原理]])がこの一部を補う。**第15章(Generating Functions)を突き合わせた結果は上記の横断的知見に追記した**が、生成関数の畳み込み則自体が「なぜ過剰計数を避けられるのか」という点は、除法の規則の枠組み(k-to-1写像とその補正)とは別の説明原理(多項式の係数抽出)によっている、という理解にとどまり、両者を統一する一般論(どちらの技法がどの範囲の問題をカバーするかの完全な線引き)はまだ得られていない。組合せ論の一般理論を扱う他ソースが ingest されたら、この線引きを補強したい。 - 濃度.md の未解決の問いに記された「全射↔単射の双対性は後続の数え上げでどう再利用されるか」という問いについて、第14章では鳩の巣原理([[鳩の巣原理]])がMapping Ruleの単射版の対偶として明示的に再利用されることが確認できた(§14.8)。一方、全射版の双対性がどう数え上げに再利用されるかは、第14章の中では明示的には現れなかった。これは今後の章(確率)の ingest 時に確認したい。 ## 関連 - 概念: [[濃度]] / [[二項係数]] / [[鳩の巣原理]] / [[包除原理]] / [[和の近似]] / [[集合]] / [[関数]] / [[母関数]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 14 Cardinality Rules]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 4 Mathematical Data Types]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 15 Generating Functions]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 14. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 15, §15.2.