Math 3134 Applied Combinatorics Comprehensive Practice Test 1 Notes

Evaluation Rules & Closed-Form Expressions

• Numerical answers on Applied Combinatorics assessments may be submitted in closed-form expression format unless explicitly stated otherwise.
• Examples of acceptable closed-form numerical expressions include:
  • Binomial coefficients such as $\binom{312}{55}$
  • Rational or transcendental constants such as $\frac{87}{e}$
• Evaluation of $\binom{6}{2}$:
  • Formula: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
  • Computation: $\binom{6}{2} = \frac{6 \times 5}{2 \times 1} = 15$

Basic Combinatorics & Selection Problems

• Problem configuration: A pizza parlor provides $8$ distinct pizza toppings. A customer orders a $3$-topping pizza.
• Case (a): All three toppings must be distinct (order does not matter).
  • Selection type: Unordered combination without replacement.
  • Calculation: $\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$
• Case (b): Repeating toppings is permitted.
  • Selection type: Unordered combination with replacement (Multiset / Stars and Bars).
  • Formula for choosing $k$ items from $n$ types with repetition: $\binom{n + k - 1}{k}$
  • Parameters: $n = 8$, $k = 3$
  • Calculation: $\binom{8 + 3 - 1}{3} = \binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Casting and Rule of Product Applications

• Production context: The play Huis Clos by Jean-Paul Sartre features a small cast of $3$ characters: Estelle, Inès, and Joseph.
• Audition outcomes:
  • $3$ auditioners are suitable for Estelle.
  • $4$ auditioners are suitable for Inès.
  • $3$ auditioners are suitable for Joseph.
• Assumption: All auditioners are distinct individuals; no auditioner is suitable for more than one role.
• Total casting combinations calculation:
  • By the Rule of Product (Fundamental Counting Principle), the total number of ways to cast the play is: $3 \times 4 \times 3 = 36$

Non-Negative Integer Solutions & Team Configurations

• Governing rules: Under International Football Association rules, a soccer team consists of $11$ players.
  • Exactly $1$ player is assigned as the goalkeeper.
  • The remaining $10$ outfield players consist of defenders, midfielders, and strikers.
  • There is no minimum or maximum restriction on any outfield position, provided the sum of outfield players equals $10$.
• Combinatorial model:
  • Equivalent to finding the number of non-negative integer solutions to: $x_1 + x_2 + x_3 = 10$
  • Here $x_1$ represents defenders, $x_2$ represents midfielders, and $x_3$ represents strikers.
  • Stars and Bars formula with $n = 3$ categories and $k = 10$ elements: $\binom{k + n - 1}{k} = \binom{10 + 3 - 1}{10} = \binom{12}{10}$
  • Simplified form: $\binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66$

Restricted Sequence Permutations & Alphabet Problems

• Alphabet specifications:
  • Total characters: $26$
  • Consonants: $21$ (with 'y' treated explicitly as a consonant)
  • Vowels: $5$
• Sequence specification: Count the number of $11$-letter sequences containing exactly $3$ vowels.
• Construction steps:
  1. Choose $3$ positions out of $11$ for the vowels: $\binom{11}{3}$
  2. Assign a vowel to each chosen position (with repetition allowed): $5^3$
  3. Assign a consonant to each of the remaining $8$ positions: $21^8$
• Total unique sequences: $\binom{11}{3} \times 5^3 \times 21^8$

Permutations of Multisets (Repeated Letters)

• Word analyzed: DEFENSIVENESS
• Letter frequencies:
  • D: $1$
  • E: $4$
  • F: $1$
  • I: $1$
  • N: $2$
  • S: $3$
  • V: $1$
  • Total length $n = 1 + 4 + 1 + 1 + 2 + 3 + 1 = 13$
• Multinomial coefficient formula for multiset permutations: $\frac{n!}{n_1! \, n_2! \, \dots \, n_k!}$
• Calculation: $\frac{13!}{1! \times 4! \times 1! \times 1! \times 2! \times 3! \times 1!} = \frac{13!}{4! \times 2! \times 3!} = 21,621,600$

Combinatorial Identity Proofs

• Identity 1: Prove $n^2 + 2\binom{n}{2} = \binom{2n}{2}$

  • Algebraic Proof:
  • Left-Hand Side (LHS):       $n^2 + 2\binom{n}{2} = n^2 + 2 \left(\frac{n(n-1)}{2}\right) = n^2 + n(n-1) = n^2 + n^2 - n = 2n^2 - n$
  • Right-Hand Side (RHS):       $\binom{2n}{2} = \frac{2n(2n-1)}{2} = n(2n-1) = 2n^2 - n$
  • Since LHS = RHS, the identity is proven.
  • Combinatorial Proof:
  • Consider choosing $2$ elements from a set of size $2n$, split into two disjoint sets $A$ and $B$, each of size $n$.
  • Total ways to pick $2$ elements: $\binom{2n}{2}$.
  • Alternative selection cases:
    • Pick $2$ elements from set $A$: $\binom{n}{2}$
    • Pick $2$ elements from set $B$: $\binom{n}{2}$
    • Pick $1$ element from $A$ and $1$ element from $B$: $n \times n = n^2$
  • Summing the cases gives: $\binom{n}{2} + \binom{n}{2} + n^2 = n^2 + 2\binom{n}{2}$.

• Identity 2: Prove $\binom{7}{2} = \binom{4}{2} + \binom{3}{2} + 12$

  • Algebraic Proof:
  • LHS: $\binom{7}{2} = \frac{7 \times 6}{2 \times 1} = 21$
  • RHS: $\binom{4}{2} + \binom{3}{2} + 12 = \frac{4 \times 3}{2} + \frac{3 \times 2}{2} + 12 = 6 + 3 + 12 = 21$
  • LHS = RHS = $21$
  • Combinatorial Interpretation:
  • Consider choosing $2$ elements from a set of $7$ items partitioned into a group of $4$ items and a group of $3$ items.
  • Selecting both from the group of $4$: $\binom{4}{2} = 6$
  • Selecting both from the group of $3$: $\binom{3}{2} = 3$
  • Selecting one from each group: $4 \times 3 = 12$
  • Total combinations: $6 + 3 + 12 = 21$

String Naming Constraints & Language Grammars

• Java legal variable name specifications:
  • First character allowed set: Uppercase letters ($26$), Lowercase letters ($26$), Dollar sign \ ($1$), Underscore $\_$ ($1$).
  • Total valid first characters: $26 + 26 + 1 + 1 = 54$
  • Subsequent character allowed set: All valid first characters plus numeric digits ($10$).
  • Total valid subsequent characters: $54 + 10 = 64$
  • Reserved three-character Java words: for, int, new, try ($4$ words).
• Calculation of legal 3-character variable names:
  • Unrestricted combinations: $54 \times 64 \times 64 = 54 \times 64^2 = 221,184$
  • Subtracting reserved words: $54 \times 64^2 - 4 = 221,184 - 4 = 221,180$

Election Combinatorics with District Constraints

• Unconstrained Election (Part a):
  • $7$ candidates running for $4$ identical seats on a town council.
  • Total valid selections: $\binom{7}{4} = \frac{7 \times 6 \times 5 \times 4}{4 \times 3 \times 2 \times 1} = 35$
• District-Constrained Election (Part b):
  • $7$ total candidates: $3$ from District 1, $4$ from District 2.
  • Goal: Fill $4$ seats with at least $1$ representative from each district.
  • Complementary Counting Approach:
  • Total unrestricted ways: $\binom{7}{4} = 35$
  • Invalid selections (0 candidates from District 1): $\binom{3}{0} \times \binom{4}{4} = 1$
  • Invalid selections (0 candidates from District 2): $\binom{3}{4} \times \binom{4}{0} = 0$ (impossible since only 3 are from District 1)
  • Valid choices: $35 - 1 = 34$
  • Direct Summation Approach:
  • $1$ from District 1, $3$ from District 2: $\binom{3}{1} \times \binom{4}{3} = 3 \times 4 = 12$
  • $2$ from District 1, $2$ from District 2: $\binom{3}{2} \times \binom{4}{2} = 3 \times 6 = 18$
  • $3$ from District 1, $1$ from District 2: $\binom{3}{3} \times \binom{4}{1} = 1 \times 4 = 4$
  • Total: $12 + 18 + 4 = 34$

Combinations with Repetition Applications

• Scenario: A florist supplies red, pink, and white roses. A customer orders a bouquet of a dozen ($12$) roses in any combination of those $3$ colors.
• Combinatorial Structure: Unordered selection with repetition (Stars and Bars).
• Parameters: $n = 3$ types, $k = 12$ selections.
• Expression: $\binom{3 + 12 - 1}{12} = \binom{14}{12} = \binom{14}{2}$

Card Combination Counting

• Deck structure: $52$ standard cards across $13$ ranks and $4$ suits.
• Full House Definition: $3$ cards of one rank and $2$ cards of a different rank.
• Step-by-Step Counting:
  1. Choose rank for the three-of-a-kind: $\binom{13}{1} = 13$
  2. Choose $3$ suits out of $4$ for that rank: $\binom{4}{3} = 4$
  3. Choose rank for the pair from remaining ranks: $\binom{12}{1} = 12$
  4. Choose $2$ suits out of $4$ for that rank: $\binom{4}{2} = 6$
• Total possible full houses: $\binom{13}{1} \times \binom{4}{3} \times \binom{12}{1} \times \binom{4}{2} = 13 \times 4 \times 12 \times 6 = 3,744$

Fixed-Point Free Permutations (Derangements) & Graph Structures

• Neighborhood emergency phone tree scenario with $20$ homes where no person calls themselves:
  • Standard Derangement Model ($D_{20}$):
  • A permutation with no fixed points.
  • Formula: $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$
  • Exact derangement expression for $20$ homes: $D_{20} = 20! \sum_{k=0}^{20} \frac{(-1)^k}{k!}$
  • Single Cycle / Directed Hamiltonian Cycle Model:
  • If the phone tree requires a single continuous loop containing all $20$ households:
  • Total cyclic permutations: $(20 - 1)! = 19!$

Circular Permutations & Adjacency Constraints

• Context: Seating the $6$ members of the band Maroon 5 at a symmetrical round table.
• Case (a): Unconstrained circular seating.
  • Formula for $n$ items in a circle: $(n - 1)!$
  • Computation: $(6 - 1)! = 5! = 120$
• Case (b): Adam Levine and James Valentine must NOT sit next to each other.
  • Complementary Counting Method:
  • Total circular seatings: $5! = 120$
  • Treat Adam Levine and James Valentine as a single block:
    • Internal arrangements of the block: $2! = 2$
    • Circular seating of $5$ effective units: $(5 - 1)! = 4! = 24$
    • Restricted seatings where they are adjacent: $2! \times 4! = 2 \times 24 = 48$
  • Valid seating arrangements: $120 - 48 = 72$

Principle of Inclusion-Exclusion (PIE)

• Survey Data ($100$ Computer Science majors total):
  • Java ($J$): $45$
  • C++ ($C$): $30$
  • Python ($P$): $20$
  • C++ and Java ($C \cap J$): $6$
  • Java and Python ($J \cap P$): $1$
  • C++ and Python ($C \cap P$): $5$
  • All three ($J \cap C \cap P$): $1$
• Union calculation using PIE:
  • $|J \cup C \cup P| = |J| + |C| + |P| - |J \cap C| - |J \cap P| - |C \cap P| + |J \cap C \cap P|$
  • $|J \cup C \cup P| = 45 + 30 + 20 - 6 - 1 - 5 + 1 = 84$
• Students not proficient in any of the three languages:
  • Total students minus proficient students: $100 - 84 = 16$

Binomial Theorem & Power Series Expansions

• Expansion 1: Coefficient of $x^4 y^6$ in $(x + y)^{10}$

  • Binomial Theorem general term: $\binom{10}{k} x^{10-k} y^k$
  • For $x^4 y^6$, setting $k = 6$:
  • Coefficient: $\binom{10}{6} = \binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210$

• Expansion 2: Coefficient of $x^{11}$ in $(2x + 3)^{25}$

  • Binomial Theorem general term: $\binom{25}{k} (2x)^k (3)^{25-k} = \binom{25}{k} 2^k 3^{25-k} x^k$
  • Setting $k = 11$:
  • Coefficient: $\binom{25}{11} 2^{11} 3^{14}$

• Expansion 3: Generalized Binomial Theorem for $(1 - 2x)^{-3}$

  • Formula: $(1 + z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k$
  • Generalized coefficient: $\binom{-n}{k} = (-1)^k \binom{n + k - 1}{k}$
  • For $(1 - 2x)^{-3}$, set $z = -2x$ and $r = -3$:
  • Term $k$: $\binom{-3}{k} (-2x)^k = (-1)^k \binom{k + 2}{k} (-1)^k 2^k x^k = \binom{k + 2}{k} 2^k x^k$
  • For $x^4$, set $k = 4$:
  • Coefficient: $\binom{4 + 2}{4} 2^4 = \binom{6}{4} \times 16 = 15 \times 16 = 240$

• Expansion 4: Coefficient of $x^5$ in $y = \frac{1}{(1 + x)^2} = (1 + x)^{-2}$

  • Term $k$: $\binom{-2}{k} x^k = (-1)^k \binom{k + 1}{k} x^k = (-1)^k (k + 1) x^k$
  • For $x^5$, set $k = 5$:
  • Coefficient: $(-1)^5 (5 + 1) = -6$

• Expansion 5: Coefficient of $x^4$ in $y = \frac{1}{(1 - 2x)^5} = (1 - 2x)^{-5}$

  • Term $k$: $\binom{-5}{k} (-2x)^k = (-1)^k \binom{k + 4}{k} (-1)^k 2^k x^k = \binom{k + 4}{k} 2^k x^k$
  • For $x^4$, set $k = 4$:
  • Coefficient: $\binom{4 + 4}{4} 2^4 = \binom{8}{4} \times 16 = 70 \times 16 = 1120$

Ordinary Generating Functions in Discrete Problems

• American Football Scoring Play Values:
  • Safety: $2$ points
  • Field goal: $3$ points
  • Touchdown: $6$ points
  • Touchdown plus extra point: $7$ points
  • Touchdown plus two-point conversion: $8$ points
  • Conversion safety: $1$ point (Historical note: achieved in the NFL in 1940)
• Generating Function Construction:
  • Assuming unrestricted repetition of scoring plays where order of scoring does not matter, each scoring play value $v$ contributes a factor of $\frac{1}{1 - x^v} = 1 + x^v + x^{2v} + x^{3v} + \dots$
  • Primary generating function (excluding conversion safety):     $f(x) = \frac{1}{(1 - x^2)(1 - x^3)(1 - x^6)(1 - x^7)(1 - x^8)}$
  • Generating function including conversion safety (1 point play):     $f(x) = \frac{1}{(1 - x)(1 - x^2)(1 - x^3)(1 - x^6)(1 - x^7)(1 - x^8)}$
  • The number of ways to score exactly $16$ points corresponds to the coefficient of $x^{16}$ in $\left[x^{16}\right] f(x)$.

Recurrence Relations Formulation & Solution

• Recurrence Construction for Substring Avoidance:

  • Goal: Construct a recurrence relation for $a_n$, the number of ternary strings (using digits $0$, $1$, and $2$) of length $n$ that do NOT contain the exact substring "12".
  • Analysis by starting character:
  • If string starts with $0$: Remaining $n-1$ characters form a valid string ($a_{n-1}$ ways).
  • If string starts with $2$: Remaining $n-1$ characters form a valid string ($a_{n-1}$ ways).
  • If string starts with $1$:
    • Second digit cannot be $2$
    • If second digit is $0$: Remaining $n-2$ characters form a valid string ($a_{n-2}$ ways).
    • If second digit is $1$: String starts with "11", remaining $n-2$ characters start with $1$ ($a_{n-1} - a_{n-2}$ effectively when solved via system).
  • System Derivation:
  • Let $a_n$ be valid strings of length $n$.
  • A valid string ending in $0$ or $1$ can be formed by appending $0$ or $1$ to any valid string of length $n-1$ ($2a_{n-1}$ ways).
  • A valid string ending in $2$ can only be formed by appending $2$ to a valid string of length $n-1$ that does NOT end in $1$.
  • Since valid strings of length $n-1$ ending in $1$ are formed by appending $1$ to any valid string of length $n-2$ ($a_{n-2}$ ways), the number of length $n-1$ valid strings not ending in $1$ is $a_{n-1} - a_{n-2}$.
  • Therefore: $a_n = 2a_{n-1} + (a_{n-1} - a_{n-2}) = 3a_{n-1} - a_{n-2}$
  • Final Recurrence Relation: $a_n = 3a_{n-1} - a_{n-2}$ for $n \ge 2$
  • Initial Conditions: $a_0 = 1$, $a_1 = 3$ (and $a_2 = 8$)

• Linear Recurrence Solution 1:

  • System: $a_n = -3a_{n-1} + 10a_{n-2}$, with $a_0 = 1, a_1 = 9$
  • Characteristic equation: $r^2 + 3r - 10 = 0 \implies (r + 5)(r - 2) = 0$
  • Roots: $r_1 = 2, r_2 = -5$
  • General solution: $a_n = C_1 (2)^n + C_2 (-5)^n$
  • Apply initial conditions:
  • $a_0 = C_1 + C_2 = 1$
  • $a_1 = 2C_1 - 5C_2 = 9$
  • Solve linear system:
  • $C_2 = 1 - C_1$
  • $2C_1 - 5(1 - C_1) = 9 \implies 7C_1 - 5 = 9 \implies 7C_1 = 14 \implies C_1 = 2$
  • $C_2 = -1$
  • Closed-form solution: $a_n = 2(2)^n - (-5)^n = 2^{n+1} - (-5)^n$

• Linear Recurrence Solution 2 (Repeated Root):

  • System: $a_n = 10a_{n-1} - 25a_{n-2}$, with $a_0 = 1, a_1 = 15$
  • Characteristic equation: $r^2 - 10r + 25 = 0 \implies (r - 5)^2 = 0$
  • Repeated root: $r = 5$ (multiplicity 2)
  • General solution: $a_n = (C_1 + C_2 n) 5^n$
  • Apply initial conditions:
  • $a_0 = C_1 = 1$
  • $a_1 = (C_1 + C_2) 5 = 15 \implies 1 + C_2 = 3 \implies C_2 = 2$
  • Closed-form solution: $a_n = (1 + 2n) 5^n$

• Linear Recurrence Solution 3 (Complex Roots):

  • System: $a_n + a_{n-2} = 0 \implies a_n = -a_{n-2}$, with $a_0 = 2, a_1 = 3$
  • Characteristic equation: $r^2 + 1 = 0 \implies r = \pm i$
  • Polar representation: $i = e^{i \pi / 2}$
  • General solution form: $a_n = C_1 \cos\left(\frac{n\pi}{2}\right) + C_2 \sin\left(\frac{n\pi}{2}\right)$
  • Apply initial conditions:
  • $a_0 = C_1 \cos(0) + C_2 \sin(0) = C_1 = 2$
  • $a_1 = C_1 \cos\left(\frac{\pi}{2}\right) + C_2 \sin\left(\frac{\pi}{2}\right) = C_2 = 3$
  • Closed-form solution: $a_n = 2\cos\left(\frac{n\pi}{2}\right) + 3\sin\left(\frac{n\pi}{2}\right)$