C++で解く：n個からr個を選ぶ順列のうち、特定のk個が常に一緒になる場合の総数

n、r、k が与えられたとき、n 個の物の中から r 個を選ぶ順列のうち、特定の k 個が常に一緒（隣接）して現れるような選び方が何通りあるかを求める問題を考えます。

入力 : n = 8, r = 5, k = 2

出力 : 960


入力 : n = 6, r = 2, k = 2

出力 : 2

この問題では「n 個から r 個を選ぶ順列」のうち「特定の k 個が必ずまとまって登場する」場合の数を求める必要があるため、組み合わせ論に関する基礎知識が少し必要になります。

解法のアプローチ

まず、この問題に対する計算式を導き出すことが重要です。式さえ立てられれば、あとはそれをプログラムに実装するだけで答えが求まります。

導かれる公式は次のとおりです。

答え = k! × (r − k + 1) × P(n − k, r − k)

ここで P(x, y) は「x 個から y 個を選んで並べる順列の総数」を表します。この式の考え方は以下のとおりです。

• k 個のグループ内部の並び替えは k! 通り
• その k 個のかたまりは、r 個の並びの中で (r − k + 1) か所のいずれかに配置できる
• 残りの (r − k) 個は、残りの (n − k) 個から選んで並べるため P(n − k, r − k) 通り

実装例

#include <bits/stdc++.h>
using namespace std;
int fact(int n){ // 階乗を計算する関数
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int npr(int n, int r){ // 順列を求める
    int pnr = fact(n) / fact(n - r);
    return pnr;
}
int countPermutations(int n, int r, int k){ // 導出した公式
    return fact(k) * (r - k + 1) * npr(n - k, r - k);
}
int main(){
    int n = 8;
    int r = 5;
    int k = 2;
    cout << countPermutations(n, r, k);
    return 0;
}

出力

960

コードの解説

上記のコードでは、まず階乗を計算する fact() 関数と、順列 P(n, r) を求める npr() 関数を定義しています。そして、導出した公式「k! × (r − k + 1) × P(n − k, r − k)」を countPermutations() 関数として実装し、答えを計算しています。

なお、大きな数を扱う場合はオーバーフローに注意が必要です。実際の競技プログラミングなどでは long long 型を使用するか、問題の指定に応じて適切な剰余を取ることをおすすめします。

まとめ

本記事では、「n 個の物から一度に r 個取り出す順列のうち、特定の k 個が常に一緒になる場合の総数」を求める問題を解きました。数式的なアプローチの導出から、それを C++ プログラムとして実装する方法までを学びました。

同じロジックは C、Java、Python などの他の言語でも同様に実装できます。このチュートリアルが皆さんのお役に立てば幸いです。