場合の数｜同じものを含む順列について
今回は、同じものを含む順列について学習しましょう。
同じものを含む順列は重複順列に似ているので、よく勘違いする人がいます。両者の違いをしっかり理解しましょう。
記事の画像が見辛いときはクリックすると拡大できます。
重複順列と同じものを含む順列との違いを知ろう
重複順列は、重複を許すという条件で、異なるｎ個のものからｒ個取って並べた順列のことです。ですから、並べるものを選ぶことができ、また選んだものが他のものと重複しても許されます。
それに対して、同じものを含む順列は、並べるものの中に同じ種類のものが混じった状態で、それらを並べた順列です。
たとえば、「１，１，５の３つの数を使ってできる３桁の整数の個数」は、重複順列の総数ではありません。この個数は、同じものを含む順列の総数になります。
例からも分かるように、並べるものがすでに決まっています。並べるものを自分で選ぶことはできません。選ばれたものの並べ替えと考えると良いでしょう。
このように重複順列と同じものを含む順列とは全く異なります。定義を正しく覚え、その意味を正しく理解しましょう。
同じものを含む順列の総数を求めよう
ｎ個の中にいくつかの種類があって、それぞれｐ個、ｑ個、ｒ個、……ずつあるとします。これらｎ個のものを一列に並べる順列が同じものを含む順列です。
ところで、ｎ個を並べる順列の総数は以下のように表されます。
ｎ個を並べる順列の総数
\begin{align*} \quad n! \text{（通り）} \end{align*}ｎ個のものを並べる順列の総数はｎ！通りですが、これはｎ個のものがすべて異なるときの総数です。
もし、ｎ個の中に同じものがｐ個、ｑ個、ｒ個、……ずつ含まれているとすればどうなるでしょうか。この場合、順列の総数ｎ！通りの中には、重複する並べ方が含まれています。
たとえば、ｐ個が同じものであれば、ｐ個の並べ方ｐ！通りを重複して数え上げていることになります。
同じ種類ごとに重複する並べ方を求め、その重複ぶんを１通りにしなければなりません。この重複ぶんの扱いさえ忘れなければ、同じものを含む順列の総数を簡単に求めることができます。
一般に、ｎ個の中に同じものがｐ個、ｑ個、ｒ個、……ずつあるとき、その並べ方の総数は以下のように表されます。
同じものを含む順列の総数
$n$ 個の中に同じものが $p$ 個、$q$ 個、$r$ 個、……ずつあるとき、その並べ方の総数は
\begin{align*} \quad \frac{n!}{p! \ q! \ r! \cdots} \text{（通り）} \end{align*}ただし
\begin{align*} \quad p + q + r + \cdots = n \end{align*}また、同じものを含む場合、順列の総数を数え上げてしまうと、同じものの並べ替えが重複することになります。ですから、並べるというよりも置く場所を選ぶと捉えた方が良いでしょう。
「ｐ個（またはｑ個、ｒ個）のものを置く場所を選ぶ」という考え方をすると、同じものを含む順列の総数を組合せの総数で求めることができます。
置き場所を選ぶだけで並べないので組合せ
- ｎカ所からｐ個を置く場所の選び方は、nＣp通り
- nＣp通りのそれぞれについて、ｎ－ｐカ所から ｑ個を置く場所の選び方は、n-pＣq通りずつ
- n-pＣq通りのそれぞれについて、ｎ－ｐ－ｑカ所からｒ個を置く場所の選び方は、n-p-qＣr通りずつ
- 以下、同様
このことから、同じものを含む順列の総数は、組合せの総数を用いて以下のように表されます。
同じものを含む順列と組合せの関係
$n$ 個の中に同じものが $p$ 個、$q$ 個、$r$ 個、……ずつあるとき、その並べ方の総数は、$p$ 個（または $q$ 個、$r$ 個）のものを置く場所を選ぶと考えると
\begin{align*} \quad {}_n \mathrm{ C }_p \times {}_{n-p} \mathrm{ C }_q \times {}_{n-p-q} \mathrm{ C }_r \times \cdots \text{（通り）} \end{align*}ただし
\begin{align*} \quad p + q + r + \cdots = n \end{align*}ｐ個（またはｑ個、ｒ個）は同じものなので、並べ方を考える必要はありません。
ですから、同じものを含む順列では、同じものをどのように並べるのかではなく、どのように置くのかという発想の方が適切です。
上述のように、順列のように見えても、捉え方によっては組合せで解決できることもあります。何に注目するかをしっかりと考えましょう。これまでをまとめると以下のようになります。
同じものを含む順列を扱った典型的なテーマ
同じものを含む順列を扱った典型的なテーマがいくつかあります。ここでは２つ紹介します。
同じものを含む順列を扱った典型的なテーマ
- 整数の個数
- 最短距離の経路
同じものを含む順列と言えば、この２つのテーマが入試でもよく出題されます。記述形式でも出題されるので慣れておきましょう。
整数の個数
最初のテーマは「整数の個数」です。整数の個数を求める問題では、数字を並べ替えて整数をつくります。
このような問題では、順列の総数を考えることが多いです。
例題１
$1 \ , \ 2 \ , \ 3 \ , \ 4$ の $4$ つの数字を使ってできる $4$ 桁の整数の個数
例題１では、４つの数字に同じものが含まれていません。ですから、例題１は、順列を扱った基本的な問題です。
異なる４つの数字を使って４桁の整数をつくるので、異なる４個のものを並べた順列の総数を求めれば良いことが分かります。
例題１の解答例
$1 \ , \ 2 \ , \ 3 \ , \ 4$ の $4$ つの数字を並べる順列の総数を求めればよいので
\begin{align*} \quad {}_4 \mathrm{ P }_4 &= 4! \\[ 7pt ] &= 4 \cdot 3 \cdot 2 \cdot 1 \\[ 7pt ] &= 24 \text{（個）} \end{align*}計算結果から、異なる４つの数字を使ってできる４桁の整数は全部で２４個です。
次の例題２はどうでしょう。
例題２
$1 \ , \ 2 \ , \ 2 \ , \ 4$ の $4$ つの数字を使ってできる $4$ 桁の整数の個数
例題２では、同じ数字が含まれています。ですから、例題２は、同じものを含む順列を扱った問題です。
例題１の４つの数字のうち、３が２に変わったと考えます。例題１で求めた４！個（２４個）の整数の中から、重複する個数を除きます。
たとえば、以下のような整数が重複するようになります。
重複ぶんの一例
$1234 \ , \ 1324$ が、例題 $2$ ではともに $1224$ になる。
$3214 \ , \ 2314$ が、例題 $2$ ではともに $2214$ になる。
例題１では、２と３の並べ方が変わると異なる整数になりました。しかし、例題２では同じ整数になります。
２と３の並べ方は２！通りあるので、４つの数字の並べ方４！通りのそれぞれについて、２！通りずつ重複していることが分かります。
例題２の解答例
$1 \ , \ 2 \ , \ 2 \ , \ 4$ の $4$ つの数字を並べる順列の総数 $4!$ のそれぞれについて、$2$ つの $2$ の並べ方 $2!$ 通りずつが重複するので
\begin{align*} \quad \frac{4!}{2!} &= \frac{4 \cdot 3 \cdot 2!}{2!} \\[ 7pt ] &= 12 \text{（個）} \end{align*}計算結果から、１，２，２，４の４つの数字を使ってできる４桁の整数の個数は全部で１２個です。
例題１，２のポイントと解答例をまとめると以下のようになります。
例題２では、組合せを利用して整数の個数を求めることができます。「１，２，２，４の数字を４カ所のどこに置くか」を考える問題と捉えることができます。
例題２を組合せで解く
- ４カ所から１個の１を置く場所の選び方は、4Ｃ1通り
- 4Ｃ1通りのそれぞれについて、３カ所から１個の４を置く場所の選び方は、3Ｃ1通りずつ
- 3Ｃ1通りのそれぞれについて、２カ所から２個の２を置く場所の選び方は、2Ｃ2通りずつ
このときの組合せの総数を計算すると、同じ結果になります。
例題２の別解例
$1 \ , \ 2 \ , \ 2 \ , \ 4$ の $4$ つの数字を並べる順列の総数は、$4$ つの数字の置き方を選ぶ組合せの総数に等しいので
\begin{align*} \quad &{}_4 \mathrm{ C }_1 \times {}_3 \mathrm{ C }_1 \times {}_2 \mathrm{ C }_2 \\[ 7pt ] = \ &4 \cdot 3 \cdot 1 \\[ 7pt ] = \ &12 \text{（個）} \end{align*}順列の総数で求める場合、どうしても重複する並びを含んでしまいます。ですから、最初から重複を除外できる組合せの方が気分的には楽な気がします。
最短距離の経路
次のテーマは「最短距離の経路」です。
例題３
図のような縦または横の道を通って $P$ から $Q$ に行くとき、最短距離の経路が何通りあるか。
方眼のように縦線と横線でいくつかの区画に分けられています。この縦線や横線を通ってＰからＱに移動します。
ＰからＱに移動するとき、下方向や左方向に移動すると最短で移動できません。ですから、上方向と右方向の移動だけを考えれば良いことが分かります。
最短距離の経路になるとき、どの経路であっても上方向の移動が３回、右方向の移動が４回の計７回の移動が行われます。
このことから、最短距離の経路は、上方向と右方向の２種類の同じものを含む順列の総数を考えれば良いことが分かります。
最短距離の経路を考えるとき、上方向または右方向の矢印を並べ替えて経路をつくると分かりやすくなります。
７個の矢印のうち、３個が上方向の矢印で、４個が右方向の矢印です。これらを並べ替えて最短距離の経路を作ります。
このときの順列の総数は以下のようになります。
例題３の解答例
最短距離の経路となるのは上方向の道 $3$ 本と右方向の道 $4$ 本の合計 $7$ 本の道を通るときである。これらを並べたときの順列の総数は
\begin{align*} \quad \frac{7!}{3! \cdot 4!} &= \frac{7 \cdot 6 \cdot 5 \cdot 4!}{3 \cdot 2 \cdot 1 \cdot 4!} \\[ 7pt ] &= 35 \text{（通り）} \end{align*}７個の矢印の並べ方７！通りには、上方向の矢印の並べ方３！通りずつと、右方向の矢印の並べ方４！通りずつとが重複しています。この重複ぶんを除くために除算しています。
また、最短距離の経路が７個の矢印の組合せでできることが分かるので、組合せを利用することもできます。
７カ所のうち、上方向の矢印３個を置く場所の選び方と、右方向の矢印４個を置く場所の選び方を考えます。
このときの経路の求め方は以下のようになります。
例題３の別解例
最短距離の経路となるのは上方向の道 $3$ 本と右方向の道 $4$ 本の合計 $7$ 本の道を通るときである。
経路の総数は、$7$ 本の道のうち、$3$ 本を上方向の道に選び、残り $4$ 本を右方向の道に選ぶときの組合せの総数に等しい。
\begin{align*} \quad {}_7 \mathrm{ C }_3 \times {}_4 \mathrm{ C }_4 &= \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \times 1 \\[ 7pt ] &= 35 \text{（通り）} \end{align*}同じものを含む順列では、順列の総数を利用すると、必ず重複ぶんを除かなければなりません。しかし、組合せなら重複ぶんを除く処理をせずに済みます。
どちらで解くかは好みによりますが、どちらの考え方も理解しておきましょう。
例題３のポイントと解答例をまとめると以下のようになります。
次は、同じものを含む順列を扱った問題を実際に解いてみましょう。