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.

Jetzt du Kein Rechner löst diese Frage, aber ihre Teile sind berechenbar. Probieren Sie unten eine aus oder geben Sie Ihre eigene ein.

⌨ Tippen ✎ Zeichnen

Dein Matheproblem

π Lösen

Übung (4)

Versuchen Sie zuerst jede auf Papier. Decken Sie die Antwort zur Kontrolle auf; überprüfte Aufgaben lassen sich im Löser Schritt für Schritt öffnen.

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.

   Schritt für Schritt durcharbeiten Tipp

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?

   ____

   Schritt für Schritt durcharbeiten Tipp

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.

   Schritt für Schritt durcharbeiten Tipp

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.

   Schritt für Schritt durcharbeiten Tipp

Behalten Sie Ihre eigenen Lösungswege

Ein kostenloses Konto fügt Notizen zu jeder Lektion, eine Aufzeichnung von dem, was Sie beendet haben, Ihre gelösten Probleme an einem Ort, und ein Tutor können Sie über diese Seite fragen. Die Mathematik selbst ist offen für alle, angemeldet oder nicht.

Registrieren Anmelden

Hier verwendete Symbole

Tippen Sie auf jedes Symbol für die vollständige Definition, ein Bild und was jeder Buchstabe darin bedeutet.

n!factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.P(A)probability, conditional probability
Chance of A; chance of A given that B happened.iimaginary unit
i² = −1.\leqless/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_ksummation
Add a_k for k = 1 up to n.\prod_{k=1}^{n} a_kproduct
Multiply a_k for k = 1 up to n.\emptysetempty set, cardinality
The set with no elements; the number of elements of A.

Fragen, die die Leute stellen

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.

Teile dieser Seite sind adaptiert aus Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Hier gekürzt und neu erklärt; Fehler gehen auf uns.

Mehr 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