組合せ数学
選んだものがどの順番で並ぶかは問題でなくて、それぞれのものは一回までしか選べないときあり得る組合せの数は
C ( n , r ) = n ! r ! ( n − r ) ! = ( n r ) {\displaystyle C(n,r)={{n!} \over {r!(n-r)!}}={n \choose r}}
になる。ここで n は選ぶ候補の数で、r は選択の回数である。
たとえば10個の数があってそのうちから5個を選ぶ選び方は 10 ! 5 ! ( 10 − 5 ) ! = 252 {\displaystyle {{10!} \over {5!(10-5)!}}=252} 通りある。
組合せ数学は理論構築と同じくらい、(特に20世紀後半以降は)与えられた問題を解決することが目標になっている。組合せ数学のうちで最も古く取っ付きやすいものはグラフ理論であり、今では他の様々な分野と結びつけられている。
組合せ論的な問いの例として、52枚のトランプカードの並べ方は何通りあるか?というものが挙げられる。これに対する答えは 52! (52 の階乗)であり、この数は(だいたい 8.065817517094 × 10)、8 の後ろにゼロが67個もついている驚くべきスケールの大きさだとも言える。これは例えば無量大数(10)に匹敵するほど大きい。
別の種類の問題には、n人の人でいくつかのグループを作るとき、それぞれの人が少なくとも1つのグループに属し、どの2人をとっても共通してちょうど1つのグループに属しており、どの2グループをとっても共通の人がちょうど1人ずついて、n-1人以上からなるグループがないような分け方はあるか?というものがある。答えはnにより、今でも部分的な回答しかえられていない。 組み合わせ論的な記述の最も古い記録はインドに見いだすことができる。紀元前6世紀にスシュルタ(en:Sushruta)によって書かれた医学書スシュルタ・サミタ(en:Sushruta Samhita)には六つの味を63通りに組み合わせることができると書かれている。苦味、酸味、塩味、甘味、渋味、辛味を一つだけ使うか二つ一緒に使うか、三つ同時に使うか、などなど。ここで、単純な味は6種類あり、二つの組み合わせは15種類あり、三つの組み合わせは20種類ある、などがいえる。紀元前300年頃にジャイナ教の数学者によって書かれたバガバティ・スートラは
ものが並ぶ順番を考えていて、それぞれものは一回しか選べないときに可能な並べ方の数は
P ( n , r ) = n ! ( n − r ) ! = n ( r ) {\displaystyle P(n,r)={\frac {n!}{(n-r)!}}=n_{(r)}}
になる。ここで n は選ぶ候補として考えているものの数で r は選択の回数、! 記号は階乗を表す慣用的な記号、 n ( r ) {\displaystyle n_{(r)}} は降冪を意味するポッホハマー記号である。
例えば5人の人から3人を選び出して並べる方法は 5!/(5-3)! = 60 通りある。
r = n のとき(つまり選ぶ候補になっているものをすべて選ぶとき)には公式は
n ! ( n − n ) ! = n ! 0 ! = n ! {\displaystyle {\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!}
となる。ただし 0! = 1 と解釈することにする。
例えば、3人の人がいるとき、その人たちを並べる方法は 3! つまり 3 × 2 × 1 = 6 通りある。これは、最初の人として3人のうち一人を選ぶことができ、2番目の人として残りの二人のうちどちらかを選ぶことができるが、そうすると最後に並ぶ人はもう選択の余地がないからである。これらを掛け合わせて全体の可能性の数をえる。