I was having a discussion with my friend Sayan Mukherjee about why we need to study combinatorics which admittedly, is not our favorite subject because we see very less motivation for it (I am not saying that there does not exist motivation for studying it, it's just that I have not found it).
Here are some of the "uses" of combinatorics that we could come up with:
-
Counting – the number of ways in which we can perform a finite sequence of operations and how objects can be arranged or selected. For example,the number of ways in which we can select $k$ odd and even elements from the set $S=\{1,2,\dots, 2n\}$ so that at most 3 odd elements consecutive elements could occur in the section.
-
Drawing bijections- The classic Stars and bars problem provides us key ideas to count the number of integral solutions to equations of the form $x_1+x_2+\dots x_n=k$.
-
The Seven Bridges of Königsberg which captivated me as a child.
I have refrained from mentioning recursions and generating functions as I see them more as tools.
But I am looking for more motivation; counting, as described in problems seems to be tip of the iceberg and I will appreciate more examples where combinatorics and graph theory can be powerful tools. Can we please have a list of uses of combinatorics? I am not looking for applications to industry, just pure math.
It is not essential that the answers be pitched at high-school level; additional info will certainly be fun to revisit!
Best Answer
As requested, here is a list of applications of combinatorics to other topics in pure mathematics.
Counting is used extensively in the original proof of Chebyshev's theorem, which you can find in Chapter 5 of (the free online version of) this book. Chebyshev's theorem is the first part of the prime number theorem, a deep result from analytic number theory.
In group theory, the pigeonhole principle is used to show that every element of a finite group has an order. One could argue that the proof that every finite integral domain is a field stems from similar logic.
A proof of Brouwer's fixed point theorem using the pigeonhole principle and Sperner's lemma is given here.
UPDATE: Graphs in Finite Group Theory. I know of several examples where graphs appear in finite group theory: prime graphs, character degree graphs, and commuting graphs. Prime graphs (about which I have written several MSE answers, e.g. $[1]$,$[2]$) concern the set of element orders in a finite group, character degree graphs have to do with the degrees of a group's irreducible characters, and commuting graphs illustrate which elements commute with which other elements. $$$$ Most of the time, the application of graph theory to finite group theory is linguistic - that is, these graphs arise naturally from group theoretic questions that are best formulated using graph theoretic language. In other words, one doesn't commonly see theorems from graph theory being used to solve problems in finite group theory, even when the aforementioned graphs are the subject of research. Sometimes, however, graph theory may also be applied more directly, as can be seen in this paper of mine, for example.