「順列」とは、異なる n 個のものから、r≤n 個を取り出して1列に並べる場合の数を求めるという問題です。これを n 個の中から r 個を選ぶ順番を考慮した場合の数と定義することもできます。
順列は、数学や統計学だけでなく、様々な場面で応用されます。例えば、競技プログラミングにおいては順列の問題が出題されることがあります。また、カードゲームやロトなどでも順列の考え方が使われます。
順列の場合の数を求める式は、以下の通りです。
nPr=(n−r)!n!
ここで、n! は n の階乗を表します。すなわち、n!=n⋅(n−1)⋅(n−2)⋯2⋅1 です。
この式の意味するところは、n 個の中から r 個を選び出して1列に並べる場合の数は、n 個の中から r 個を選び出す場合の数 nCr に、その並べ方の場合の数 r! を乗じたものと等しいということです。つまり、順列は組合せと乗法原理の関係を表しています。
順列の場合の数を求める際には、以下のような考え方を用いることができます。
まず、n 個の中から1つ選ぶ方法は n 通りあります。次に、残った n−1 個の中から1つ選ぶ方法は (n−1) 通りあります。このように、選ぶ個数が減っていくごとに、選ぶ方法の場合の数が1ずつ減っていくわけです。よって、n 個から r 個を選ぶ場合の数は、以下のように求めることができます。
nPr=n(n−1)(n−2)⋯(n−r+1)
この式は、先程の式と等価であることがわかります。
なお、順列の場合の数は、組合せの場合の数よりも大きくなります。例えば、5人の中から2人を選んで列に並べる場合の数は、組合せの場合の数が10通りであるのに対して、順列の場合の数は20通りになります。つまり、順番を考慮すると場合の数が増えるということです。