If two actions A and B mutually exclude each other and action A can be performed in
k ways, and B - by n ways, then perform one of these actions (either A or B)
can be in k + m ways.
Example.
Let there be given two baskets, in one basket there are 8 red balls, in the other basket - 5 black
balls. How many ways can you pull out one ball? We can pull out either a red or a black ball.
By the rule of the sum we get that one ball can be pulled out in 8 + 5 = 13 ways.
The rule of product.
Let it be required to execute k actions sequentially. If the first action can be performed by N1
ways, the second action N2 ways, the third - N3 ways and so to the k-th action, which
can be performed in Nk ways, then all k actions can be performed in:
N = N1 * N2 * ... * Nk
ways.
Example.
Consider the baskets from the previous example. How many ways can you get two balls out?
First we can pull out either a red or a black ball. From the above example we know
that this can be done in 13 ways, so we can take out the second ball in 13 - 1 ways (one
the ball we pulled out at the first action), so we can take out 13 balls in 13 * 12 = 156 ways.
Combinations.
In combinations, the order of the elements is not important. That is, the following pairs of two symbols A and B in this case are identical: AB == BA.
Combinations without repetition.
Let's consider an example, let we have 4 books: A, B, C and D. We need to choose 2 books as a gift(!). How many ways can you do this? We need to choose from 4 items 2 items, and the order is not important. Therefore you need to find the number of combinations of 4 elements of 2.
As a result, we get 6 combinations: AB AC AD BC BD CD.
Note that here there are no repetitions (AA, BB, ...) and in fact AB is the same as BA.
The main thing is that in the set are two elements A and B.
Combination with repetition.
Let's consider an example. In the confectionery shop were sold 4 varieties of cakes: A, B, C and D.
How many ways can we buy 2 cakes?
As a result, we get 10 combinations: AB AC AD BC BD CD AA BB CC DD. As we see, in combinations there are repetitions: AA BB CC DD.
Permutation.
Permutation without repetition.
Let there be 4 symbols: A, B, C and D. How many ways you can combine two symbols from this set
avoid duplicating characters?
We got 12 ways:
AB AC AD BC BD CD
BA CA DA CB DB DC
Permutations with repetitions.
For example, let's use the condition of the problem from the previous example, but duplication of symbols is acceptable. That is, how many ways can the symbols A, B, C and D be combined in two characters?
AB AC AD BC BD CD
BA CA DA CB DB DC
AA BB CC DD
Transpositions.
In transpositions, absolutely all elements of the set are considered. As well as in permutations
the order of the elements is important.
Transposition without repetition.
In this case, we ask the question: how many ways can I place n different subjects on n different places?
In fact, a transposition without repetitions is the permutation of n elements in n places.
ABCD BACD CBAD DBCA
ABDC BADC CBDA DBAC
ADCB BDCA CDAB DACB
ADBC BDAC CDBA DABC
ACBD BCAD CABD DCBA
ACDB BCDA CADB DCAB
Transposition with repetition.
If there are identical elements among the n elements to be sorted, then we can ask:
How many ways can I rearrange n items that are sold in n different places, if there are among them
k of different types (k < n), that is, of the same types?
How many different letters can be made from the letters of the word "mississippi"?
Here 1 letter "m", 4 letters "i", 4 letters "s" and 2 letters "p", only 11 letters.
Hence the number of permutations with repetitions is
Below is a diagram of the algorithm for choosing the appropriate way of working with a given set of elements.
Here 1 letter "m", 4 letters "i", 4 letters "s" and 2 letters "p", only 11 letters.
Hence the number of permutations with repetitions is
