積が36になる3つの因数の組み合わせの計算方法

[nabeyang]

こんにちは、nabeyangです。

整数をある数の因数に分ける、一般的な計算方法が無いかと思い、質問します。

例えば積が36で、3つの因数に分ける場合は

(36, 1, 1), (18, 2, 1), (12, 3, 1), (9, 4, 1), (9, 2, 2),

(6, 6, 1), (6, 3, 2), (4, 3, 3)

の8通りです。これを僕は36の約数(36, 18, 9, 6など)をあたまに括り出すようなことを

繰り返して求めたのですが、それだと場合の数が事前に分からないし、

36だとか3の数が少し大きくなるだけで、手では負えなくなってしまいます。

もう少し賢い方法は無いでしょうか？

[クロメル]

むむむ、難しいものですね。

たぶん、「正の整数」を「正の整数の和」として、

どう分けることができるか。

1+1+1+1=4,

1+1+2=4,

1+3=4,

2+2=4

4=4

みたいな計算を求めるステップが必要だと思います。

これを本問題では、指数部分に応用すればいいのだと思います。

しかし、重複部分（二重に数えている場合等）を考慮しないと、

いけなかったり、大変ですね(^^;)。

[Limg]

思いつきですが、こんな方法は「一般的な計算方法」になりませんか？

(1) 与えられた被分解数Nに対し、素因数分解を施し素因数配列[ni]を作る。
例： N = 36 = 2 * 2 * 3 * 3 ⇒ [ni] = [2, 2, 3, 3]

(2) 分解数Mの因数分解とは、[ni]の要素をM組に分けることと等価になります。

(3) 解答の組合せ数Cは、Mと[ni]の要素数Lで予測できると思います。

重複するケースを除外するのが結構面倒と思いますが、
大体の見当を付けるには、全てが異なる数と見なして計算すれば少し楽できると思います。

[nabeyang]

Limgさん、クロメルさん、

ありがとうございます。細かいところは理解する

努力が必要そうで、理解できていませんが、

アルゴリズム的なアプローチなら個別の例を計算できそうだと

感じました。

nabeyang

[kuhcrow]

こんにちは、kuhcrowです。

わたしも全然わからないので、en.wikipedia などざっと見てみました。

nabeyangさんの問題、整数をある数の因数に分ける、

ことを「整数の乗法的分割」、

クロメルさんの正の整数を「正の整数の和」に表す

ことを「整数の加法的分割」、

LimgさんのようにN個のものを分けることを

「集合の分割」というそうです。

加法的分割は同じN個のもの（すなわちN個の１）の分け方、

集合の分割は異なるN個のもの分け方ということになります。

以下は簡単に分かります。

・Nが素数巾 p^k ならその乗法的分割は k の加法的分割できまる

・Nが異なる素数の積、すなわち素因数分解したときの各指数がすべて１

　なら、集合の分割と同じになる

でも一般の場合はとっても難しそうですね‥

集合の分割の場合の数を、ベル数というそうですが、

これは要素の数 N に対して当然急激に大きくなり、

Limgさんの方法では大変かもしれません。

例えば B(26)=49631246523618756274 とか？

http://oeis.org/A000110/list

P.S.

en.wikipedia をぱらぱら見ていたら、

なぜか「源氏物語」が出てきました。

B(5)=52 個の分け方が書いてあるそうです。

http://en.wikipedia.org/wiki/Bell_number#History

[クロメル]

kuhcrowさん、

おお、なるほど、うまくまとめて頂き、嬉しいです^^。

難しい計算をしようとしていることは分かりました(^^;)。