C++で同じ行・列に重複しないようにn×n交点へ4つのアイテムを配置する組み合わせの求め方

この問題では、整数 n が与えられます。縦に n 本、横に n 本の直線が引かれており、これらの直線は合計 n² 個の交点を作ります。求めたいのは、どの行（横方向）にもどの列（縦方向）にも複数のアイテムが含まれないという条件のもとで、この交点のうち4か所にアイテムを配置する方法が全部で何通りあるのかということです。

具体例を見ながら問題を理解していきましょう。

入力

n=4

出力

24

解説

まず、n 本ある横線の中から、アイテムを置く対象となる4本を選びます。この選び方は ⁿC₄ 通りです。

続いて、各横線には n 本の縦線が交差しているため、最初に選んだ横線上にはアイテムを置ける位置が n 通りあります。しかし、同じ列への重複配置は禁止されているため、2本目の横線では使える列が1つ減って n−1 通り、3本目では n−2 通り、4本目では n−3 通りになります。

以上より、配置方法の総数は次の式で求められます。

ⁿC₄ × n × (n−1) × (n−2) × (n−3)

なお、n=4 の場合は ⁴C₄ × 4 × 3 × 2 × 1 = 24 となり、先ほどの出力結果と一致します。

アルゴリズムの実装例

#include <iostream>
using namespace std;
long long placeItems(int n) {
    return (1LL * (1LL *
    ((n) * (n - 1) * (n - 2) * (n - 3)) / (4 * 3 * 2 * 1)) *
    ((1LL * (n) * (n - 1) * (n - 2) * (n - 3))));
}
int main() {
    int n = 4;
    cout<<"The number of way is which 4 items can be placed in the intersection of "<<n;
    cout<<" lines vertically and horizotally are "<<placeItems(n);
    return 0;
}

実行結果

The number of way is which 4 items can be placed in the intersection of 4 lines vertically and horizotally are 24

まとめ

このように、組み合わせの考え方（ⁿC₄）と順列的な掛け算（n × (n−1) × (n−2) × (n−3)）を組み合わせることで、行と列の重複制約を満たす配置の総数を効率よく計算できます。大きな n に対しても O(1) の計算量で答えが求まるため、実用的なアプローチといえます。