8.1: What is Combinatorics?

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

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\)?