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\text{.}\)
When \(n\) is a positive integer, we define \(n!\) (read “\(n\) factorial”) by
By convention, we set \(0!=1\text{.}\) As an example, \(7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 \cdot
1=5040\text{.}\) Now for integers \(m,n\) with \(m\ge n\ge0\) define \(P(m,n)\) by
For example, \(P(9,3)=9\cdot
8\cdot 7=504\) and \(P(8,4)=8\cdot 7\cdot 6\cdot5 =1680\text{.}\) Also, a computer algebra system will quickly report that
If \(X\) is an \(m\)-element set and \(n\) is a positive integer with \(m\ge n\text{,}\) then the number of \(X\)-strings of length \(n\) that are permutations is \(P(m,n)\text{.}\)
Proof.
The proposition is true since when constructing a permutation \(s=x_1x_2,\dots x_n\) from an \(m\)-element set, we see that there are \(m\) choices for \(x_1\text{.}\) After fixing \(x_1\text{,}\) we have that for \(x_2\text{,}\) there are \(m-1\) choices, as we can use any element of \(X-\{x_1\}\text{.}\) For \(x_3\text{,}\) there are \(m-2\) choices, since we can use any element in \(X-\{x_1,x_2\}\text{.}\) For \(x_n\text{,}\) there are \(m-n+1\) choices, because we can use any element of \(X\) except \(x_1,x_2,\dots x_{n-1}\text{.}\) Noting that
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.
To count possible officer slates, work from a set \(X\) containing the names of the \(80\) interested students (yes, even poor Bob). A permutation of length four chosen from \(X\) is then a slate of officers by considering the first name in the permutation as the President, the second as the Vice President, the third as the Secretary, and the fourth as the Treasurer. Thus, the number of officer slates is \(P(80,4)=37957920\text{.}\)
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\text{.}\) 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.
Reading QuestionsReading Questions
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 two 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.
