Permutations

Permutations

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.

Example

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 \(n!\) \(n\) factorial ) by \[\begin{aligned}\end{aligned}\] 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{aligned}\end{aligned}\] \(P(m,n)\) number of permutations 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{aligned}\end{aligned}\]

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

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Practice (4)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Suppose we are forming strings of length four. The first and second characters in the string will be distinct uppercase English letters. The third and fourth characters in the string will be distinct digits (i.e., chosen from \(0\)\(9\)). How many strings meet these criteria? Explain your reasoning, and it would be better if you expressed your answer as a product of numbers rather than giving only a final numerical answer.

2. Suppose that Alice, Carlos, Dave, Xing, and Yolanda are the five candidates to serve as chair, vice chair, and treasurer of a student organization. You should be able to answer this without listing all the outcomes. However, to set the stage for things yet to come, write out all the possible outcomes somewhere for your reference. (Don't submit them all here, however! You probably also want to just write A, C, D, X, and Y rather than using everyone's full name.) How many possible outcomes are there for filling the three positions?

   ____

3. Suppose we change the election and instead of having three distinct officers, the organization is to elect three co-chairs. Group the outcomes you listed in the previous part so that all election outcomes that would lead to the same co-chairs are grouped together. For instance, ADC and CDA would be grouped together, since what matters here is simply that Alice, Carlos, and Dave were elected and not whether Alice or Carlos was elected chair.

   Doing this forms ____ groups, and each group contains ____ outcomes.

4. Suppose we had \(80\) candidates and needed to elect five co-chairs. Listing out all the outcomes and grouping them would be rather challenging. Describe in a couple of sentences your thoughts on how you could generalize the ideas of the two previous tasks to get an answer to this question without writing out all the options. For this one, if you are able to come up with what the answer should be, express it either as a quotient of products or using the \(P(m,n)\) notation.

Symbols used here

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

P(A),\ P(A \mid B)

probability, conditional probability
Chance of A; chance of A given that B happened.

i

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Try your own

⌨ Type ✎ Draw

Your maths problem

Solve

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

More in Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs