📚 学習ノート中学・高校・大学の学習内容に沿った自学習サイト

場合の数の応用

重複組合せ・円順列・同じものを含む順列を導出から理解し、辞書式順序で何番目かを数える。

この単元の目標
  • 重複組合せ・円順列・同じものを含む順列の公式を導出を踏まえて使い分けられる
  • 制約つきの場合の数を場合分け・余事象・ブロック分けで処理できる
  • 辞書式順序で特定の並びが何番目かを系統的に数えられる
📑 目次
  1. 応用パターンの全体像
  2. 導出: 公式はこうしてできる
  3. 辞書式順序で何番目か
  4. 練習問題
  5. 確認クイズ

応用パターンの全体像

基本の順列・組合せに慣れたら、「区別のないもの」「丸い配置」「同一要素の混在」という拡張パターンに進みます。どの公式を使うべきかは、対象が区別できるか、配置に端がないか、同じ要素を含むかという3点で判定します。公式を丸暗記するより、それぞれがどう導けるかを一度自分で追いかけておくと、初見の問題でも慌てません。

パターン状況公式
重複組合せn 種類から重複を許して r 個選ぶnHr=n+r−1Cr{}_n\mathrm{H}_r = {}_{n+r-1}\mathrm{C}_r
円順列n 人を円形に並べる（回転を同一視）(n−1)!(n-1)!
数珠順列円順列で裏返しも同一視(n−1)!2\dfrac{(n-1)!}{2} （n は 3 以上）
同じものを含む順列n 個中に同一のものが p 個と q 個n!p! q!\dfrac{n!}{p!\,q!}

導出: 公式はこうしてできる

🔍 重複組合せの公式の導出

  1. 整数解の問題に言い換える
    x1+x2+⋯+xn=rx_1 + x_2 + \cdots + x_n = r

    種類 i を選ぶ個数を非負の整数 xix_i とすれば、選び方と整数解が1対1に対応する

  2. 丸と仕切りで表す
    ∘  ∘  ⋯  ∘⏟r  ∣  ⋯  ∣⏟n−1\underbrace{\circ\;\circ\;\cdots\;\circ}_{r}\;\underbrace{\mid\;\cdots\;\mid}_{n-1}

    r 個の丸と n-1 本の仕切りを一列に並べた図が1つの選び方を表す

  3. 並べ方を数える
    n+r−1Cn−1=n+r−1Cr{}_{n+r-1}\mathrm{C}_{n-1} = {}_{n+r-1}\mathrm{C}_r

    全体 n+r-1 個の位置から仕切りの置き場所を選べばよい

🔍 同じものを含む順列の導出

  1. 一旦すべて区別する
    n!n!

    同一の p 個と q 個に仮のラベルを付ければ、異なる n 文字の順列 n! 通り

  2. ラベルの重複分を割り引く
    n!p! q!\dfrac{n!}{p!\,q!}

    ラベルの付け替え p! 通り（および q! 通り）はどれも同じ並びに見えるため割る

円順列は「誰か1人を基準に席を固定する」と通常の並びに帰着します。基準を決めないまま数えると、同じ配置を何度も数えてしまうのが典型的なミスです。

辞書式順序で何番目か

辞書式順序とは、辞書が単語を並べるのと同じ規則で並べた順序のことです。何番目かを求めるときは、注目する並びより前に現れる並びの総数を、上位の桁から順に確定させながら数えます。各段階では「残りの要素のうち、確定済みの数字より小さいもの」の個数に残りの階乗を掛ければよく、単純な積算で処理できます。

  1. 1番目の要素が注目値より小さいケースを数え、残りは自由なので (n−1)!(n-1)! を掛ける
  2. 1番目の要素を注目値に確定し、2番目以降でも同じ操作を繰り返す
  3. 並びが完全に一致したら最後に自分自身の 1 を足して答えにする
例題: 辞書式順序での順位

1, 2, 3, 4, 5 の順列を辞書式順に小さいほうから並べるとき、31425 は何番目か。

解答・解説

先頭が 1 か 2 の並びは 2×4!=482 \times 4! = 48 個。3, 1 を確定したあと3番目が 2 の場合は 2!=22! = 2 個（31245, 31254）。31425 の直前までに他の該当はないので、48+2+1=48 + 2 + 1 = **51番目**

練習問題

練習問題

  1. 6 種類のお菓子から、重複を許して合計 10 個買うときの買い方を求めよ。

    ヒント

    各種類の個数を xix_i とすると x1+⋯+x6=10x_1 + \cdots + x_6 = 10 の非負整数解。

    解答・解説

    6H10=15C5={}_6\mathrm{H}_{10} = {}_{15}\mathrm{C}_5 = **3003通り**

  2. 8 人を円形のテーブルに座らせるとき、特定の 2 人が隣り合う座り方は何通りか。

    ヒント

    隣り合う 2 人を 1 つのブロックとみなす。

    解答・解説

    ブロックと他の 6 人の計 7 体の円順列 (7−1)!=720(7-1)! = 720 通りに、ブロック内の並び 2 通りを掛けた **1440通り**

  3. 1, 2, 3, 4 の順列を辞書式順にすべて並べるとき、2341 は先頭から何番目か。（発展）

    ヒント

    先頭が 1 の並び、次に 21xx、231x の順で数える。

    解答・解説

    3!+2!+1!=93! + 2! + 1! = 9 個が前にあるので **10番目**

  4. a, a, a, b, c の 5 文字を一列に並べるとき、aaa が連続する並び方は何通りか。（発展）

    ヒント

    aaa を 1 つのブロックとみなす。

    解答・解説

    ブロック, b, c の 3 つの並び 3!=3! = **6通り**

確認クイズ

確認クイズ

問1. 5 人を円形に並べる円順列の総数はどれか。

問2. x + y + z = 6 を満たす非負の整数解の個数はどれか。

問3. a を 2 個、b を 2 個、c を 1 個含む 5 文字の並び方は何通りか。

📝 メモこの端末のみに保存
メモ欄はページ読み込み後に使えるようになります。