順列と組合せの総数の素因数分解を求める

動機

順列や組合せの総数は、その名前どおり組合せ的に増加してしまうため、計算機で扱いたいときは工夫が必要です。また、結果が十分小さくても、途中の乗算でオーバーフローしてしまうおそれもあります。

ここでは、「階乗の素因数分解を求める」で示した方法を応用して、順列や組合せの総数も、素因数分解のまま求めてしまうことにします。

（以下、数式部分が見づらい場合は、数式をどれでも右クリックし、Math Settings -> Math Renderer から適当なものをお選びください）

順列の総数

順列の総数 $_nP_k=\frac{n!}{(n-k)!}$ の分子と分母をそれぞれ素因数分解で表しておけば、結果の素因数分解は各素数の指数を計算するだけで求められます。指数の計算も減算のみです。

つまり、例えば、

 _{12}P_{4}=\frac{12!}{8!}=\frac{2^{10}\times3^5\times5^2\times7^1\times11^1}{2^7\times3^2\times5^1\times7^1}=2^3\times3^3\times5^1\times11^1

のように、簡単に求められます。

組合せの総数

組合せの総数は $_nC_k=\frac{n!}{(n-k)!\times k!}$ と表せますが、同様です。

例えば、

_{12}C_{4}=\frac{12!}{8!\times4!}=\frac{2^{10}\times3^5\times5^2\times7^1\times11^1}{2^7\times3^2\times5^1\times7^1\times2^3\times3^1}=3^2\times5^1\times11^1

となります。

コード

次のコードは、それぞれの階乗（の素因数分解）を求めてから結果を出すのではなく、各素数ごとに結果の指数を直接求めるように工夫しています。

最終結果はこれらの素因数分解を求めるところまでです。例えば、総数どうしの比率から確率を求めたい場合などは、このままで扱えることもあります。しかし、総数そのものを実際に求めるにはこれらを掛け合わせることになり、その場合はオーバーフローに注意する必要があります。

permcomb.c

#include <stdio.h>

void
permutation(int n, int k) {
  int prime[n+1];
  int i, j;

  for (i = 2; i <= n; i++) {
    prime[i] = 1;
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      for (j = i*2; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      prime[i] = 0;
      for (j = i; j <= n; j *= i) {
        prime[i] += n/j;
        if (j <= n-k) prime[i] -= (n-k)/j;
      }
      if (prime[i])
        printf("%d^%d\n", i, prime[i]);
    }
  }
  printf("\n");
}

void
combination(int n, int k) {
  int prime[n+1];
  int i, j;

  for (i = 2; i <= n; i++) {
    prime[i] = 1;
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      for (j = i*2; j <= n; j += i) {
        prime[j] = 0;
      }
    }
  }
  for (i = 2; i <= n; i++) {
    if (prime[i]) {
      prime[i] = 0;
      for (j = i; j <= n; j *= i) {
        prime[i] += n/j;
        if (j <= n-k) prime[i] -= (n-k)/j;
        if (j <= k) prime[i] -= k/j;
      }
      if (prime[i])
        printf("%d^%d\n", i, prime[i]);
    }
  }
  printf("\n");
}

int
main(void) {
  permutation(12, 4);
  combination(12, 4);
  permutation(100, 50);
  combination(100, 50);
  return 0;
}