Counting Principles in Combinatorics

Counting is a fundamental aspect of combinatorics and discrete mathematics. It involves determining the number of ways certain events can occur, which is essential in fields like probability, statistics, computer science, and more. This comprehensive lecture will cover the foundational counting principles, progressing from basic to advanced topics:

1. Sum Rule
2. Product Rule
3. Permutations
4. Combinations
5. Arrangements with Non-Distinct Objects
6. Counting Integer Solutions (Stars and Bars Method)
7. Bijection Principle
8. $k$-to-1 Rule

The Sum Rule states:

• If there are two tasks, and the first task can be completed in $n$ ways and the second task can be completed in $m$ ways, and these tasks cannot both occur at the same time (they are mutually exclusive), then there are $n + m$ ways to choose one of these tasks to perform.

Key Point: Mutual exclusivity is crucial; the tasks do not overlap.

• Problem: A vending machine offers 5 types of chips and 3 types of chocolate bars. If you can choose either a bag of chips or a chocolate bar, how many snack options do you have?

• Solution:

  • Chips: 5 options
  • Chocolate bars: 3 options
  • Total options: $5 + 3 = 8$

• Problem: A dealership has 10 sedans and 7 SUVs available. If a customer wants to buy either a sedan or an SUV, how many choices does the customer have?

• Solution:

  • Sedans: 10 options
  • SUVs: 7 options
  • Total options: $10 + 7 = 17$

The Product Rule states:

• If a process involves making a sequence of choices, where the first choice can be made in $n$ ways, the second choice can be made in $m$ ways (after the first choice has been made), and these choices are independent (the number of ways to make one choice doesn’t affect the number of ways to make another), then the total number of ways to make the sequence of choices is $n \times m$.

Key Point: Independence is important; the choices do not interfere with each other.

• Problem: You are making a sandwich. You have 3 types of bread (white, wheat, rye) and 4 types of fillings (turkey, ham, chicken, veggie). How many different sandwiches can you make if you choose one bread and one filling?

• Solution:

  • Bread options: 3
  • Filling options: 4
  • Total sandwiches: $3 \times 4 = 12$

• Problem: You roll a standard 6-sided die twice. How many different outcomes are possible?

• Solution:

  • First roll options: 6
  • Second roll options: 6
  • Total outcomes: $6 \times 6 = 36$

A permutation refers to the number of ways to arrange a set of objects in a specific order, where all objects are distinct and order matters.

• Total permutations of $n$ distinct objects: The number of ways to arrange $n$ distinct objects in sequence is $n!$ (pronounced “n factorial”), where:

  \[ n! = n \times (n - 1) \times (n - 2) \times \dotsm \times 1 \]

• Permutations of $r$ objects chosen from $n$ distinct objects: The number of ways to arrange $r$ objects out of $n$ distinct objects is:

  \[ P(n, r) = n \times (n - 1) \times (n - 2) \times \dotsm \times (n - r + 1) = \frac{n!}{(n - r)!} \]

Key Points:

• Order Matters: Changing the order of objects creates a different permutation.
• Distinct Objects: All objects are different from each other.

• Problem: How many ways can you arrange 4 different books on a shelf?

• Solution:

  • Total permutations: $4! = 4 \times 3 \times 2 \times 1 = 24$

• Problem: In a competition with 5 athletes, how many ways can gold, silver, and bronze medals be awarded?

• Solution:

  • We need to choose and order 3 medalists out of 5 athletes.
  • Total permutations: $P(5, 3) = 5 \times 4 \times 3 = 60$

• Problem: How many 3-digit PIN codes can be created using the digits 0-9 if no digit is repeated and the first digit cannot be zero?

• Solution:

  • First digit options: 9 options (digits 1-9)
  • Second digit options: 9 options (digits 0-9 excluding the first digit)
  • Third digit options: 8 options (digits 0-9 excluding the first two digits)
  • Total permutations: $9 \times 9 \times 8 = 648$

A combination refers to the number of ways to select a subset of objects from a larger set where order does not matter, and all objects are distinct.

• Combinations of $r$ objects chosen from $n$ distinct objects:

  \[ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!} \]

Key Points:

• Order Does Not Matter: Changing the order of the selected objects does not create a new combination.
• Distinct Objects: All objects are different from each other.

• Problem: From a group of 7 students, how many ways can you choose a committee of 3 students?

• Solution:

  • Total combinations: $C(7, 3) = \frac{7!}{3!(7 - 3)!} = 35$

• Problem: In a lottery game, you must choose 6 numbers out of 49. How many different sets of numbers can you choose?

• Solution:

  • Total combinations: $C(49, 6) = \frac{49!}{6!(49 - 6)!} = 13,983,816$

• Problem: An ice cream shop offers 10 flavors. How many ways can you choose 2 flavors for a double-scoop cone if the order of scoops doesn’t matter?

• Solution:

  • Total combinations: $C(10, 2) = \frac{10!}{2!(10 - 2)!} = 45$

When arranging objects where some are identical, the standard permutation formula $n!$ (which counts arrangements of $n$ distinct objects) overcounts the number of unique arrangements. We need to adjust for the indistinguishable objects.

Formula for Permutations with Repetition:

If there are $n$ total objects, where:

• $k_1$ objects are of type 1,
• $k_2$ objects are of type 2,
• $\dots$,
• $k_m$ objects are of type $m$,

and $k_1 + k_2 + \dots + k_m = n$, then the number of distinct arrangements is:

\[ \text{Number of arrangements} = \frac{n!}{k_1! \times k_2! \times \dotsm \times k_m!} \]

Key Points:

• Identical Objects: Objects of the same type are indistinct and swapping them does not create a new arrangement.
• Adjustment: We divide by the factorial of the counts of each type to correct for overcounting.

Problem: How many unique ways can you arrange the letters in the word “BALLOON”?

Solution:

• Letters and Counts:
  • B: 1
  • A: 1
  • L: 2
  • O: 2
  • N: 1
• Total Letters: $n = 7$
• Repeating Letters:
  • L occurs $k_1 = 2$ times
  • O occurs $k_2 = 2$ times

Calculation:

\[ \text{Number of arrangements} = \frac{7!}{2! \times 2!} = \frac{5040}{4} = 1260 \]

Explanation:

• Overcounting: If we treated all letters as distinct, we would have $7! = 5040$ arrangements.
• Adjusting for Identical Letters: Dividing by $2!$ for each set of identical letters corrects the count.

Problem: You have 10 beads: 4 red, 3 blue, and 3 green. How many unique necklaces can you make by stringing all the beads in a line?

Solution:

• Total Beads: $n = 10$
• Repeating Beads:
  • Red beads: $$k_1 = 4$$
  • Blue beads: $k_2 = 3$
  • Green beads: $k_3 = 3$

Calculation:

\[ \text{Number of arrangements} = \frac{10!}{4! \times 3! \times 3!} = \frac{3628800}{288 \times 6} = 2100 \]

Explanation:

• Each set of identical beads is indistinct, so swapping them doesn’t create new arrangements.
• Dividing by the factorial of each bead count corrects for overcounting.

Problem: How many unique ways can you arrange the letters in the word “MISSISSIPPI”?

Solution:

• Letters and Counts:
  • M: 1
  • I: 4
  • S: 4
  • P: 2
• Total Letters: $n = 11$
• Repeating Letters:
  • I occurs $k_1 = 4$ times
  • S occurs $k_2 = 4$ times
  • P occurs $k_3 = 2$ times

Calculation:

\[ \text{Number of arrangements} = \frac{11!}{4! \times 4! \times 2!} = \frac{39916800}{1152} = 34650 \]

Explanation:

• Adjusting for the repeated letters corrects the overcounting.

Counting the number of non-negative integer solutions to equations of the form:

\[ x_1 + x_2 + \dotsm + x_n = k \]

is a common problem in combinatorics. This type of problem can be solved using the Stars and Bars method, which relates to combinations with repetition.

Key Concepts:

• Non-Negative Integers: Values $x_i \geq 0$.
• Stars and Bars: A visual method to represent the distribution of identical items into distinct categories.

• Stars ($*$): Represent the units to be distributed (e.g., identical balls).
• Bars ($|$): Represent dividers between categories (variables $x_i$).

Total Symbols:

• Number of stars: $k$ (the total units to distribute).
• Number of bars: $n - 1$ (dividing the units among $n$ variables).

The number of non-negative integer solutions is:

\[ \text{Number of solutions} = \binom{k + n - 1}{n - 1} \]

Problem: How many ways can you distribute 10 identical candies to 4 children so that each child can receive any number of candies (including zero)?

Solution:

• Variables: $x_1, x_2, x_3, x_4$ represent candies received by each child.
• Equation: $x_1 + x_2 + x_3 + x_4 = 10$
• Applying Stars and Bars:
  • Stars: 10 candies ($k = 10$)
  • Bars: $4 - 1 = 3$ dividers
• Total Symbols: $10 + 3 = 13$

Calculation:

\[ \text{Number of solutions} = \binom{10 + 4 - 1}{4 - 1} = \binom{13}{3} = 286 \]

Explanation:

• Each arrangement of stars and bars corresponds to a unique distribution.
• The positions of the bars determine how many candies each child receives.

Problem: Find the number of non-negative integer solutions to $x + y + z = 7$.

Solution:

• Variables: $x, y, z$
• Stars and Bars:
  • Stars: $k = 7$
  • Bars: $3 - 1 = 2$
• Total Symbols: $7 + 2 = 9$

Calculation:

\[ \text{Number of solutions} = \binom{7 + 3 - 1}{3 - 1} = \binom{9}{2} = 36 \]

Problem: How many non-negative integer solutions are there to $a + b + c + d = 5$, where $a \geq 1$ and $b \geq 2$?

Solution:

• Adjust for Constraints:
  • Since $a \geq 1$, let $a’ = a - 1$ ($a’ \geq 0$)
  • Since $b \geq 2$, let $b’ = b - 2$ ($b’ \geq 0$)
• Adjusted Equation: \[ (a’ + 1) + (b’ + 2) + c + d = 5 \implies a’ + b’ + c + d = 2 \]
• Variables: 4 variables, all $\geq 0$
• Stars and Bars:
  • Stars: $k = 2$
  • Bars: $4 - 1 = 3$
• Total Symbols: $2 + 3 = 5$

Calculation:

\[ \text{Number of solutions} = \binom{2 + 4 - 1}{4 - 1} = \binom{5}{3} = 10 \]

Explanation:

• Adjusting for the minimum values ensures all variables are non-negative.
• We then apply the Stars and Bars method to the adjusted equation.

The problem of counting non-negative integer solutions is equivalent to finding the number of combinations with repetition.

• Formula:

  \[ C(n + r - 1, r) = \binom{n + r - 1}{r} \]

  where:

  • $n$ is the number of types of items (categories).
  • $r$ is the number of items to choose (stars).

The Bijection Principle states:

• If there is a one-to-one and onto mapping (a bijection) between two finite sets $A$ and $B$, then the number of elements in $A$ is equal to the number of elements in $B$:

  \[ |A| = |B| \]

Key Points:

• A bijection is a function where every element of set $A$ maps to a unique element in set $B$, and every element of $B$ is mapped from an element in $A$.
• This principle allows us to count the elements of a complex set by establishing a bijection with a set whose size is known or easier to compute.

Problem: How many subsets does a set with $n$ elements have?

Solution:

• Set $A$: All subsets of the $n$-element set.
• Set $B$: All binary strings of length $n$.
• Bijection: Each subset corresponds to a binary string where each bit represents whether an element is included (1) or not included (0) in the subset.
• Conclusion: Since there are $2^n$ binary strings of length $n$, the set has $2^n$ subsets.

Problem: If each person in a room shakes hands with every other person exactly once, how many handshakes occur among $n$ people?

Solution:

• Set $A$: Pairs of people shaking hands.

• Set $B$: Combinations of 2 people from $n$ people.

• Bijection: Each handshake corresponds to a unique pair.

• Total handshakes:

  \[ C(n, 2) = \frac{n(n - 1)}{2} \]

The $k$-to-1 Rule states:

• If there is a function $f: A \rightarrow B$ such that every element in $B$ is the image of exactly $k$ distinct elements in $A$ (i.e., the function is $k$-to-1), then:

  \[ |B| = \frac{|A|}{k} \]

Key Points:

• This rule is useful when counting the number of distinct outcomes by accounting for multiple configurations in $A$ that map to a single outcome in $B$.
• It is essential when some arrangements or configurations are considered equivalent.

Problem: How many distinct ways can you arrange the letters in the word “LEVEL”?

Solution:

• Letters: L, E, V, E, L

• Total letters: 5

• Repeated letters:

  • L occurs 2 times
  • E occurs 2 times

• Total permutations without considering repeats: $5! = 120$

• Adjust for repeats:

  • Divide by the factorial of the counts of repeated letters.

  • Total distinct arrangements:

    \[ \frac{5!}{2! \times 2!} = \frac{120}{4} = 30 \]

• $k$-to-1 mapping:

  • $k = 2! \times 2!$ because each unique arrangement corresponds to $4$ permutations that are indistinct due to repeated letters.

Problem: In a row of 6 seats, there are 3 pairs of identical twins. How many unique seating arrangements are possible?

Solution:

• Total permutations if twins were distinguishable: $6! = 720$

• Since twins are indistinguishable within pairs, we need to adjust:

  • Divide by $(2!)^3$ (since there are 3 pairs and within each pair, the twins are indistinct).

• Total distinct arrangements:

  \[ \frac{6!}{(2!)^3} = \frac{720}{8} = 90 \]

Explanation:

• The $k$-to-1 rule accounts for the indistinguishable twin pairs.

• Sum Rule: Use when selecting one option from mutually exclusive tasks.

  • Total ways: $n + m$
  • Key Point: Tasks cannot occur at the same time.

• Product Rule: Use when making a sequence of independent choices.

  • Total ways: $n \times m$
  • Key Point: Choices do not affect each other.

• Permutations: Counting the number of ways to arrange distinct objects where order matters.

  • Total permutations of $n$ distinct objects: $n!$
  • Permutations of $r$ objects from $n$: $P(n, r) = \frac{n!}{(n - r)!}$
  • Key Points:
    • Order matters.
    • Objects are distinct.

• Combinations: Counting the number of ways to select distinct objects where order does not matter.

  • Total combinations of $r$ objects from $n$: $C(n, r) = \frac{n!}{r!(n - r)!}$
  • Key Points:
    • Order does not matter.
    • Objects are distinct.

• Arrangements with Non-Distinct Objects:

  • When objects are identical, adjust the permutation count by dividing by the factorial of the counts of each type.

  • Formula:

    \[ \text{Number of arrangements} = \frac{n!}{k_1! \times k_2! \times \dotsm \times k_m!} \]

• Counting Integer Solutions (Stars and Bars Method):

  • Used to count the number of non-negative integer solutions to equations of the form $x_1 + x_2 + \dotsm + x_n = k$.

  • Formula:

    \[ \text{Number of solutions} = \binom{k + n - 1}{n - 1} \]

  • Key Points:

    • Adjust for constraints by redefining variables.
    • Equates to combinations with repetition.

• Bijection Principle:

  • Establishes that if there is a one-to-one correspondence between two sets, they have the same number of elements.
  • Key Point: Useful for counting complex sets by mapping them to simpler ones.

• $k$-to-1 Rule:

  • When counting indistinct arrangements, divide the total number of permutations by the number of indistinct arrangements ($k$).
  • Key Point: Adjusts for overcounting due to indistinguishable objects.

• Important in Permutations and Combinations:

  • Distinct Objects: Objects are considered different from each other (e.g., numbered balls).
  • Indistinct Objects: Objects are considered identical (e.g., identical twins, repeated letters).

• Implications:

  • When objects are distinct, each permutation or combination counts as unique.
  • When objects are indistinct, permutations that differ only by swapping indistinct objects are considered the same and must be counted accordingly.

• Mutual Exclusivity (Sum Rule):

  • Tasks or events are mutually exclusive when they cannot occur simultaneously.
  • Example: Choosing either a red or blue shirt when you cannot wear both at the same time.

• Independence (Product Rule):

  • Choices are independent when the outcome of one choice does not affect the outcomes of others.
  • Example: Rolling two dice; the result of one die does not influence the other.

1. Arranging “STATISTICS”:

   • How many unique ways can you arrange the letters in “STATISTICS”?
   • Solution:

     • Letters and Counts:

       • S: 3
       • T: 3
       • A: 1
       • I: 2
       • C: 1

     • Total letters: $n = 10$

     • Calculation:

       \[ \text{Number of arrangements} = \frac{10!}{3! \times 3! \times 2!} = \frac{3628800}{72} = 50400 \]

2. Distributing Marbles:

   • How many ways can you distribute 15 identical marbles into 4 boxes so that each box contains at least 2 marbles?
   • Solution:

     • Adjust for minimums:

       • Let $x_i’ = x_i - 2$ ($x_i’ \geq 0$)

       • Adjusted equation:

         \[ x_1’ + x_2’ + x_3’ + x_4’ = 15 - 8 = 7 \]

     • Apply Stars and Bars:

       \[ \text{Number of ways} = \binom{7 + 4 - 1}{4 - 1} = \binom{10}{3} = 120 \]

3. Integer Solutions with Maximum Constraints:

   • Find the number of non-negative integer solutions to $x + y + z = 10$ where $x \leq 5$.
   • Solution:

     • Since $x \leq 5$, consider $x$ values from 0 to 5.

     • For each $x$, the equation becomes $y + z = 10 - x$ with $y, z \geq 0$.

     • For each $x$, calculate the number of solutions:

       \[ \text{Number of solutions for } x = k = \binom{(10 - k) + 2 - 1}{2 - 1} = 11 - k \]

     • Sum over $x = 0$ to $5$:

       \[ \sum_{k=0}^{5} (11 - k) = 11 + 10 + 9 + 8 + 7 + 6 = 51 \]

4. Distributing Balls with At Least One in Each Box:

   • How many ways can 8 identical balls be placed into 3 boxes if each box must contain at least one ball?
   • Solution:

     • Adjust for minimums:

       • Let $x_i’ = x_i - 1$ ($x_i’ \geq 0$)

       • Adjusted equation:

         \[ x_1’ + x_2’ + x_3’ = 8 - 3 = 5 \]

     • Apply Stars and Bars:

       \[ \text{Number of ways} = \binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = 21 \]