1
$\begingroup$

I bashed together a clunky ruby script to find the sum total of $n \choose r$ where $r = 1,n$

I wanted to determine how many lines of output I could expect from a script that produces all possible combinations of an array. I found that, for any $n$, the sum total $= 2^n$

$ ruby nchrsum.rb
6 choose 6 == 1
6 choose 5 == 6
6 choose 4 == 15
6 choose 3 == 20
6 choose 2 == 15
6 choose 1 == 6
6 choose 0 == 1
Total n choose r where n = 6 and r = 1,6:
       64

Holds true for all $n$ I tried -- but why?

$\endgroup$
2
  • 1
    $\begingroup$ In your array application, consider marking each array element with a 0 for "not taken" or a 1 for "taken". There are two choices for each array element and therefore $2^n$ ways to mark the entire array. $\endgroup$ – Will Orrick Jul 27 '15 at 17:40
  • $\begingroup$ $2^n = (1 + 1)^n = \sum_{i=0}^{n}\binom{n}{i}$ $\endgroup$ – steven gregory Jul 27 '15 at 17:45
7
$\begingroup$

It's from the Binomial Theorem, expanding $(1+1)^n$

$\endgroup$
1
  • $\begingroup$ Perfect answer. $\endgroup$ – David Simmons Jul 27 '15 at 17:35
4
$\begingroup$

Another explanation is to observe that, since $\,\dbinom nk$ is the number of subsets of $k$ elements in a set of $n$ elements, the sum of all these coefficients ($n$ fixed) is but the number of all subsets of a set of $n$ elements – which is known to be $2^n$.

$\endgroup$
4
  • 1
    $\begingroup$ +1, I was just writing this myself. I feel like this explanation doesn't hide the fact that the identity can be obvious. $\endgroup$ – preferred_anon Jul 27 '15 at 18:05
  • 1
    $\begingroup$ @Daniel Littlewood: Technically, the proof with $(1+1)^n$ is quite simple. But it doesn't explain, in my opinion, why it is so. $\endgroup$ – Bernard Jul 27 '15 at 18:08
  • $\begingroup$ @Bernard: They're all explanations, I think; but different explanations can link to the reader's previous knowledge in different ways, which is why having multiple answers to a question can be so useful. $\endgroup$ – Brian Tung Jul 27 '15 at 23:48
  • $\begingroup$ I totally agree with this point of view. $\endgroup$ – Bernard Jul 27 '15 at 23:57
3
$\begingroup$

One more explanation, given a CS or CS-like background: Consider the set of all $n$-bit numbers, from $0$ through $2^n-1$, inclusive; there are thus $2^n$ of them, by inspection. (For instance, there are $2^3 = 8$ numbers from $0$ through $2^3-1 = 7: 0, 1, 2, 3, 4, 5, 6, 7$.)

We could, also, count them as follows: How many of the numbers have no $1$ bits? We choose none of the $n$ bits to be equal to $1$, so the answer is

$$ \binom{n}{0} $$

How many of them have exactly one $1$ bit? We choose one of the $n$ bits to be equal to $1$, so the answer is

$$ \binom{n}{1} $$

How many of them have exactly two $1$ bits? We choose two of the $n$ bits to be equal to $1$, so the answer is

$$ \binom{n}{2} $$

And so on.

Of course, this way of counting must equal our first answer, so we can combine all of these separate counts to obtain

$$ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n} = 2^n $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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