2.2.1. 順列

Code: permutation.py
Test: test_permutation.py

順列とは

ものを取り出して並べるときの、可能な並べ方のことをいう。

例えば、区別できる \(5\) 個の要素から \(3\) 個を取り出し、並べる操作は次の図のように表現できる。

permutation

順列の場合の数

\(n\) 個から \(k\) 個を取り出して順番に並べるとき、場合の数は記号 \(_nP_k\) または \(P(n,k)\) で表される。
右辺は \(k\) 個の数の積となっている。
\[P(n,k) = n \times (n-1) \times \ldots \times (n-k+1)\]

または階乗を用いて、次のように表すこともできる。

\[P(n,k) = \frac{n!}{(n-k)!}\]

2つ目の式は次のように解釈できる。

  • \(n\) 個すべてを順番に並べる (\(n!\) 通り)

  • \(k\) 個目以降の \(n-k\) 個の並べ方を無視する (\((n-k)!\) で割る)

interpret_permutation

実装

概要

素数の法 \(p\) のもとで、順列の場合の数 \(P(n, k)\) を求める。

実装のポイント

階乗を予め計算しておくことで、クエリ計算量 \(\mathcal{O}(1)\) で計算できる。

計算量

  • 前処理

    • list_mod_facts(n, p) \(\mathcal{O}(n)\)

    • list_mod_inv_facts(n, p) \(\mathcal{O}(n + \log{n})\)

  • クエリ

    • mod_perm(n, k, p) \(\mathcal{O}(1)\)

コード

[1]:

from __future__ import annotations


def list_mod_facts(n: int, p: int) -> list[int]:
    f = [1 for i in range(n+1)]
    for i in range(2, n+1):
        f[i] = f[i-1] * i % p
    return f


def list_mod_inv_facts(n: int, p: int) -> list[int]:
    invf = [1 for i in range(n+1)]
    fn = 1
    for i in range(2, n+1):
        fn = fn * i % p
    invf[n] = pow(fn, p-2, p)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % p
    return invf


def mod_perm(n: int, k: int, p: int, f: list[int], invf: list[int]) -> int:
    return f[n] * invf[n-k] % p

使用例

[2]:

f = list_mod_facts(100000, 1000000007)
invf = list_mod_inv_facts(100000, 1000000007)
p = mod_perm(10, 3, 1000000007, f, invf)
print(p)

720