Notes on Permutations (Section 3.2)

Permutations

Definition of Permutation

The word "permute" means to arrange.
A permutation is a way to arrange a specific number of objects from a given group.

Permutation Notation

Notation: $P(n, k)$
- Read as "permutation n pick k" or "permutation n choose k".
- $n$ : The total number of objects available (the starting group).
- $k$ : The number of objects being selected and arranged.
Parameters for $k$ :
- $k ot< 0$ (cannot pick negative objects).
- $k ot> n$ (cannot pick more objects than available).
- Therefore, $0 ot ext{l}e k ot ext{l}e n$

Permutation Formula

The formula for calculating permutations is: $P(n, k) = \frac{n!}{(n-k)!}$
Explanation of the formula:
- The numerator, $n!$ , represents all possible ways of arranging the total $n$ objects.
- The denominator, $(n-k)!$ , divides out the arrangements of the objects that are not being picked. Since $k$ objects are picked, $(n-k)$ objects are not picked. We divide by $(n-k)!$ because we are not concerned with the order or arrangements of the un-picked objects.
Practical Application: While the formula exists, it is generally not necessary to memorize or use it for calculations.
- For large numbers, a calculator would still be required to simplify the factorials.

Using a Calculator for Permutations

Permutation calculations are pre-programmed into most scientific calculators.
Steps for TI-30XA calculator (common model):
1. Enter the first number (the $n$ value).
2. Press "2nd" (acting as a shift key).
3. Press the permutation key, which is often labeled "nPr" (behind the "9" button on TI-30XA).
4. Enter the second number (the $k$ value).
5. Press "=" (equals).
Example: For $P(11, 5)$
- Enter "11", then "2nd", then "nPr", then "5", then "=".
- Result: $55,440$ ways.

Permutations vs. Fundamental Counting Principle (FCP)

Connection to FCP (Section 3.1): Permutations are closely related to problems solved using the Fundamental Counting Principle.
Example 1: 10 people, 10 seats
- FCP Approach: 10 spots, options: $10 \times 9 \times 8 \times ext{…} \times 1 = 10!$
  - Using calculator: $10! = 3,628,800$
- Permutation Approach: We are arranging all 10 people from the group of 10. So, $P(10, 10)$ .
  - Using calculator: $10 \text{ nPr } 10 = 3,628,800$
- Conclusion: In this specific case, both methods yield the same result with similar effort.
Example 2: 14 students, 10 seats
- FCP Approach: 10 spots, options: $14 \times 13 \times 12 \times 11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5$
 - This is not a factorial because not all students are seated (4 are left out).
 - Calculating involves typing all 10 numbers and multiplications and is time-consuming.
- Permutation Approach: We are selecting and arranging 10 students from 14. So, $P(14, 10)$ .
 - Using calculator: $14 \text{ nPr } 10 = 3,632,428,800$
- Conclusion: In problems where $k < n$ , the permutation method is significantly quicker and easier than the FCP approach of multiplying many individual numbers.

Properties of Permutations

For an experiment to be solved using permutations, two properties must be satisfied:

Repetition is NOT allowed:
- Objects can be selected only once. Once an element is used, it cannot be used again in that experiment.
- Example: A person selected for the first seat cannot also be selected for the sixth seat.
- Implication: If repetition is allowed (stated directly or implied), then FCP or a tree diagram must be used, as permutations cannot handle repetition.
Order of selection matters (Objects are being arranged):
- The sequence in which objects are selected significantly changes the outcome.
- Example: If Sally is in the first seat and Jack in the second, this is a different arrangement than Jack in the first and Sally in the second.
- Metaphor: In a yearbook, if a teacher and student swap places, the caption identifying the person on the left as "teacher" would be incorrect, showing order matters.

Summary: If a problem meets both criteria (no repetition, order matters), it can be solved using the permutation technique.

Relationship between FCP and Permutations (Important Notes):

All permutation problems can also be solved using FCP. The choice depends on which method is quicker or more intuitive for the specific problem.
However, not all FCP problems can be solved using permutations, specifically those where repetition is allowed.

Permutation Examples (from Section 3.2)

Example 3: Electing committee roles
- Problem: How many ways can a committee of 20 people elect a president, secretary, and treasurer?
- Analysis:
  - Repetition? No, one person cannot hold multiple titles simultaneously. (Condition 1 satisfied)
  - Order? Yes, titles imply order (President A, Secretary B is different from President B, Secretary A). (Condition 2 satisfied)
- FCP Approach (from Section 3.1): 3 positions. Options: $20 \times 19 \times 18 = 6,840$
- Permutation Approach: $P(20, 3)$
  - Using calculator: $20 \text{ nPr } 3 = 6,840$
- Conclusion: Both methods yield the same result; the effort is comparable for this problem.
Example 19, Part A: Four-digit codes without repetition
- Problem: How many four-digit codes can be formed from the letters {A, B, C, D, E, F} if letters cannot be repeated?
- Analysis:
  - Total letters: 6. Code length: 4.
  - Repetition? No, explicitly stated "cannot be repeated". (Condition 1 satisfied)
  - Order? Yes, forming a "code" implies order matters (ABCD is different from ACBD). (Condition 2 satisfied)
- FCP Approach: 4 spots. Options: $6 \times 5 \times 4 \times 3 = 360$
- Permutation Approach: $P(6, 4)$
  - Using calculator: $6 \text{ nPr } 4 = 360$
Example 19, Part B: Eight-character code with mixed types and no repetition
- Problem: An 8-character code: first two spots (different letters), next three (different numbers from 1-9), final three (different symbols from {!, @, #, $, %, ^}). How many codes?
- Analysis: Each segment (letters, numbers, symbols) satisfies permutation properties (no repetition, order matters).
- FCP Approach: 8 spots split into 3 sections.
  - Letters: $26 \times 25$
  - Numbers (from 1-9): $9 \times 8 \times 7$
  - Symbols (1 of 6 available): $6 \times 5 \times 4$
  - Total: $(26 \times 25) \times (9 \times 8 \times 7) \times (6 \times 5 \times 4) = 39,312,000$
- Permutation Approach (Product of Permutations):
  - Letters: $P(26, 2)$
  - Numbers: $P(9, 3)$
  - Symbols: $P(6, 3)$
  - Total: $P(26, 2) \times P(9, 3) \times P(6, 3)$
    - Using calculator: $(26 \text{ nPr } 2) \times (9 \text{ nPr } 3) \times (6 \text{ nPr } 3) = 39,312,000$
- Conclusion: The permutation approach is more concise and quicker, especially with multiple segments.
Example: Casting for a play
- Problem: 14 actresses audition for 8 female roles. How many casting possibilities?
- Analysis:
  - Repetition? No, one actress plays one role. (Condition 1 satisfied)
  - Order? Yes, roles are different (leading actress, supporting, etc.), so assigning different actresses to different roles means order matters. (Condition 2 satisfied)
- FCP Approach: 8 spots. Options: $14 \times 13 \times 12 \times 11 \times 10 \times 9 \times 8 \times 7 = 121,080,960$
- Permutation Approach: $P(14, 8)$
  - Using calculator: $14 \text{ nPr } 8 = 121,080,960$
Example: Teacher and students in a line
- Problem: A teacher and 10 students (11 people total) stand in a line for a picture. If the teacher stands on either end of the line, how many different arrangements are possible?
- Analysis:
  - Repetition? No, each person occupies one spot. (Condition 1 satisfied)
  - Order? Yes, positions in a line matter, and the teacher's specific end position matters. (Condition 2 satisfied)
- Permutation Approach (Broken down):
  1. Teacher's placement: The teacher can be on the left end or the right end (2 options). This is $P(2, 1)$ .
  2. Students' placement: The remaining 10 students can be arranged in the remaining 10 spots. This is $P(10, 10)$ .
  - Total arrangements: $P(2, 1) \times P(10, 10)$
    - Using calculator: $(2 \text{ nPr } 1) \times (10 \text{ nPr } 10) = 2 \times 3,628,800 = 7,257,600$

Circular Permutations

Definition: A special type of permutation that deals with arranging objects in a circular pattern, rather than in a linear row.
Situations: Seating people at a round table, placing keys on a keyring, designing a circular spinner, etc.
Difference from Linear Permutations: In linear arrangements, rotating the entire arrangement (e.g., ABC, BCA, CAB) results in distinct outcomes. In circular arrangements, rotations are considered the same arrangement if the relative positions of objects remain unchanged.
Example: Seating 4 people (A, B, C, D) at a round table
- If person A always has B to their left and D to their right, and C across, any rotation of the table results in the same relative arrangement.
- A linear arrangement of 4 people would be $4! = 24$ ways. However, for a circular table, these 24 linear arrangements collapse into fewer distinguishable circular arrangements because rotations are indistinguishable.
- For 4 people, there are 4 rotations for each unique relative arrangement. So, $24 \div 4 = 6$ distinguishable circular arrangements.
Formula for Circular Permutations:
- Notation: $CP(n)$
- Formula: $CP(n) = (n-1)!$
- Applying to 4 people: $CP(4) = (4-1)! = 3! = 3 \times 2 \times 1 = 6$

Circular Permutation Examples

Example 10: Arthur and his 12 knights at a round table
- Problem: 13 people (Arthur + 12 knights) at a round table. How many seating arrangements?
- Analysis: Keyword "round table" indicates a circular permutation.
- Total people: $n=13$
- Calculation: $CP(13) = (13-1)! = 12!$
  - Using calculator: $12! = 479,001,600$
- Note: If they were sitting in a row, it would be $13!$ , which is even more.
Example 15: 8 keys on a keyring, considering direction
- Problem: How many ways can 8 keys be placed on a keyring? Each key can face two ways (jagged side up or down).
- Analysis: Keyring implies circular permutation. The added condition about direction introduces an additional factor.
- Step 1: Determine the number of circular arrangements for 8 unique keys.
  - $CP(8) = (8-1)! = 7! = 5,040$
- Step 2: Account for the direction of each key.
  - After the first key is placed (which sets the reference), each of the other $n-1$ keys can face two ways (up or down).
  - Number of ways for direction: $2^{n-1} = 2^{8-1} = 2^7 = 128$
- Step 3: Multiply the order arrangements by the direction arrangements.
  - Total ways: $7! \times 2^7 = 5,040 \times 128 = 645,120$
- Conclusion: This is a more complex circular permutation problem requiring consideration of an additional factor.

Distinguishable vs. Indistinguishable Objects (Permutations with Repetition)

Problem Type: Finding the number of unique arrangements when some of the objects are identical.
Example A: "isogram"
- Problem: How many distinguishable arrangements can be made from the letters in "isogram"?
- Analysis: All letters in "isogram" (I, S, O, G, R, A, M) are unique (distinguishable).
- Total letters: 7.
- Calculation: $7! = 5,040$
Example B: "statistics"
- Problem: How many distinguishable arrangements could be made from the letters in "statistics"?
- Analysis: The word "statistics" contains repeating letters (indistinguishable objects). Simply calculating $10!$ (for 10 letters) would produce too many outcomes, as swapping identical letters (e.g., the two 's's at the end) would be counted as a new arrangement, even though it looks the same.
- Method: Divide the total permutations by the factorial of the count of each repeating letter.
 - Total letters: $n=10$
 - Repeated letters counts:
 - S: 3 times ( $3!$ ways to arrange them)
 - T: 3 times ( $3!$ ways to arrange them)
 - A: 1 time ( $1!$ ways)
 - I: 2 times ( $2!$ ways to arrange them)
 - C: 1 time ( $1!$ ways)
 - (Check: $3+3+1+2+1=10$ )
- Formula: $\frac{n!}{n1! n2! \text{…} nk!}$ where $n$ is the total number of letters and $ni$ is the count of each repeated letter.
- Calculation for "statistics": $\frac{10!}{3! \times 3! \times 2! \times 1! \times 1!} = \frac{10!}{3! \times 3! \times 2!}$
 - Using calculator: Enter $10! \div (3! \times 3! \times 2!)$
 - Crucial: Use parentheses around the denominator: \text{10 SHIFT FACTORIAL \div (3 SHIFT FACTORIAL \times 3 SHIFT FACTORIAL \times 2 SHIFT FACTORIAL) = 50,400}
- Conclusion: There are $50,400$ distinguishable arrangements for the letters in "statistics". This is also called finding the number of distinguishable permutations.