1

i (1以上9以下)を含むならば、i がi 個含む数について、
オンライン整数列大辞典のA108571(https://oeis.org/A108571)に載っています。
また、この条件をみたす数の個数は
66712890763701234740813164553708284
であることも載っています。
この個数を次のコードで求めました。

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 = 10
s = 0
(1..n - 1).each{|i|
  # i個の文字を使用
  (1..n - 1).to_a.combination(i){|ary|
    s += c(ary)
  }
}
p [n, s]

さて上記において、使用する文字数毎にその個数を求めていますが、
これを桁数(1から45)毎にその個数を求めるにはどうすればよいでしょうか?

なお、d(1から25)桁の個数は以下に載っています。
https://oeis.org/A127007/list

2 件の回答 2

2

1~9を使用するかどうかの511パターンの組み合わせを全て列挙し、使用桁の和が桁数に一致するものを抽出すればよいかと思います。

(1..45).each{|i|
    s = 0
    (1..9).each{|j|
        (1..9).to_a.combination(j){|ary|
            if ary.inject{|sum, n| sum + n} == i then
                s += c(ary)
            end
        }
    }
    p s
}
1

先に、1~9を使用するかどうかの2^9 - 1パターンの組み合わせをその和毎に分類してみました。

def factorial(m)
  (1..m).inject(:*)
end

def c(d, ary)
  factorial(d) / ary.map{|m| factorial(m)}.inject(:*)
end

n = 10
h = {}
(1..n - 1).each{|i|
  # i個の文字を使用
  (1..n - 1).to_a.combination(i){|ary|
    d = ary.inject(:+)
    h.key?(d) ? h[d] = h[d].push(ary) : h[d] = [ary]
  }
}

s = 0
(1..n * (n - 1) / 2).each{|d|
  t = 0
  h[d].each{|ary|
    td = c(d, ary)
    s += td
    t += td
  }
  p t
}
# 条件をみたす数の個数
p [n, s]

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。