11554


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

[code]

    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]
    
[/code]

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

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


CC BY-SA 3.0
2015-06-20T08:07:09.910
11551
2015-06-20T11:34:12.310
2015-06-20T11:34:12.310
5363
5363
question
ruby アルゴリズム
i (1以上9以下)を含むならば、i がi 個含む数について


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

[code]

    (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
    }
    
[/code]


CC BY-SA 3.0
2015-06-20T09:28:46.023
11554
2015-06-20T09:28:46.023
5750
11551
answer


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

[code]

    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]
    
[/code]


CC BY-SA 3.0
2015-06-20T10:18:44.430
11555
2015-06-20T11:31:00.280
2015-06-20T11:31:00.280
5363
5363
11551
answer