The relationship between the number of combinations and the binomial coefficients

Combination of $$$n$by $$$k$called sampling of $$$k$elements taken on a set containing $$$n$items. The same element cannot be selected several times; the order in which we are given a decision on the election of a particular element is not taken into account. The number of all possible combinations of $$$n$by $$$k$equally $$$_n ^ k$- coefficient in Newton's binomial. A fact known to every student: you can read about it in Wikipedia or in any textbook, where combinations and combinatorics are generally mentioned.

But why these two numbers are equal is not explained anywhere. Perhaps everyone considers this fact obvious and does not require any additional explanation.

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

Let's start with a specific example. Take the amount $$$(a + b)$and we will raise it to some degree, for example, to the fourth.

$$

$$(a + b) ^ 4 = (a + b) (a + b) (a + b) (a + b).$$

Let us open the brackets on the right, but we will not give such terms, use them to write degrees, and forget about commutative multiplication for a minute, i.e. We will not change the order of factors in terms:

$$

$$(a + b) ^ 4 =$$

$$

$$(a + b) (a + b) (a + b) (a + b) =$$

$$

$$((a + b) (a + b)) ((a + b) (a + b)) =$$

$$

$$(aa + ab + ba + bb) (aa + ab + ba + bb) =$$

$$

$$aa (aa + ab + ba + bb) + ab (aa + ab + ba + bb) +$$

$$

$$ba (aa + ab + ba + bb) + bb (aa + ab + ba + bb) =$$

$$

$$aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb +$$

$$

$$baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb.$$

Let's think of the terms in the final polynomial as character strings. We got 16 lines 4 characters long. Understand why 16 is easy. Every time we multiply the 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. finally got $$$2 \ times 2 \ times 2 \ times 2 = 2 ^ 4 = 16$.
')
We assume that if the element in the string is $$$a$then it is not “chosen”, but if $$$b$then "selected". In this case, the string $$$aaaa$corresponds to the case when none of the 4 elements was chosen, but the string $$$bbbb$- the case when all items are selected.

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

Now recall the commutativity of multiplication and the notation "degree". All these lines can be written as $$$a ^ 2b ^ 2$and in the original amount we get:

$$

$$aabb + abab + abba + baab + baba + bbaa =$$

$$

$$a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 =$$

$$

$$6a ^ 2b ^ 2.$$

The coefficient 6 is the answer to our question about the number of ways to select two elements. It is not surprising, because when we give such terms, we count the number of factors in which $$$a$and $$$b$come in equally. That is, we count the number of lines in which the same number of elements is “selected”.

Let us return to the initial sum and give all the terms. For clarity, I will explicitly record a factor of 1 and will use the fact that $$$a ^ 0 = b ^ 0 = 1$.

$$

$$(a + b) ^ 4 = 1a ^ 4b ^ 0 + 4a ^ 3b ^ 1 + 6a ^ 2b ^ 2 + 4a ^ 1b ^ 3 + 1a ^ 0b ^ 4.$$

In such a record to find out the number of ways to choose $$$k$items from $$$4$just look at the coefficient before the term in which $$$b$enters into $$$k$-th degree

By the way, note that $$$1 + 4 + 6 + 4 + 1 = 16 = 2 ^ 4$. This is another property of the binomial coefficients, which becomes obvious if we recall that we started with a polynomial in which $$$2 ^ 4$terms.

For the general case

$$

$$(a + b) ^ n = C_n ^ 0a ^ nb ^ 0 + C_n ^ 1a ^ {n-1} b ^ 1 + ... + C_n ^ na ^ 0b ^ n$$

$$

$$\ sum_ {k = 0} ^ {n} {C_n ^ k} = 2 ^ n.$$

The notation is very simple: $$$C$bottom worth $$$n$- degree of brackets, top $$$k$- the degree to which the term is $$$b$.

Or, as we now know, $$$n$this is the number of elements in the set from which we make a sample, $$$k$- the number of items we choose.

I will add that usually the definition of the binomial coefficient is not given through the product $$$a$and $$$b$, and through the product $$$(1 + x) ^ n$and in the polynomial, which is obtained in the end, there is only $$$x$(because when $$$a = 1$any degree $$$a$is equal to one). The essence of this does not change, but to notice the combinatorial essence of the resulting formula becomes more difficult.