組み合わせ論において、除法は計数原理です。これは、あるタスクを n 通りの手順で実行できる場合、そのタスクを実行する方法はn / d通りあり、各方法wに対して、 n通りの方法のうちちょうどd通りが方法wに対応するというものです。簡単に言うと、除法は、物を数える際に「重要でない」違いを無視する一般的な方法です。[ 1 ]
セットに適用
集合の観点から言えば、「有限集合Aが、それぞれd個の要素を持つ n 個の互いに素な部分集合の和集合である場合、 n = | A |/ dとなる。」[ 1 ]
関数として
関数の観点から定式化された除法則：「f がAからBへの関数であり、AとBは有限集合である。また、すべての値y ∈ Bに対して、 f ( x ) = yとなる値x ∈ Aがちょうどd 個存在する場合（この場合、fはd対 1であると言う）、 | B | = | A |/ dとなる。」[ 1 ]
例
円卓の例の視覚的表現例１
円卓に4人が座る方法はいくつありますか？ただし、各人が同じ左隣と右隣に座る場合、2つの座り方は同じとみなします。
- この演習を解決するには、まずランダムに席を選び、それを1人目に割り当てます。残りの席は、テーブルを時計回りに順番に番号を付けていきます。最初の席を選ぶときは4席、2番目は3席、3番目は2席、最後の席は1席から選べます。したがって、4! = 24通りの座り方があります。しかし、左右の隣の人が同じでない場合にのみ異なる配置を考慮するため、4席に1席だけを選ぶことになります。
- 1番席を選ぶ方法は4通りあるので、割り算の法則（n / d ）により、4人がテーブルを囲む場合の座席配置は24/4 = 6通りあります。
例２
全部で6個の色のついたレンガがあり、そのうち4個は赤、2個は白です。これらを並べる方法はいくつありますか？
- すべてのレンガの色が異なる場合、それらを並べる方法は全部で6! = 720通りになりますが、レンガの色は一定なので、次のように計算します。
- 4つの赤いレンガは4! = 24通りの並べ方ができる。
- 白いレンガ2個には2! = 2通りの並べ方がある。
- 4つの赤レンガと2つの白レンガの配置の総数 = 6 ! / 4!2! = 15。
参考文献
- ローゼン、ケネス・H（2012）。離散数学とその応用。マグロウヒル・エデュケーション。ISBN 978-0077418939。
さらに読む
- Leman, Eric; Leighton, F Thompson; Meyer, Albert R; Mathematics for Computer Science, 2018. https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
