1.1: Introduction

Last updated
Save as PDF

Page ID: 97321

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

There are three principal themes to our course:

Discrete Structures Graphs, digraphs, networks, designs, posets, strings, patterns, distributions, coverings, and partitions.

Enumeration Permutations, combinations, inclusion/exclusion, generating functions, recurrence relations, and Pólya counting.

Algorithms and Sorting, eulerian circuits, hamiltonian cycles, planarity testing, graph coloring, spanning trees, shortest paths, network flows,

Optimization bipartite matchings, and chain partitions.

To illustrate the accessible, concrete nature of combinatorics and to motivate topics that we will study, this preliminary chapter provides a first look at combinatorial problems, choosing examples from enumeration, graph theory, number theory, and optimization. The discussion is very informal—but this should serve to explain why we have to be more precise at later stages. We ask lots of questions, but at this stage, you'll only be able to answer a few. Later, you'll be able to answer many more … but as promised earlier, most likely you'll never be able to answer them all. And if we're wrong in making that statement, then you're certain to become very famous. Also, you'll get an A++ in the course and maybe even a Ph.D. too.