Basic Concepts and Principles of Combinatorics
Definition: Different groups composed of any elements are called combinations of these elements.
Example 1: From the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, many different combinations of 2, 3, 4, ... digits can be formed. Some of them will differ only in the order of digits, for example, 123, 8056, 96, 312, 231, 321.
All possible combinations are classified into three types:
Definition: Combinations of $n$ elements taken $m$ at a time are combinations that consist of $m$ elements taken from the given $n$ elements, and differ by at least one element. The number of combinations of $n$ elements taken $m$ at a time is denoted as $C_n^m$ and is found by the formula
$$C_n^m = \frac{n!}{m!(n-m)!} \quad\quad (1)$$
Note that by definition
$$n! = 1 \times 2 \times 3 \times 4 \times 5 \times ... \times n \quad (n \in N)$$
$$0! = 1$$
Example 2: From 10 candidates for the same position, three must be selected. How many possible selections are there?
Solution: All possible selections are combinations of 10 candidates taken 3 at a time, which differ by at least one candidate, i.e., these combinations are combinations. According to formula (1), their number is
$$C_{10}^3 = \frac{10 \times 9 \times 8}{1 \times 2\times 3} = 120.$$
Definition: Arrangements of $n$ elements taken $m$ at a time are combinations that consist of $m$ ements taken from the given $n $ elements, and differ either by the composition of elements or by their order. The number of arrangements of $n$ elements taken $m$ at a time is denoted as $A_n^m$ and is found by the formula:
$$A_n^m = n(n-1)(n-2)...(n-m+1) = \frac{n!}{(n-m)!}\qquad (2)$$
Example 3: According to the curriculum, second-year students study 10 disciplines. For one day, classes from 4 disciplines can be scheduled. How many ways can the schedule be made for one day?
Solution: All possible schedules for one day are combinations of 10 disciplines taken 4 at a time, which differ either by the disciplines or by their order, i.e., these combinations are arrangements. According to formula (2), their number is
$$A_10^4 = 10 \times 9 \times 8 \times 7 = 5040$$
Definition: Permutations of $n$ elements are combinations consisting of these $n$ elements and differing in their order. The number of permutations of $n$ elements is denoted as $P_n$ and is found by the formula
$$P_n = 1 \times 2 \times 3 \times ... \times (n-1) \times n = n! \qquad\qquad (3)$$
Example 4: How many five-digit numbers can be written using five different digits (excluding zero)?
Solution: The combinations that form five-digit numbers from five different digits differ by the order of digits, i.e., these combinations are permutations of five elements. According to formula (3), their number is
$$P_5 = 5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$$
Example 5: In a box of 10 items, 2 are defective. Six items are selected at random. What is the probability that all selected items are standard?
Solution: Event $A$ – 6 standard items are selected. According to the problem condition, the order in which 6 items are selected does not matter, so these will be combinations of 10 items taken 6 at a time. Therefore, the number of all possible elementary outcomes will be
$$n = C_{10}^6.$$
Event $A$ is favorable to only combinations of 6 items taken from 8 standard ones in any order, i.e.,
$$m = C_8^6.$$
Thus, according to the classical definition of the probability of event $A$, we have
$$P(A) = \frac{C_8^6}{C_{10}^6} = \frac{8!}{6!\times2!}: \frac {10!}{6! \times4! } = \frac{8!\times6!\times4!}{6!\times 2! \times10!} = \frac{2}{15}$$
Basic Concepts and Principles of Combinatorics
Sum Principle. If set $A$ contains $n$ elements and set $B$ contains $m$ elements, and $A \cap B = \emptyset,$ then the set $A \cup B$ contains $n + m$ elements.
Product Principle. If set $A$ contains $n$ elements and set $B$ contains $m$ elements, then the set $C$ of all possible pairs $(a, b)$ where $a \in A$ and $b \in B$ contains $n \times m$ elements.
Example 6. In a basket, there are 4 apples of the first variety and 5 apples of the second variety. Two apples are taken at random. Find the probability that these apples are of different varieties.
Solution. Let event $A$ be that the two randomly taken apples are of different varieties.
There are 9 apples in total, and the number of combinations of 2 apples taken from 9 is $C^2_9.$
Thus, the total number of possible outcomes is $C^2_9.$
The event $A$ will be supported by combinations formed from pairs of apples of different varieties. According to the product principle, the number of such pairs will be $m = C_4^1 \times C_5^1$.
Using the classical definition of probability, we obtain the desired probability of event $A:$
$$P(A) = \frac{m}{n} = \frac{C_4^1\times C_5^1}{C_9^2} = \frac{4!}{3!} \times \frac{5!}{4!}: \frac{9!}{2!\times 7!} = \frac{4!\times 5! \times 2! \times 7!}{3! \times 4! \times 9!} = \frac{5}{9}$$
