September 09, 2009

My Combinatorics Problem, Let Me Show You It

Because I am too lazy to solve it myself, and too dumb to find it in the literature: How many ways are there to file N letters among k folders, such that no folder is empty? (What I am really interested in doing is counting the number of non-isomorphic functions of a discrete random variable.) The first reader to provide a solution gets a free year's subscription to the blog.

Update, 2 hours later: Thanks to reader M.L. for pointing me to Stirling numbers of the second kind, and to readers L.Z. and Jake Hofman for reading the sentence in parentheses and directing me to Bell numbers and counting surjections. Also to the four (!) others who wrote in after them with solutions. — Now that I see the answer, I suspect I did this problem in one of David Griffeath's classes...


Posted at September 09, 2009 14:33 | permanent link

Three-Toed Sloth