= Algebraic combinatorics
Algebraic combinatorics studies discrete structures using tools such as <groups>, <rings>, <representations>, and <polynomials>, and in turn gives combinatorial interpretations of algebraic quantities. A <group action> can organize objects into <orbits>; a <generating function> can encode an entire sequence of counts.
For example, let $A$ be the <adjacency matrix> of a finite <graph>. The entry $(A^r)_{ij}$ counts length-$r$ <walks> from vertex $i$ to vertex $j$. The proof is induction: matrix multiplication sums over the penultimate vertex, appending one edge to each shorter <walk>. Thus powers of a <matrix>, and sometimes its <eigenvalues>, answer an enumeration problem. The matrix calculation also explains why revisiting vertices is allowed: it counts <walks>, rather than only <simple paths>.
Other central connections include <symmetric functions>, <Young tableaux>, and <representation theory of the symmetric group>. Their usefulness comes from translating a combinatorial question into an algebraic operation for which structure theorems are available.
Back to article page
