2008-09-03

A Taste of Combinatorics

It is summer, and Bengt is on the beach. He is hungry, so he goes to buy ice cream.
"How many flavours are there?" he asks the salesman.
"There are n flavours today."
"Then I would like a number of cones, each with k different flavours."
"And no two cones must be identical? Ah, that's a classic problem of combinatorics."
"No, that's too easy. And that way, I would get some cones that are almost identical. No, I want there to be no two cones that have p flavours in common."

  1. Let's start with something easy: Suppose p = 1; in other words, no two cones have any flavours in common. How many cones will Bengt get?

  2. Then the classic problem, where p = k; no two cones are identical. How many cones does Bengt get?

  3. Finally, the problem Bengt is really concerned with, for a general p. How many cones?