Chapter 6.4: Permutations, Combinations, and Preliminary Probability Notes

Permutations

• A permutation of a set is an arrangement of its objects in a definite order.
• When ordering matters and objects are chosen without repetition, the number of permutations of n distinct elements taken r at a time is denoted by P(n, r).
• Key formula:
  • $P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}$
• Special case: when $r=n$, $P(n,n) = n!$
• When all n elements are used, the number of permutations is $n! = n\times (n-1) \times (n-2) \times \cdots \times 1$.
• Examples from the transcript:
  • On two elements {a, b}, the permutations are (a, b) and (b, a) → 2 = 2!
  • For three elements {a, b, c}, the number of permutations is $3! = 6$ (abc, acb, bac, bca, cab, cba).
  • For a 6-person lineup: the number of arrangements is $6! = 720$.
• P(n, r) vs n!:
  • P(n, r) reduces to n! when r = n.
  • In general, $P(n,r) = \frac{n!}{(n-r)!}$.
• Multiset permutations (identical items): if a set has n objects with n1 of type 1, n2 of type 2, …, nk of type k (with n1+n2+…+nk = n), the number of distinct permutations is
  • $\frac{n!}{n<em>1!\,n</em>2!\,\cdots\,n_k!}$
• Examples:
  • In a word where some letters repeat, e.g., WHITEWATER has repeated letters, the number of distinct permutations is $\frac{10!}{2!\,2!\,2!}$ since W, T, and E each appear twice.
  • ATLANTA has A appearing 3 times and T appearing 2 times; thus the count is $\frac{7!}{3!\,2!}$.

Combinations

• A combination is a subset where the order of selection does not matter.
• Number of ways to choose r objects from n distinct objects (without regard to order) is denoted by C(n, r) or \binom{n}{r}.
• Key formulas:
  • $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
  • Relationship to permutations: $P(n,r) = \binom{n}{r} \cdot r!$
• Example comparisons:
  • From 4 objects, number of 2-element permutations: $P(4,2) = 4\cdot 3 = 12$.
  • Number of 2-element combinations: $\binom{4}{2} = 6$.
• Large n examples:
  • $\binom{500}{3} = \frac{500\times 499\times 498}{3\times 2 \times 1}$ (written as successive product: $500\cdot 499\cdot 498/6$).
  • Generally, combinations can be used to count “groups” where order is irrelevant.

Worked examples and applications

• 6-person volleyball team image for a group photo:
  • Number of line arrangements: $6! = 720$.
• Baseball team of 9 people for a group photo:
  • Number of line arrangements: $9!$.
• Selecting officers from a committee of 8 members (4 distinct positions):
  • Number of ways: $P(8,4) = 8\times 7\times 6\times 5 = 1680$.
• Selecting president, vice-president, secretary from 10 members:
  • $P(10,3) = 10\times 9\times 8 = 720$.
• Executive roles from 100 members (CEO, vice-CEO, secretary, treasurer, etc.):
  • If 5 distinct offices: $P(100,5) = 100\times 99\times 98\times 97\times 96\,.$
• Multiset permutations with repeats (e.g., letters in a word):
  • For a word with counts n1, n2, …, nk of distinct letters: $\frac{n!}{n<em>1!\,n</em>2!\,\cdots\,n_k!}$.
• Examples:
  • WHITEWATER: counts W=2, T=2, E=2; others occur once; number of unique arrangements: $\frac{10!}{2!\,2!\,2!}$.
  • ATLANTA: A=3, T=2, L=1, N=1; number of unique arrangements: $\frac{7!}{3!\,2!}$.
• Subset selection (combinations):
  • Subcommittee of 4 from 10 members: $\binom{10}{4} = 210$.
  • University executive committee: 5 from 15: $\binom{15}{5} = 3003$.
• Card and dice problems (probability prelude):
  • 5-card poker hands from a standard 52-card deck: $\binom{52}{5} = 2{,}598{,}960$.
  • A string quartet from groups: example counting by combinations and then by permutations when order matters (e.g., selecting 2 violinists from 6, 1 violist from 3, 1 cellist from 2):
  • Ways: $\binom{6}{2} \cdot \binom{3}{1} \cdot \binom{2}{1} = 15 \cdot 3 \cdot 2 = 90$.
  • If order matters for the violinists (1st violinist, 2nd violinist), multiply by the internal arrangements: $P(6,2) = 6\cdot 5 = 30$, leading to further counts (e.g., total 180 in that variant).
• Composite selection with multiple categories (investor choosing companies):
  • Select 2 aerospace from 5, 2 energy from 3, 2 electronics from 4:
  • $\binom{5}{2} \cdot \binom{3}{2} \cdot \binom{4}{2} = 10 \cdot 3 \cdot 6 = 180$.
• Group itinerary problems (arranging performances in cities):
  • Without restrictions: number of orderings of 5 cities: $5! = 120$.
  • If California cities (3 cities) must be consecutive: treat them as a block plus the other 2 cities → 3 items to arrange: $3! = 6$ ways to arrange the blocks, and inside the California block, the CA cities can be arranged in $3! = 6$ ways. Total: $3! \times 3! = 36$.
  • If there are 6 cities with 3 in California and 3 outside, the count becomes: arrange 4 items (the 3-city block + 2 other cities + one more outside city) as appropriate; the transcript shows 36 for the California-consecutive case with a 5-city example, and 144 for a 6-city example where all three CA cities are consecutive in a larger lineup.
• Probability basics (sample spaces and equally likely outcomes):
  • An experiment yields a sample space S consisting of all possible outcomes. An event E is a subset of S.
  • Equally likely outcomes assumption: in many introductory problems, each outcome has the same probability a priori.
  • Probability of an event E: $P(E) = \frac{n(E)}{n(S)}$ where $n(E)$ is the number of outcomes in E and $n(S)$ is the number of outcomes in S.
• Dice and cards examples:
  • Rolling a single fair die: S = {1,2,3,4,5,6} with equally likely outcomes.
  • Probability of events on a die: e.g., even numbers: $E = {2,4,6},\; P(E) =\frac{3}{6}=\frac{1}{2}$; odd numbers: 1/2; numbers less than 5: 4/6 = 2/3; etc.
  • Deck of cards: from a standard 52-card deck, probabilities include:
  • P(Ace) = $\frac{4}{52} = \frac{1}{13}$,
  • P(Face) = $\frac{12}{52} = \frac{3}{13}$,
  • P(Spade) = $\frac{13}{52} = \frac{1}{4}$.
  • Two dice: sample space has 36 ordered outcomes (red die, blue die). Event E could be sum equals 9, which has 4 outcomes: $E = {(6,3), (5,4), (4,5), (3,6)}$ and $P(E) = \frac{4}{36} = \frac{1}{9}$.
• Some additional probability exercises:
  • For sums on two dice, compute probabilities for sum 7, sum < 6, and sum > 10 by counting favorable ordered pairs in the 36 equally likely outcomes.

Quick reference formulas

• Permutations (order matters, no repetition):
  • $P(n,r) = \frac{n!}{(n-r)!}$
  • When r = n: $P(n,n) = n!$
• Combinations (order does not matter):
  • $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
• Relationship between permutations and combinations:
  • $P(n,r) = \binom{n}{r} \cdot r!$
• Multiset permutations (repeated items):
  • If there are n1 of type 1, n2 of type 2, …, nk of type k, with n = n1+n2+…+nk, then
  • $\frac{n!}{n<em>1!\,n</em>2!\,\cdots\,n_k!}$
• Large-number combinations example:
  • $\binom{52}{5} = 2{,}598{,}960$
• Specific problem answers (from transcript):
  • 6 people in a line: $6! = 720$
  • 9 people in a line: $9!$
  • 8 people selecting 4 officers: $P(8,4) = 1680$
  • 10 members with 3 offices: $P(10,3) = 720$
  • 100 members with 5 executive offices: $P(100,5) = 100\cdot 99\cdot 98\cdot 97\cdot 96$
  • 10-letter word permutations with repeats: $\frac{10!}{2!\,2!\,2!}$ for WHITEWATER; $\frac{7!}{3!\,2!}$ for ATLANTA
  • Subcommittee: $\binom{10}{4} = 210$; University exec: $\binom{15}{5} = 3003$
  • Poker hands: $\binom{52}{5} = 2{,}598{,}960$
  • Strings (violinists/violists/cellist): combinations and permutations as shown (e.g., 2 violinists from 6, 1 violist from 3, 1 cellist from 2 → 90 ways; with ordering among violins, 180 ways)
  • Investor selection: $\binom{5}{2}\cdot\binom{3}{2}\cdot\binom{4}{2} = 180$
  • California-consecutive layout problem: for 3 CA cities among 5 total, consecutive arrangements give totals like 36 (for 3 CA consecutive with 2 others) and 144 in larger setups.

Probability: foundational concepts (recap)

• Experiment: any process with observable outcomes.
• Trial: a repetition of the experiment.
• Outcome: a possible result of a trial.
• Sample space S: the set of all possible outcomes of an experiment.
• Event E: a subset of the sample space S.
• Equally likely outcomes: often assumed in introductory problems; each outcome in S has the same probability.
• Probability of E: $P(E) = \frac{n(E)}{n(S)}$ where $n(E)$ is the number of outcomes in E and $n(S)$ is the total number of outcomes in S.
• Examples used in the notes include coin tosses, rolling dice, drawing cards, and selecting subsets from sets.

Notes on real-world relevance and interpretation

• Permutations and combinations underpin counting in scheduling, seating, and resource allocation problems where order matters (permutations) or does not matter (combinations).
• Probability theory connects counting to likelihoods, enabling assessment of events in games, statistics, and decision making.
• The distinction between ordered vs unordered selections helps avoid double counting or undercounting in practical problems (e.g., assigning distinct roles vs forming a team).
• Ethical/philosophical reflections: Probability and combinatorics are neutral tools; applications may involve fair allocation, risk assessment, and transparency in decision processes. The content here does not discuss ethics explicitly, but practitioners should consider fairness, bias, and transparency when modeling real-world scenarios.

Quick practice prompts (to test understanding)

• Compute P(n, r) for n = 7 and r = 3.
  • Answer: $P(7,3) = 7\times 6\times 5 = 210$
• Compute C(n, r) for n = 7 and r = 3.
  • Answer: $\binom{7}{3} = \frac{7!}{3!\,4!} = 35$
• If a word has letters with repeats, e.g., APPLE (A, P, P, L, E), how many distinct permutations are there?
  • Answer: $\frac{5!}{2!} = 60$ because P repeats twice.
• A deck of 52 cards: the probability of drawing an Ace in a single draw.
  • Answer: $\frac{4}{52} = \frac{1}{13}$
• Two dice sum to 9: list favorable ordered pairs and compute probability.
  • Answer: 4 favorable pairs, so probability $\frac{4}{36} = \frac{1}{9}$.

Notes:

• Throughout, bold emphasis was placed on the distinction between order-sensitive (permutations) and order-insensitive (combinations) counting.
• All formulas are presented in LaTeX-friendly syntax and are ready to render in a math-enabled document.
• If you want, I can convert this into a clean PDF-ready cheat sheet with sections reorganized by topic and include more worked exercises with step-by-step solutions.