CSE 21
Math for Algorithms

Counting with Categories

In counting with categories, there are multiple arrangements and some are treated as the same (due to the existence of one or more "categories"). Thus, in order to determine the number of "actual" arrangements, we have to divide the total number of arrangements by the size of each category.

def. size of one category
number of arrangements that are the same in one particular way

You can think of counting with categories as the "division rule."

Example. A simple example is fixed-density binary strings. We pose the question "how many length-n binary strings contain k ones (for k ≤ n)?" This is the same as asking "how many ways are there to order n elements, where k elements (ones) are all the same and the other n - k elements (zeros) are also all the same?"

There are n! ways to order n elements. But some of the elements are identical, so we're doing a lot of overcounting. We have to divide out by the number of ways to order the k ones and the number of ways to order the n - k zeros (k! arrangements are the same due to ones; (n - k)! arrangements are the same due to zeros).

So the answer is n! / (k! (n - k)!), or n choose k.