Sunday, September 27, 2015

Some more interesting combinatorics

I tried to solve the following problems from the book by Lovasz and got wrong - well atleast the basic thinking was right :)

Problem 1: We have $20$ different presents that we want to distribute to $12$ different children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?
Problem 2: We have $20$ kinds of presents with unlimited supply of each kind. We want to give this to $12$ children. It is not required that all children get something, it is possible that all presents are given to the same child. In how many ways can we distribute the presents?

What do you think the answers are?

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...