Category Archives: combinatorics

Combinatorial Proofs of Two Hagen-Rothe Identities in Concrete Mathematics

There are two binomial coefficient identities in Concrete Mathematics that have bothered me for years:  They look they should have combinatorial proofs, but I couldn’t for the life of me think of what those might be.  (In Concrete Mathematics they are … Continue reading

Posted in combinatorics, lattice paths | Leave a comment

Vandermonde’s Identity from the Generalized Product Rule

Vandermonde’s Identity, is one of the more famous identities involving the binomial coefficients.  A standard way to prove it is with the following combinatorial argument. How many ways are there to choose a committee of size r from a group of n men … Continue reading

Posted in binomial coefficients, calculus, combinatorics | Leave a comment

Combinatorial Proofs for the Binomial and Alternating Binomial Power Sums

In this post I give combinatorial proofs of formulas for the binomial and alternating binomial power sums:  and Here’s the first. Identity 1. . Proof.  Both sides count the number of functions from  to subsets of .  For the left … Continue reading

Posted in binomial coefficients, combinatorics, Stirling numbers | 1 Comment

Log-Convexity of the Bell Numbers

A sequence is said to be log-convex if, for all , . In this post I give a short, combinatorial-flavored proof that the Bell numbers are log-convex.  The argument is from my answer here on Math.SE. The combinatorial interpretation of the Bell … Continue reading

Posted in Bell numbers, combinatorics, inequalities, sequences and series | Leave a comment

A Combinatorial Proof for the Power Sum

Probably the most common formula for the power sum is the one involving binomial coefficients and Bernoulli numbers , sometimes called Faulhaber’s formula: Historically, this, or a variant of it, was the first general formula for the power sum. There … Continue reading

Posted in binomial coefficients, combinatorics, number theory, Stirling numbers | Leave a comment

Yet Another Nice Proof of the Derangements Formula

A couple of posts from a few years back give proofs of the formula for , the number of derangements on n elements.  (A derangement is a permutation with no fixed points.)  Both proofs avoid the use of the principle of inclusion-exclusion, which … Continue reading

Posted in combinatorics, derangements, permutations | Leave a comment

Solving Two-Term Combinatorial Recurrence Relations, Part II

A few years ago I published a paper [2] giving a partial answer to the following question in Graham, Knuth, and Patashnik’s Concrete Mathematics (Problem 6.92): Develop a general theory of the solutions to the two-parameter recurrence A post from a few years … Continue reading

Posted in combinatorics, recurrence relations | 1 Comment