how many combinations of n marbles of k colors?

marbles.rb

def marbles(n, k)
    free = n - k
    if free == 0
        return 1
    end
    combos = Array.new(k,1)
    (free-1).times do
        (k-1).downto(1) do |x|
            combos[x] = combos[0..x].inject(:+)
        end
    end
    return combos.inject(:+)
end

puts marbles(10,10)
puts marbles(30,7)


# problem statement:
# There are infinite number of marbles, you are allowed to select n marbles of k different colors.  There are infinite many from each color.  You have to have at least one marbles of each color, how many possibilities for selection would you have?



#idea behind algorithm
#
# we have colors 1,2,3,4, and we have 4 free marbles
#
# if we choose 1 for first marble we can choose 1,2,3,4 for 2nd marble
#
#  continue this:
#  "if we choose ______ we can choose _____ for 2nd marble"
#      2->2,3,4
#      3->3,4
#      4->4
#
# this allows us to avoid duplicates for instance picking green green blue
# is the same as picking green blue green, the order that we pick the marbles
# doesn't matter if we end up with 2 green and one blue in the end
#
# color                      C1   C2   C3   C4
# after free marble 1       [ 1    1    1    1]
#                                 +1   +2   +3
# after free marble 2       [ 1    2    3    4]
#                                 +1   +3   +6
# after free marble 3       [ 1    3    6   10]
#                                 +1   +4  +10
# after free marble 4       [ 1    4    10  20]
#
# you will notice that the +amount is the sum of all the lower colors from
# the previous step added to the previous value, that is because C1-C3 will
# all produce a C4 in the next step, and all the C4's will produce another
# so we can choose C4 C4 C4 C4 or C3 C4 C4 C4 as possible combinations