The relationship between the number of combinations and binomial coefficients

Combination of $$ by $$ called sampling from $$ elements taken on a set containing $$elements. The same item cannot be selected multiple times; the order in which we are presented with a decision on the election of an element is not taken into account. The number of all possible combinations of$$ by $$ equally $$- coefficient in Newton’s binomial. A fact known to every student: you can read about it on Wikipedia or in any textbook, where combinations and combinatorics are mentioned.

However, why these two numbers are equal is not explained anywhere. Perhaps everyone considers this fact obvious and not requiring any additional explanation.

In fact, the connection is really very simple, if you think about it. However, until some point, the connection between the coefficients of the polynomial and combinatorics was for me something of a field of magic. If this is so for you now, welcome to the cut, I will explain the obvious.

Let's start with a concrete example. Take the amount$$ and raise it to some extent, for example, to the fourth.

$$

Let’s open the brackets on the right, we won’t give similar terms, use them to write the degree, and also forget for a moment about the commutativity of multiplication, i.e. we will not change the order of the factors in the terms:

$$

$$

$$

$$

$$

$$

$$

$$

Let's think of the terms in the resulting polynomial as character strings. We got 16 lines 4 characters long. Understanding why 16 is easy. Each time we multiply by a bracket containing 2 terms, we double the number of elements in the final result. In total, we multiplied 4 brackets with two terms, i.e. eventually got$$.

We assume that if an element equals$$, then it is not “selected”, but if$$, then "selected." In this case, the line$$ corresponds to the case when none of the 4 elements were selected, and the line $$- the case when all the elements are selected.

Suppose now that we want to answer the question "how many ways can you choose two of the four elements." Given our agreement, all we have to do is count the number of lines in which there are exactly two letters$$: $$. There are exactly six of them.

Now let us recall the commutativity of multiplication and the notation “degree”. All these lines can be written as$$, and in the original amount we get:

$$

$$

$$

Coefficient 6 is the answer to our question about the number of ways to select two elements. It is not surprising, because when we present such terms, we calculate the number of factors in which$$ and $$come in equally. That is, we count the number of rows in which the same number of elements is “selected”.

We return to the initial sum and give all the terms. For clarity, I will explicitly write down the coefficient 1 and I will use the fact that$$.

$$

In such a record, to find out the number of ways to choose $$ items from $$ just look at the coefficient before the term in which $$ included in $$degree.

By the way, note that$$. This is another property of binomial coefficients, which becomes obvious if we recall that we started with a polynomial in which$$terms.

For the general case

$$

$$

The notation is very simple: $$ below stands $$ - degree of bracket, above $$ - the degree to which the term stands $$.

Or, as we now know,$$ this is the number of elements in the set from which we make a selection, $$- the number of elements that we select.

I add that usually the definition of the binomial coefficient is not given through the product$$ and $$, and through the product $$ and in the polynomial that results, there is only $$ (since when $$ any degree $$equal to one). The essence of this does not change, but it becomes more difficult to notice the combinatorial essence of the resulting formula.