Where is combinatorics used in computer science?

Question

Programming

I'm just starting to learn combinatorics. What is the use of combinatorics in computer science

Answer 1

Actually quite a lot. For example, combinatorics, in fact, first mentioned by Leibniz, went into the so-called seven bridge problem, which gave rise to graph theory, and already on the basis of which, for example, dynamic routing network protocols have been developed. From the same opera - the solution of the problem of the shortest path in a graph, which now seems to be solved by complete or partial enumeration, which is also combinatorics, and the very solution of such a problem forms the basis of routing in networks. It is also an integral part of the creation of artificial neural networks, which is part of the development of the artificial intelligence industry. The same applies to cryptography.

Answer 2

Little applied. In computer science, it is most likely to be needed in the analysis of the complexity of various algorithms, the choice of the optimal enumeration strategy. It occurs all the time in Olympiad programming. In real life - mainly when combinatorial formulas are required for calculating probabilities, and those, in turn, for testing statistical hypotheses.
Combinatorics can also be useful in problems related to statistical physics, when the entropy of the system is estimated through the number of states, and through it - further behavior or stability. Perhaps it is needed for algorithms like ultra-fast multiplication of numbers. But all this is a very distant level, when viewed from which elementary combinatorics is already indistinguishable from the multiplication table.
UPD. We can recall one place where combinatorics is required in ordinary problems. This is when we have a set of some subsets, permutations, words over the alphabet, or anything else that combinatorics usually considers. And we want to find its index by an element of this set. And vice versa.
The task does not arise often, but if it does, then one cannot do without combinatorial formulas.