150620

Ruby


i (1以上9以下)を含むならば、i が i 個含む数の個数について(1)

i (1以上9以下)を含むならば、i が i 個含む数について

オンライン整数列大辞典のA108571に載っている。

また、この条件をみたす数の個数は
66712890763701234740813164553708284
であることも載っている。

さて、N進法のとき条件をみたす数の個数を求めてみる。

def factorial(m)

  (1..m).inject(:*)

end

def c(ary)

  sum = 0

  p = 1

  ary.each{|m|

    sum += m

    p *= factorial(m)

  }

  factorial(sum) / p

end

N = 20

(2..N).each{|n|

  s = 0

  (1..n - 1).each{|i|

    # i個の文字を使用

    (1..n - 1).to_a.combination(i){|ary|

      s += c(ary)

    }

  }

  p [n, s]

}

出力結果

[2, 1]

[3, 5]

[4, 80]

[5, 14381]

[6, 40885253]

[7, 2163451135829]

[8, 2525544441942679544]

[9, 75742010013818779294524291]

[10, 66712890763701234740813164553708284]

[11, 1942822997165179351555175450239287744555392665]

[12, 2080073366819317156363661211242237402694399273780324072649]

[13, 90119293418056939454016830629777394012980315428451803426514614495110994]

[14, 172455511938741999081801502699156952559204424009474834769855450110414719504

150224997558]

[15, 157986102253960981574445206052521197511653328373414551764354038895571390274

01448911234591184156199226978]

[16, 746442030816246157764653429242897250983760556051433948548329751407825856488

15412540158487503830483934552059902954171577605]

[17, 194945695614188169608419067260711262969994712345859557219548670082563980886

14502291258692509506601658052856424259637610563629746085130521420291]

[18, 300275814547418946820910664259718512972412140953192527318957576882139850782

55181991824197487253872154559471957395361481032033404019653356456027127282226298

8138910740]

[19, 289899468213502373867902815950578001530607279689328109339320546553053002418

86575154255270349007564269427340241998153036135878840443110759520091417773370119

0727029967708522620675887212828851]

[20, 185783061526404568110804790044210372472519765825214788837615964098447729062

50157408042296617329443569724170810698372794541477017718173686018716815466159770

719024873776518211993768384857812465924625616829947997242136]