数えるとはどういうことか ― 加法原理・乗法原理・全射の数え上げ
「数える」とは集合の濃度を求めることです．足すか掛けるかは直和か直積かに対応し，順列・組合せの公式もこの視点から自然に導かれます．全射の数え上げまで含め，数え上げの本質に迫ります．
組合せ論の教科書を開くと，いきなり順列や組合せの公式が出てきます．しかし，そもそも「数える」とはどういうことかを考えたことがあるでしょうか？ この記事では，数え上げの本質が集合の濃度であることを出発点に，加法原理・乗法原理・順列・組合せを統一的に理解します．
1 「数える」＝集合の濃度
定義 1 (数え上げの本質).
有限集合 の数え上げとは，（ の濃度，つまり要素数）を求めることです．
一見当たり前ですが，これは非常に重要な視点です．「サイコロの目の出方は何通り？」という問いは，「出目の集合の濃度はいくつ？」と言い換えることで数学の対象になります．
注意 2.
数え上げ問題を解くときの第一歩は，数えたい対象を集合として明確に定義することです．「何の集合の要素数を求めているのか？」が曖昧だと，ダブルカウント（重複して数える）やカウント漏れの原因になります．
2 加法原理 ― 直和は足し算
定理 3 (加法原理).
有限集合 と が互いに素（）のとき，
が成り立ちます．より一般に， が互いに素ならば，
です．
注意 4.
加法原理は直和の言葉で書けます． のとき （直和）と書くと， です．つまり，「足すか？」は「その集合を互いに素な部分に分割できるか？」と同じことです．
例 5 (場合分け).
52枚のトランプからハートまたはスペードのカードを引く場合の数は，ハートの集合（13枚）とスペードの集合（13枚）は互いに素なので， 通りです．
3 乗法原理 ― 直積は掛け算
定理 6 (乗法原理).
有限集合 と の直積 について，
が成り立ちます．
注意 7.
乗法原理は「独立した選択を順番にする」状況に対応します． から1つ選び， から1つ選ぶ方法の数は です．ここで鍵となるのは， の選び方が の選び方に依存しないことです．
例 8 (パスワード).
英大文字26文字と数字10文字を使って，「英字2文字 + 数字3桁」のパスワードを作る方法は， 通りです．各文字の選択が独立なので乗法原理が適用できます．
4 順列と組合せ ― 直積の変形
定義 9 (順列).
個の異なるものから 個を選んで並べる方法の数を と書き，
です．
これは乗法原理の自然な応用です．1番目の選択肢は通り，2番目は（1番目と異なるので）通り，…，番目は通りです．
定義 10 (組合せ).
個の異なるものから 個を選ぶ（順序を区別しない）方法の数を と書き，
です．
注意 11.
を で割る理由は明快です．順列は「選んで並べる」ので，同じ 個の要素が 通りの順番で数えられています．順序を無視したいので で割ります．これは対称群による商集合を考えていることに相当します．
5 全射の数え上げ ― 包除原理への伏線
定義 12 (全射の数え上げ).
元集合 から 元集合 （）への全射（surjection）の個数を とおくと，
です．
注意 13.
この公式はなぜ交互に足したり引いたりするのでしょうか？ これは包除原理の典型的な応用で，第3回の記事で詳しく解説します．直感的には，「少なくとも1つの要素が像に現れない」ケースを補正しているのです．
例 14 (競プロでの数え上げ).
AtCoder の数え上げ問題を解くとき，最初にやるべきことは何を数えているのかを集合として定式化することです．「 個のボールを 個の箱にすべての箱が非空になるように入れる方法」は，集合 から集合 への全射の数そのものです．
6 まとめ
数え上げとは集合の濃度を求めることです
加法原理は直和（互いに素な和集合）に対応します
乗法原理は直積（独立な選択の組合せ）に対応します
順列・組合せは乗法原理の自然な帰結です
全射の数え上げは包除原理への入口です
次の記事では，組合せ（二項係数）がなぜこんなにも多くの場面に現れるのか，その秘密に迫ります．