Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section2.2Permutations

In the previous section, we considered strings in which repetition of symbols is allowed. For instance, “\(01110000\)” is a perfectly good bit string of length eight. However, in many applied settings where a string is an appropriate model, a symbol may be used in at most one position.

Example2.5

Imagine placing the \(26\) letters of the English alphabet in a bag and drawing them out one at a time (without returning a letter once it's been drawn) to form a six-character string. We know there are \(26^6\) strings of length six that can be formed from the English alphabet. However, if we restrict the manner of string formation, not all strings are possible. The string “yellow” has six characters, but it uses the letter “l” twice and thus cannot be formed by drawing letters from a bag. However, “jacket” can be formed in this manner. Starting from a full bag, we note there are \(26\) choices for the first letter. Once it has been removed, there are \(25\) letters remaining in the bag. After drawing the second letter, there are \(24\) letters remaining. Continuing, we note that immediately before the sixth letter is drawn from the bag, there are \(21\) letters in the bag. Thus, we can form \(26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21\) six-character strings of English letters by drawing letters from a bag, a little more than half the total number of six-character strings on this alphabet.

To generalize the preceding example, we now introduce permutations. To do so, let \(X\) be a finite set and let \(n\) be a positive integer. An \(X\)-string \(s=x_1x_2\dots x_n\) is called a permutation if all \(n\) characters used in \(s\) are distinct. Clearly, the existence of an \(X\)-permutation of length \(n\) requires that \(|X|\ge n\).

When \(n\) is a positive integer, we define \(n!\) (read “\(n\) factorial”) by \begin{equation*} n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots\cdot 3\cdot 2\cdot 1. \end{equation*} By convention, we set \(0!=1\). As an example, \(7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 \cdot 1=5040\). Now for integers \(m,n\) with \(m\ge n\ge0\) define \(P(m,n)\) by \begin{equation*} P(m,n) = \frac{m!}{(m-n)!} = m(m-1)\cdots(m-n+1). \end{equation*} For example, \(P(9,3)=9\cdot 8\cdot 7=504\) and \(P(8,4)=8\cdot 7\cdot 6\cdot5 =1680\). Also, a computer algebra system will quickly report that \begin{equation*} P(68,23) = 20732231223375515741894286164203929600000. \end{equation*}

Note that the answer we arrived at in Example 2.5 is simply \(P(26,6)\) as we would expect in light of Proposition 2.6.

Example2.7

It's time to elect a slate of four class officers (President, Vice President, Secretary and Treasurer) from the pool of \(80\) students enrolled in Applied Combinatorics. If any interested student could be elected to any position (Alice contends this is a big “if” since Bob is running), how many different slates of officers can be elected?

Solution
Example2.8

Let's return to the license plate question of Example 2.1. Suppose that Georgia required that the three letters be distinct from each other. Then, instead of having \(26^3=17\,576\) ways to fill the last three positions on the license plate, we'd have \(P(26,3) = 26\times 25\times 24 = 15\,600\) options, giving a total of \(140\,400\,000\) license plates.

As another example, suppose that repetition of letters were allowed but the three digits in positions two through four must all be distinct from each other (but could repeat the first digit, which must still be nonzero). Then there are still \(9\) options for the first position and \(26^3\) options for the letters, but the three remaining digits can be completed in \(P(10,3)\) ways. The total number of license plates would then be \(9\times P(10,3)\times 26^3\). If we want to prohibit repetition of the digit in the first position as well, we need a bit more thought. We first have \(9\) choices for that initial digit. Then, when filling in the next three positions with digits, we need a permutation of length \(3\) chosen from the remaining \(9\) digits. Thus, there are \(9\times P(9,3)\) ways to complete the digits portion, giving a total of \(9\times P(9,3)\times 26^3\) license plates.