O'Reilly logo

Concrete Mathematics: A Foundation for Computer Science, Second Edition by Oren Patashnik, Donald E. Knuth, Ronald L. Graham

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5. Binomial Coefficients

Let’s take a breather. The previous chapters have seen some heavy going, with sums involving floor, ceiling, mod, phi, and mu functions. Now we’re going to study binomial coefficients, which turn out to be (a) more important in applications, and (b) easier to manipulate, than all those other quantities.

Lucky us!

5.1 Basic Identities

The symbol Image is a binomial coefficient, so called because of an important property we look at later this section, the binomial theorem. But we read the symbol “n choose k.” This incantation arises from its combinatorial interpretation—it is the number of ways to choose a k-element subset from ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required