Solution!

gistfile1.rb

def factorial(n)
  product = 1
  1.upto(n) do |k|
    product *= k
  end
  return product
end

def choose(n,k)
  if k > n
    return 0
  end
  return factorial(n)/(factorial(k)*factorial(n-k))
end

# ignore this it's broken, see count2
def count(n, s)
  if s == 0
    return factorial(n)
  end

  if n == 1
    if s == 0
      return 1
    elsif s == 1
      return 0
    end
  end

  sg = n/2
  fg = n - sg

  result = 0
  if s <= fg
    0.upto(s) do |i|
      result += choose(s,i) * count(fg, i) * choose(n-s, fg-i) * count(sg, 0)
    end
  else
    0.upto(fg) do |sfg|
      0.upto(s-fg) do |ssg|
        next if sg - ssg > fg - sfg # check the count(3,3) case to see why this is necessary... but this is probably just a band-aid
        # it's still wrong... i think it depends on whether the first one takes
        # one same from the second or not...

        # result += choose(fg, sfg) * count(fg, sfg) * choose(sg-ssg, fg-sfg) * 
        #   choose(s-fg, ssg) * count(sg, ssg) * choose(sg - ssg, sg - ssg)
        x = choose(fg, sfg) * count(fg, sfg) * choose(sg-ssg, fg-sfg) *  # <---- it takes them from non-same sg when it COULD take some that are the same.
          choose(s-fg, ssg) * count(sg, ssg) * choose(sg - ssg, sg - ssg)
        if n == 7 && s == 7
          # puts "Sfg: #{sfg}, Ssg: #{ssg}, X: #{x} (n: #{n} s: #{s})"
        end
        result += x
      end
    end
  end

  return result
end

$memo = Hash.new

def count2(n, s)
  if s == 0
    return factorial(n)
  end

  if n == 1
    if s == 0
      return 1
    elsif s == 1
      return 0
    end
  end

  if $memo[[n,s]]
    return $memo[[n,s]]
  end

  sg = 1
  fg = n - sg

  result = 0
  if s <= fg
    0.upto(s) do |i|
      result += choose(s,i) * count2(fg, i) * choose(n-s, fg-i) * count2(sg, 0)
    end
  else
    result += count2(fg, fg-1) * count2(sg, 0) * fg
  end

  $memo[[n,s]] = result

  return result
end

1.upto(100) do |n|
  puts "#{n}: #{count2(n,n)}"
end