The Old New Thing

April 14, 2014 - The Old New Thing

The geeky thrill of discovering that two things are really the same thing, just with different labels

April 14, 2014 Apr 14, 2014 04/14/14
Raymond Chen
Today's post about binomial coefficients was intended to be a warm-up for Catalan numbers, but it turns out Eric Lippert already covered them, first in the context of binary trees, then in the context of arbitrary trees and forests, and then again in the context of matched parentheses. Another way of seeing the correspondence between ...

Enumerating subsets with binomial coefficients

April 14, 2014 Apr 14, 2014 04/14/14
Raymond Chen
Inspired by the Little Program which enumerates set partitions, I decided to do the binomial coefficients this week. In other words, today's Little Program generates all subsets of size k from a set of size n. As before, the key is to interpret a recurrence combinatorially. In general, when a recurrence is of the form A + B, it means that ...