Combination rearrangement and placement and Newton binom examples

The following configurations are used to formulate and solve problems in combinatorics: permutations, placement, combinations.

A set is called ordered if each element of this set is associated with a certain number (element number) from 1 to n , where n is the number of elements of the set.

Rearrangement

Suppose we have some ordered set N consisting of n different elements. A permutation of n elements is a set of elements of the set that differ from the initial one only in the order of the elements. Usually the permutation is denoted as P n and is calculated by the formula:

P n = n !

Example:

Find the number of permutations of a set consisting of three elements: A , B , C.

According to the formula, the number of permutations will be equal to 3! = 6.

Indeed, these are sets (ABC), (ACB), (BAC), (BCA), (CAB), (CBA).

Accommodation

Suppose we have some ordered set N consisting of n different elements. An arrangement of n elements in k will be an ordered subset of k non-repeating elements selected from a set consisting of n elements. Usually the permutation is denoted as A n k and is calculated by the formula:

Example:

Find the number of placements of the set consisting of four elements: A , B , C , D two by two, i.e. how many different arrangements of two elements can be made of the specified set.

According to the formula, the number of placements will be equal to 4! / (4-2)! = 24/2 = 12.

Indeed, these are sets (AB), (BA), (AC), (CA), (AD), (DA), (BC), (CB), (BD), (DB), (CD), (DC ).

Combination.

Suppose we have some ordered set N consisting of n different elements. A combination of n elements in k will be a subset of k non-repeating elements selected from a set consisting of n elements. Subsets that differ only in the order of the elements (but not the composition), are considered the same, this combination differs from placements. Usually the combination is denoted as С n k and is calculated by the formula:

Example:

Find the number of combinations of the set consisting of four elements: A , B , C , D two by two.

According to the formula, the number of combinations will be equal to 4! / 2! (4-2)! = 24/4 = 6.

Indeed, these are sets (AB), (AC), (AD), (BC), (BD), (CD).

Combination properties:

1. With n 0 = 1.

2. С n k = С n n - k .

3. С n k = С n - 1 k - 1 + С n - 1 k

4. С n 0 + С n 1 + С n 2 + ... + С n n - 1 + С n n = 2 n .

The combination plays an important role in mathematics. In particular, it is used in the Newton binomial.

Binomial theorem.

Newton's binom is a relation that allows to represent the expression ( a + b ) n ( n ∈ Z + ) as a polynomial, namely:

( a + b ) n = a n + C n 1 a n - 1 b + C n 2 a n - 2 b 2 + ... + C n k a n - k b k + ... + C n n - 1 a b n - 1 + b n .

The numbers C n 1 , C n 2 , ..., C n n - 1 are called binomial coefficients.

Using the following table, you can determine the values ​​of binomial coefficients for any degree. It is constructed as follows - any number is formed by the sum of the adjacent numbers above it. That is why this table is called the Pascal triangle.

0

one

one

eleven

2

1 2 1

3

1 3 3 1

four

1 4 6 4 1

five

1 5 10 10 5 1

6

1 6 15 20 15 6 1

7

1 7 21 35 35 21 7 1

eight

1 8 28 56 70 56 28 8 1

The degree of n is indicated on the left and the values ​​of the corresponding binomial coefficients on the right.

Example:

Represented as a polynomial ( a + 1) 4 .

According to the table, in the case of the fourth degree, the coefficients of the resulting polynomial will be equal to 1, 4, 6, 4, 1.

And, indeed ( a + 1) 4 = a 4 + 4 a 3 + 6 a 2 + 4 a + 1.