One day the king approached a shepherd. He asked, "how many sheep do you have?" Counting the sheep would have presented a problem, as they were difficult to tell apart. The shepherd knelt down, counted for a minute, and said, "25. Each sheep has four feet, and I counted 100 feet."

In mathematics, the choose function is a function on two variables, , which counts the ways a collection of k items can the chosen from a (larger collection) containing n items.

Practically speaking, you use this function to answer questions like, "how many handshakes occur when there are 25 engineers in a room and they all shake hands". Or, "If I can go to the community farm three times during the week, how many possible schedules are there?" If you get a little bit more clever, the choose function will answer questions such as, "how many ways can I distribute 100 pieces of candy to twelve children while making sure every child has at least two pieces?"

There are many mathematical expressions for the choose function. Most of them are complicated and difficult to remember. My favorite expression is for the choice function is,

I prefer this because it is backed by a fun intuitive explanation. I want you to understand this intuition. First, let's move the formula into a more convenient arrangement.

Now we can discuss the numerator, . It represents the number of ways we can make an ordered selection of items from a set of size . We have options for the first item, options for the second item, and so on. After items, we wind up with: possible ordered choices. So far so good.

The numerator is close to what we want, but it isn't exactly what the choice function should return. The numerator over-counts the choices we are interested in.

Consider the handshake example from before. Here, the numerator evaluates to , which represents twice the number of handshakes that actually occur. It accounts twice for the handshake between Eric and Micah, because this handshake corresponds to the ordered choices [Micah, Eric] and [Eric, Micah].

Or, consider the scheduling example from above. Here, the numerator evaluates to , which over counts the number of possible schedules by a factor of six. It accounts six times for the schedule "Monday, Wednesday, Thursday", because this schedule manifests itself through six unique ordered choices.

In other words, the numerator tells us how many length-k lists we can build, while we are interested in knowing how many size-k sets we can build.

In Ruby speak, we could even say,

def belong_to_same_choice(list_1, list_2):
		Set.new(list_1) == Set.new(list_2)
end

If we think about how many lists correspond to a single set, it is clear that the numerator over-counts by a factor of . The denominator, , compensates for the over-counting. It cuts the feet off of the sheep.

If you are interested in some fun math-related reading on Wikipedia, try to conceptualize belong_to_same_choice() as defining an equivalence relation on the set of ordered choices. This equivalence relation yields a collection of equivalence classes, which are all of size .

In the future, when you need to count something, and you think enumerating it might be a pain, use combinatorics! In particular, it can be useful to over-count the quantity that you are interested in, and then determine how much you have over-counted by.