ホーム >> 組合せ >> 積が一定の互いに素な $3$ 数の組の個数
hide or visible

問題の説明

$47!=1\times 2\times \cdots \times 47$ のことです.題材は整数ですが,個数を数える問題なので,組合せの問題です.$47!$ はとても大きな数なので,問題の条件を満たす $a,b,c$ の組も非常にたくさんあることが容易に予想されます.したがって,ひとつひとつ数えていてはキリがありません.何らかの工夫が必要です.

ちなみに,答えはかなり大きな数になります.

ヒント

この問題の一番のポイントは,$a,b,c$ のどの $2$ つも互いに素 という条件です.言い換えれば,$a,b,c$ のどの $2$ つも共通の素因数をもちません.この条件をいかに使うかが鍵となります.

解答例

$47!$ の素因数は, $$2,3,5,7,11,13,17,19,23,29,31,37,41,43,47$$ の合計 $15$ 個です.$abc=47!$ であり,$a,b,c$ はどの $2$ つも互いに素なので,共通の素因数をもちません.たとえば,$a$ が素因数 $17$ をもてば,$b$ も $c$ も $17$ を素因数にもつことはありません.つまり,これら $15$ 個の素因数は,完全に $3$ つに分割されなければならないということです.したがって,この問題は $15$ 個のものを $3$ つのグループに分ける組分けの問題に帰着されます.(組分けに関しては,→重複順列の基礎 を参照してください)

そこでまず,上の $15$ 個の数字を $3$ つの箱 $A,B,C$ に分けることを考えます.ただし,空の箱があってもよいとします.この分け方は $3^{15}$ 通りです.もし,空の箱がちょうど $2$ つあるとすると,その分け方は $a,b,c$ のうち,$2$ つが $1$ ということに対応し, $a < b< c$ という条件を満たさないので除外します.(空の箱がちょうど $2$ つあるような分け方は $3$ 通りです) そうでないときは,グループの分け方が問題の条件の $a,b,c$ の組に対応します.ただし,$3!=6$ 通りのグループ分けがちょうどひとつの $a,b,c$ の組に対応します.

よって,求める組の数は, $$\frac{3^{15}-3}{3!}=2391484$$ $\boxed{2391484}$ 個です.