Relation between coefficients of $(x+1)^n$ and choosing $k$ elements from a set ot size $n$?

Question

What do binomials have to do with sets? It seems so random that $n \choose k$ gives you the number of ways you can choose $k$ elements from a set of $n$ elements while at the same time gives you the coefficients of an expanded binomial raised to a given power. Binomials and sets seem like completely different concepts. Does the variable $x$ in $x^2 + 2x + 1$ have anything to do with sets?

Answer 1

The following might help in seeing the reasoning behind Greg Martin's answer, which I just up-voted but his answer could be a bit too concise for someone who hasn't worked through these ideas before.

Notation: In what follows, ellipses (i.e. $\cdots$) denote the continuation of a finite sum, not the continuation of an infinite sum.

You're probably familiar with expansions such as the following, which come from the distributive law. (I'm actually using extended distributive laws, which follow from the associative property of addition and more than one application of the standard distributive law, but for the present purpose it's probably too much of a distraction to go deeper into that rabbit hole.)

$$(A+B+C+\cdots)(a+b+c+\cdots)$$

$$= \; (A+B+C+\cdots)(a) \; + \; (A+B+C+\cdots)(b) \; + \; (A+B+C+\cdots)(c) \; + \; \cdots$$

$$ = \;\; (Aa+Ba+Ca+\cdots) \; + \; (Ab+Bb+Cb+\cdots) \; + \; (Ac+Bc+Cc+\cdots) \; + \; \cdots$$

This possibly bewildering maze of symbols can be summarized by noticing each term in the first original factor gets paired (or shakes hands with) each pair in the second original factor. In classes going back to at least the mid 1980s I used to call this "super FOIL".

Now let’s use this to examine what happens when we expand positive integer powers of $(x+1).$

$$(x+1)^2 \; = \; (x+1)(x+1) \; = \; (x+1)(x) + (x+1)(1) \; = \; (x)(x) + (1)(x) + (x)(1) + (1)(1) $$

This can be summarized by saying one adds all products formed by picking a term from $(x+1)$ and picking a term from $(x+1),$ then multiplying the two terms picked. Note that this results in a sum of $2 \cdot 2 = 2^2 = 4$ products to be added.

$$(x+1)^3 \; = \; (x+1)(x+1)^2 \; = \; (x+1)(\text{what we just did}) $$

$$ = \; (x)(\text{what we just did}) + (1)(\text{what we just did}) $$

This can be summarized by saying one adds all products formed by picking a term from $(x+1)$ and picking a term from the expansion of $(x+1)^2,$ then multiplying the two terms picked. Note that this is equivalent to adding all products formed by picking a term from $(x+1)$ and picking a term from $(x+1)$ and picking a term from $(x+1),$ then multiplying these three terms. Moreover, this results in a sum of $2 \cdot 2 \cdot 2 = 2^3 = 8$ products to be added.

$$(x+1)^4 \; = \; (x+1)(x+1)^3 \; = \; (x+1)(\text{what we just did}) $$

$$ = \; (x)(\text{what we just did}) + (1)(\text{what we just did}) $$

This can be summarized by saying one adds all products formed by picking a term from $(x+1)$ and picking a term from the expansion of $(x+1)^3,$ then multiplying the two terms picked. Note that this is equivalent to adding all products formed by picking a term from $(x+1)$ and picking a term from $(x+1)$ and picking a term from $(x+1)$ and picking a term from $(x+1),$ then multiplying these four terms. Moreover, this results in a sum of $2 \cdot 2 \cdot 2 \cdot 2 = 2^4 = 16$ products to be added.

Clearly, when carrying this out, some of the products we're adding are going to the be same. For example, in the case of $(x+1)^4$ all of the products $(1)(x)(x)(x)$ and $(x)(1)(x)(x)$ and $(x)(x)(1)(x)$ and $(x)(x)(x)(1)$ are the same, as each is equal to $x^3.$

At this point let's consider a specific problem that should now be enough to show how expanding $(x+1)^n$ involves combinatorics with sets.

Problem: What is the coefficient of $x^5$ in the expansion of $(x+1)^9$?

Solution: Prior to combining like terms, the expansion of $(x+1)^9$ consists of a sum of $2^9$ products of $9$ terms being multiplied together, where each of the terms is either $x$ or $1.$ The only way to get an $x^5$ term in this manner is when exactly $5$ of the terms is an $x$ and exactly $4$ of the terms is a $1.$ For example, three such products are $(1)(x)(x)(x)(1)(x)(x)(1)(1)$ and $(x)(x)(x)(x)(1)(x)(1)(1)(1)$ and $(1)(1)(1)(1)(x)(x)(x)(x)(x).$ The coefficient of $x^5$ will simply be how many of these products show up, which is the same as the number of ways we can place five $x$'s into $9$ parentheses. Note that the number of ways we can place these five $x$'s is the same as the number of ways we can choose $5$ parentheses from $9$ parentheses, which is equivalent to the number of ways we can choose $5$ elements from a set of $9$ elements. Incidentally, this is an unordered choice -- combinations, not permutations -- since the apparent ordering of the parentheses is simply an artifact of the fact that we're considering the parentheses as distinct objects.

Answer 2

Imagine that you want to find the coefficient of $x^k$ in $(x+1)^n$. Think of the $n$ copies of $x+1$ as having $n$ different colors and written as $(x+1)(x+1)(x+1)\cdots(x+1)$. Every time we choose $k$ different color $x$s and the $1$s of the other $n-k$ colors, we add $1$ to the coefficient of $x^k$. How many ways are there of choosing $k$ of the $n$ different $x$s...?