Permutation and combination is the most basic concept of combinatorics. The so-called arrangement refers to taking out a specified number of elements from a given number of elements for sorting. Combination refers to taking out only a specified number of elements from a given number of elements, regardless of sorting.
The central problem of permutation and combination is to study the total number of possible situations in a given permutation and combination. Permutation and combination are closely related to classical probability theory.
Famous problems of permutation and combination:
(1) Calculate the number of methods for grouping certain items under specific conditions. These are about permutation, combination and integer division.
(2) Map coloring: Color the map of the world, with one color for each country. If neighboring countries are required to have different colors, do they always need only four colors? This is a problem of graph theory.
(3) The boatman crosses the river: The boatman wants to transport a wolf, a sheep and a cabbage across the river. As long as the boatman is away, the sheep will eat cabbage and the wolf will eat the sheep. The boatman's boat can only hold one thing at a time. How to transport everything across the river? This is a problem of linear programming.
(4) The postal route problem in China was put forward by Professor Guan Meigu, a combinatorial mathematician in China. The postman has to cross every road in the city at least once. How to take the shortest distance? This is not a NP-complete problem. There is an algorithm with polynomial complexity: first, find odd-numbered points, calculate the connection mode between these points with matching algorithm, and then solve it with Euler path algorithm. This is also a problem of graph theory.
(5) Task assignment (also called marriage problem): Some employees have to complete some tasks. It takes different time for each employee to complete different tasks. Each employee is assigned only one task. Each task is assigned to only one employee. How to allocate employees and tasks to minimize the time spent? This is a problem of linear programming.
Baidu encyclopedia-permutation and combination