\n#! /usr/bin/ruby -w\n\n# With one argument, the product 1*2*..*n\n# With two arguments with m <= n, the product m*(m+1)*..*n\n# With two arguments with n < m, 1.\n@known_factorials = { "0|1"=>1 };\ndef factorial(n, m=1)\n  unless @known_factorials.has_key?(n.to_s + "|" + m.to_s)\n    n = n.to_i;\n    m = m.to_i;\n    product = 1;\n    (m..n).each {|i| product *= i}\n    @known_factorials[n.to_s + "|" + m.to_s] = product\n  end\n  @known_factorials[n.to_s + "|" + m.to_s]\nend\n\n# Sums an array.\ndef sum(numbers)\n  ans = 0;\n  numbers.each{|i| ans += i}\n  ans\nend\n\n# The number of ways to divide a set of n things into a combination of\n# sizes[0] and sizes[1] and ... and leftover things.  If sizes has only one\n# argument, is the familiar "n choose m" function.\ndef choose(n, *sizes)\n  n = n.to_i\n  ans = factorial(n, n + 1 - sum(sizes));\n  sizes.each { |i| ans /= factorial(i) };\n  ans\nend\n\n# This calls the function with each descending sequence whose terms sum to\n# total and whose maximimum element is max (that optionally starts with the\n# initial subsequence).\ndef call_with_each_descending_sequence(total, max, function, initial=[])\n  # Special case for 1\n  sequence = initial + (1..total).collect { 1 };\n  function[sequence];\n\n  (2..max).each {|i|\n    sequence = initial + [i];\n    if i < total\n      call_with_each_descending_sequence(total - i, i, function, sequence)\n    elsif i == total\n      function[sequence];\n    end\n  }\nend\n\n# Calculate the number of possible birthday assignments to some number of\n# people with a given maximimum number of people getting the same day.\ndef possible_birthday_assignments(people, max_one_day)\n  ans = 0;\n  call_with_each_descending_sequence(\n    people.to_i,\n    max_one_day.to_i,\n    proc {|duplicate_sequence| \n      people_to_duplicate_sequence = choose(people, *duplicate_sequence);\n\n      day_groupings = []\n      last_count = 0;\n      duplicate_sequence.each {|count|\n        if (last_count != count)\n          day_groupings.push(1);\n          last_count = count;\n        else\n          day_groupings[-1] += 1;\n        end\n      }\n      days_to_day_groupings = choose(365, *day_groupings);\n\n      ans += days_to_day_groupings * people_to_duplicate_sequence;\n    }\n  );\n  ans;\nend\n\ncount = possible_birthday_assignments(*ARGV);\nprob = ( count * 1_000_000 / 365**(ARGV[0].to_i) ).to_f / 1_000_000;\nputs "Odds #{prob} that #{ARGV[0]} people have at most #{ARGV[1]} birthdays together";\n