counting 7

CP214: Discrete Structures Study Notes

Overview

• Course: CP214 - Discrete Structures

• Topic: Counting

• Relevant Chapters: 6 and 8 of the Textbook

• Instructor: Dr. Shimaa Abdelmeguid

Outline

• Permutations and Combinations

  • Definition and explanation of concepts

  • Examples and calculations

• Pascal's Triangle and Binomial Coefficients

Permutations and Combinations

Key Definitions

• Permutation: An ordered arrangement of a set of distinct objects.

• r-Permutation: An ordered arrangement of r elements from a set of n distinct elements. Denoted as P(n, r).

  • Formula:
    

    $P(n, r) = \frac{n!}{(n - r)!}$

• Combination: An unordered selection of r elements from a set of n distinct elements.

• r-Combination: A subset of the set containing r elements. Denoted as C(n, r).

  • Notation of binomial coefficient:
    

    $C(n, r) = \frac{n!}{r!(n - r)!}$

Examples illustrating Permutations

1. Example of Selecting 3 from 6:

   • Question: How many different sets of 3 people can be picked from a group of 6?

   • Initial incorrect calculation: 6 choices for first, 5 for second, 4 for third:

     • $6 \times 5 \times 4 = 120$ (Incorrect because order matters)

   • Correct approach requires using combinations since the order is not relevant to the selection.

2. Example with Set S = {1, 2, 3}:

   • Permutation of 3 gives: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, etc.

   • Total permutations: 6 total, with:

     • P(3, 2) = 6 (for 2 permutations of 3 elements)

3. Theorem 1: Formula to find r-permutations from n distinct elements:

   • General form:
     

     $P(n, r) = n(n - 1)(n - 2) \times \text{…} \times (n - r + 1)$

   • Basic proof involves product rule and number of choices at each stage.

   • Noteworthy that P(n, 0) = 1, as there is one way to order zero elements.

Examples of Applications of Permutations

• Example 1: Awarding Medals

  • Problem: 8 runners with distinct awards (gold, silver, bronze).

  • Calculation:
    

    $P(8, 3) = 8! / 5! = 8 \times 7 \times 6 = 336$

• Example 3: Saleswoman Visiting Cities

  • Fixed starting point, permute remaining:

  • Calculation:
    

    $7! = 5040$

Combinations

Key Definitions

• r-Combination: Unordered selection of r elements from a set.

• Binomial coefficient: Notated as C(n, r), expressing the number of combinations.

Theorem 2: Count of Combinations Formula

• Formula: $C(n, r) = \frac{n!}{r!(n - r)!}$

  • Application in various contexts discussed in examples.

Examples of Combinations

1. Example of Selecting Poker Hands:

   • Problem: Choices from a 52-card deck.

   • Calculation for hands of 5:
     

     $C(52, 5) = \frac{52!}{5! \times 47!} = 2,598,960$

2. Selecting from Astronaut Crew:

   • Problem: Selecting 6 from a pool of 30.

   • Calculation:
     

     $C(30, 6)$ leads to 593,775 combinations.

3. Configuration in Soccer Club:

   • Split players into genders and count possibilities using:
     

     $C(8,6) \times C(7,5)$

   • Result: 588 configurations.

Permutations vs Combinations Applied in different Scenarios

1. Horse Race Scenarios where ties are possible—with detailed combinatorial counting for each tie scenario.

   • Total combinations concluded to be 13 ways.

2. Committee Formation with specific gender ratios demonstrating combinatorial principles by tallying cases cumulatively.

   • Total ways to establish given committee resulted in 96,460.

Binomial Coefficients and Theorems

1. Pascal’s Triangle:

   • Arrangement of binomial coefficients showing relations and calculations illustrated across layers.

   • Each row correlates to coefficients of binomial expansions like (a + b)ⁿ.

2. Binomial Theorem:

   • Expresses power expansions involving coefficients derived from combinations:
     

     $(a + b)ⁿ = \text{Sum of } C(n, k) \times a^{n-k} \times b^{k}$

   • Example with calculations from (x + y)² leading to consolidated expressions.

3. Application of Binomial Theorem for coefficients in complex expansions, demonstrating with variables raised to specific powers, showing specific instances of extraction of coefficients in polynomial forms.

Summary of Counting Principles Discussed

• Basic counting principles revisited.

• Inclusion-Exclusion Principle.

• Pigeonhole Principle.

• Permutations and combinations definitions/implementations.

• Binomial coefficients derived from Pascal's triangle and applications in algebraic expansions.