8.1: What is Combinatorics?

Last updated
Save as PDF

Page ID: 8428

\( \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}}\)

Combinatorics studies the arrangements of objects according to some rules. The questions that can be asked include

Existence. Do the arrangements exist?
Classification. If the arrangements exist, how can we characterize and classify them?
Enumeration. How many arrangements are there?
Construction. Is there an algorithm for constructing all the arrangements?

Example \(\PageIndex{1}\label{eg:whatiscombo-01}\)

In how many ways can five people be seated at a round table? What if a certain pair of them refuses to sit next to one another? What if there are \(n\) people?

Example \(\PageIndex{1}\label{eg:whatiscombo-02}\)

Given integers \(n_1 \geq n_2 \geq \cdots \geq n_t \geq 1\), a Young tableau of the shape \((n_1,n_2,\dots,n_t)\) consists of \(t\) rows of left-justified cells, with \(n_i\) cells in the \(i\)th row (counting from the top row). These cells are occupied by the integers 1 through \(n\), where \(n=n_1+n_2+\cdots+n_t\), such that the entries are in descending order across each row from left to right, and down each column from top to bottom. For instance, the three Young tableaux of the shape \((3,1)\) are depicted in Figure \(\PageIndex{1}\).

Screen Shot 2020-01-15 at 12.53.20 PM.png — Figure \(\PageIndex{1}\): The three Young tableaux of the shape (3, 1).

It is known that there are 35 Young tableaux of the shape \((4,2,1)\). Can you list all of them? In general, one may ask, how many Young tableaux are there of shape \((n_1,n_2,\ldots,n_t)\), and how can we generate all of them?

Example \(\PageIndex{3}\label{eg:whatiscombo-03}\)

A binary string is a sequence of digits, each of which being 0 or 1. Let \(a_n\) be the number of binary strings of length \(n\) that do not contain consecutive 1s. It is easy to check that \(a_1=2\), \(a_2=3\), and \(a_3=5\). What is the general formula for \(a_n\)?

Example \(\PageIndex{4}\label{eg:whatiscombo-04}\)

The complexity of an algorithm tells us how many operations it requires. By comparing the complexity of several algorithms for solving the same problem, we can determine which one is most efficient. Let \(b_n\) be the number of operations required to solve a problem of size \(n\). If it is known that \[b_n = 2b_{n-1}+3b_{n-2}, \qquad n\geq3, \nonumber\] where \(b_1=1\) and \(b_2=3\), what is the general formula for \(b_n\)?