5桁の整数を「違う数字・同じ数字」で分類すると何種類?

<問題の意味>

パイの問題ではπ=3.14・・・の中の5桁が「すべて同じ数字」という場合を調べました。 他にどういうパターンがあるでしょうか? 右のパターンはほんの一例です。

「すべて違う数字」
「3種類の数字が1個、2個、2個」
「2種類の数字が2個と3個」・・・・・・
<数え上げ作戦>

私のとった方法です。PolynomialDistr というプログラムで以下の処理をします。

00000〜99999 を作る(5重のループ)。

数字を小さい順に並べ替える。例えば 54341 なら 13445 にする。

最初の数字に 0 を割り当てる。次の数字が同じなら 0 を割り当て、そうでなければ1つ増やして 1 を割り当てる。 こうしてすべての数をパターンに変換する。例えば 13445 であれば 01223 に変換される。

パターンの出現度数を数える。

結果は右の通りです。パイの問題ではNo.16を使いました。 「16パターンは細かすぎる」のなら5パターンまたは7パターンにまとめることができます(右下)。 例えば、11811はNo.2、72777はNo.9ですが同じ仲間だとみなしてもいいでしょう。

  1. 00000 ・・・ 10 ・・・すべて同じ数字
  2. 00001 ・・・ 225
  3. 00011 ・・・ 450
  4. 00012 ・・・ 2400
  5. 00111 ・・・ 450
  6. 00112 ・・・ 3600
  7. 00122 ・・・ 3600
  8. 00123 ・・・ 12600
  9. 01111 ・・・ 225
  10. 01112 ・・・ 2400
  11. 01122 ・・・ 3600
  12. 01123 ・・・ 12600
  13. 01222 ・・・ 2400
  14. 01223 ・・・ 12600
  15. 01233 ・・・ 12600
  16. 01234 ・・・ 30240 ・・・すべて違う数字
    計    100 000
<結果の解釈>

No.10 のパターン 01112 を例にとります。このパターンを作った数のひとつはabbbcですが(a<b<c)、他にも babbc, cabbb などいくつかあります。 それらを数え上げると (1+3+1)!/1!3!1!=20 個です。

ここでは多項分布の公式を使いましたが、別法としてこう考えてもいいです。 まずbを区別してab1b2b3c の5つを並べると5!通り。 しかし、b1,b2,b3が実は同じbだからダブって数えてしまった。そこで3!で割る。

一方、0〜9の10個から3個を選ぶ方法は10C3=120通り。 よって答えは 120×20=2400 通り。

<パターンをグループにまとめる>

16種類のパターンは次のようにまとめられます。括弧の中はどれも同じ度数です。

  1. 1種類(すべて同じ)・・・(1)
  2. 2種類・・・(2, 9), (3, 5)
  3. 3種類・・・(4, 10, 13), (6, 7, 11)
  4. 4種類・・・(8, 12, 14, 15)
  5. 5種類(すべて異なる)・・・(16)

2-5-2019, S. Hayashi