Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the sum of the first $n$ integers: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ This has always made the following bit of combinatorial sense to me. Imagine the set $\{*,1,2,\ldots,n\}$. We can choose two from this set, order them in decreasing order and thereby obtain a point in $\mathbb{N}^2$. We interpret $(i,*)$ as $(i,i)$. These points give a clear graphical representation of $1+2+\cdots+n$:

$$ \begin{matrix} &&&\circ\\ &&\circ&\circ\\ &\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\\ \end{matrix} $$

Similar identities are: $$\sum_{i=1}^n\,i^2=\frac{n(n+1)(2n+1)}{6}=\frac{2n(2n+2)(2n+1)}{24}=\frac{1}{4}\binom{2n+2}{3}$$ $$\sum_{i=1}^n\,i^3=\frac{n^2(n+1)^2}{4}=\binom{n+1}{2}^2$$ I am aware of geometric explanations of these identities, but not combinatorial ones similar to the above explanation for summing first powers that make direct use of the "choosing" interpretation of the binomial coefficient. Can anyone offer combinatorial proofs of these?

share|improve this question
1  
Written this way, I find it interesting that the binomial coefficient $\binom{2n+2}{3}$ is divisible by 4. Is there a direct combinatorial explanation for this? –  Srivatsan Dec 29 '11 at 22:19
1  
@Srivatsan: By stars-and-bars, $\binom{2n+2}{3}$ is the number of ways to write $2n-1$ as a sum of four nonnegative integers, if the order of the terms matter. The transitive closure of the rotation relation $(a+b+c+d)\sim(b+c+d+a)$ is an equivalence equation which partitions the set of sums into equivalence classes of size $4$. (An equivalence class with less than 4 different members is impossible because $2n-1$ is odd). –  Henning Makholm Dec 29 '11 at 22:31

3 Answers 3

up vote 9 down vote accepted

Here's a combinatorial proof for $$\sum_{k=1}^n k^2 = \binom{n+1}{2} + 2 \binom{n+1}{3},$$ which is just another way of expressing the sum. Both sides count the number of ordered triples $(i,j,k)$ with $0 \leq i,j < k \leq n$.

For the left side, condition on the value of $k$. For each $k$, there are $k^2$ ways to choose $i$ and $j$ from the the set $\{0, 1, \ldots, k-1\}$.

For the right side, consider the cases $i=j$ and $i \neq j$ separately. If $i = j$, then there are $\binom{n+1}{2}$ such triples. This is because we just choose two numbers from $\{0, \ldots, n\}$; the smaller must be the value of $i$ and $j$ and the larger must be the value of $k$. If $i \neq j$, then there are $2\binom{n+1}{3}$ such triples, as we could have $i < j$ or $j < i$ for the smaller two numbers.


For $$\sum_{k=1}^n k^3 = \binom{n+1}{2}^2,$$ both sides count the number of ordered 4-tuples $(h,i,j,k)$ with $0 \leq h,i,j < k \leq n$.

For the left side, once again if we condition on the value of $k$ we see that there are $\sum_{k=1}^n k^3$ such 4-tuples.

For the right side, there is a bijection from these 4-tuples to ordered pairs of two-tuples $(x_1,x_2), (x_3,x_4)$ with $0 \leq x_1 < x_2 \leq n$ and $0 \leq x_3 < x_4 \leq n$. There are $\binom{n+1}{2}^2$ such pairs, so let's look at the bijection.

The bijection: If $h < i$, then map $(h,i,j,k)$ to $(h,i),(j,k)$. If $h > i$, then map $(h,i,j,k)$ to $(j,k), (i,h)$. If $h = i$, then map $(h,i,j,k)$ to $(i,k), (j,k)$. This mapping is reversible, as these three cases correspond to the cases where $x_2 < x_4$, $x_2 > x_4$, and $x_2 = x_4$.


(Both of these proofs are in Chapter 8 of Proofs that Really Count, by Benjamin and Quinn. They give at least one other combinatorial proof for each of these identities as well.)

share|improve this answer

We give a combinatorial interpretation of the formula $$ 2^2+4^2+6^2+\cdots +(2n)^2=\binom{2n+2}{3} \qquad\qquad (1) $$ for the sum of the first $n$ even squares.

There are $\binom{2n+2}{3}$ ways to choose $3$ numbers from the numbers $1, 2, \dots, 2n+2$. We organize and count the choices in another way.

Maybe the largest number chosen is $2k+1$ or $2k+2$. If it is $2k+1$, the other two can be chosen in $\binom{2k}{2}$ ways, and if it is $2k+2$, then the other two can be chosen in $\binom{2k+1}{2}$ ways. The total is $$\frac{(2k)(2k-1)}{2} +\frac{(2k+1)(2k)}{2}\quad\text{that is,}\quad (2k)^2.\qquad\qquad(2)$$ Take $k=1, 2, 3, \dots, n$. By Formula $(2)$, the number of ways of choosing $3$ numbers from $1, 2, \dots, 2n+2$ is $$ 2^2+4^2+6^2+\cdots +(2n)^2. $$

The above argument was not purely biective, because of the ``calculation'' in Formula $(2)$. But there is a standard workaround that produces a purely bijective proof of the fact that $$ \binom{m}{2} +\binom{m+1}{2}=m^2. $$ The geometric idea is that the sum of two consecutive triangular numbers is a square. More formally, let $M$ be the collection $\{1,2,3,\dots,m\}$. Then the number of ordered pairs $(a,b)$ with $a$ and $b$ in $M$ is $m^2$. These ordered pairs are of two types: (i) the ones with $a<b$ and (ii) the ones with $a \ge b$. The number of ordered pairs $(a,b)$ with $a<b$ is just $\binom{m}{2}$. The number of ordered pairs $(a,b)$ with $a \ge b$ is the same as the number of ordered pairs $(b,a+1)$ with $b<a+1$, and this is $\binom{m+1}{2}$.

Comment: It follows by "algebra" from Formula $(1)$ that $$ 1^2+2^2+\cdots +n^2=\frac{1}{4}\binom{2n+2}{3}. \qquad\qquad(3) $$ (The algebraic division by $4$ can be bypassed by counting suitable equivalence classes, giving a pristinely bijective proof of $(3)$.)

When I first saw the usual expression $\dfrac{(n)(n+1)(2n+1)}{6}$ for the sum of the first $n$ squares, I remember thinking that the $2n+1$ somehow looks as if it does not fit in. But it does, it is actually $n$ and $n+1$ that are strange! We can think of $(n)(n+1)(2n+1)$ as ``really'' being $(1/4)[(2n)(2n+1)(2n+2)]$.

share|improve this answer

In general,

$\LARGE \sum_{i=0}^n\, \binom{i}{k}=\binom{n+1}{k+1}$.

One combinatorial interpretation for this is: the RHS is the number of ways to choose a team of $k+1$ people out of $n+1$ people numbered 1 through $n+1$. The LHS is the number of ways to choose the highest-numbered person on the team (person #$i+1$) and then choose $k$ of the $i$ lower-numbered people.

In general, you can make squares, cubes, et cetera - any polynomial, in fact - out of a linear combination of binomial coefficients, so those sums are all linear combinations of the above formulas.

share|improve this answer
    
My feeling is that this is not what the OP considers a "direct" interpretation of the binomial coefficient. –  Srivatsan Dec 29 '11 at 23:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.