sample.rb

#!/usr/bin/env ruby
# coding: utf-8

total = 500
coins = [1, 5, 10, 50, 100, 500]
size = total/coins.min
ret = 1.upto(size).inject([]) do |r, n|
  comb = coins.repeated_combination(n)
  r + comb.select do |c|
    c.inject(:+).eql?(total)
  end
end

p "pattern = #{ret.compact.sort}"
p "pattern.size = #{ret.size}"