ESE_122_Lecture_Nov 18

Welcome to ESE 122

• Course Title: Discrete Mathematics for Engineers

• Semester: Fall 2024

Course Topics

• Chapter 1: Speaking Mathematically (1.1-1.3)

• Chapter 2: Logic of Compound Statements (2.1-2.5)

• Chapter 3: Logic of Quantified Statements (3.1-3.2)

• Chapter 4: Elementary Number Theory and Methods of Proof (4.1-4.8)

• Chapter 5: Sequences

• Chapter 6: Set Theory (6.1-6.2)

  • 6.1: Definitions - equality, Venn Diagrams, etc.

  • 6.2: Properties of Sets

• Chapter 7: Functions

• Chapter 8: Relations

• Chapter 9: Probability

• Chapter 10: Graphs and Trees

Chapter 9: Probability and Counting

• 9.3: Counting Elements of Disjoint Sets: The Addition Rule (Nov 11)

• 9.4: Pigeonhole Principle (Nov 11)

• 9.5: Counting Subsets of a Set: Combinations (Nov 11)

• 9.6: r-Combination with and without Repetition (brief) (Nov 11)

• 9.7: Pascal’s Formula and Binomial Theorem (Nov 11)

• 9.8: Probability Axioms and Expected Values (Nov 11)

• 9.9: Conditional Probability, Bayes Formula, and Independent Events (Nov 13)

• Difference between Disjoint and Independent Events (Nov 13)

Combinations and Subsets

9.5 Counting Subsets of a Set: Combinations (1/6)

• The number of subsets of size r from a set S is called r-combination.

• Notable fact: Order in the subset is not important.

Example 9.5.1 – 3-Combinations

• Set: {Ann, Bob, Cyd, Dan}

  • a. List all 3-combinations of the set:

    • {Bob, Cyd, Dan} (leave out Ann)

    • {Ann, Cyd, Dan} (leave out Bob)

    • {Ann, Bob, Dan} (leave out Cyd)

    • {Ann, Bob, Cyd} (leave out Dan)

  • b. Number of 3-combinations: 4

  • c. Ways to form a committee of size 3: 4

Ordered vs. Unordered Selection

• Ordered Selection: Important to consider the order of elements.

• Unordered Selection: Only the identity of chosen elements matters.

Example 9.5.2 – Unordered Selection

• Unordered selection of two elements from {0, 1, 2, 3}:

  • {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}

  • Total unordered selections: 6

Theorem 9.5.1: Computational Formula for Combinations

• Formula for choosing subsets of size r from n elements: (n choose r)

Example 9.5.4 – Choosing Teams

• Choosing 5 members from 12: 792 distinct teams

Example 9.5.9 – Poker Hand Problems

• Types of Poker Hands:

  • Royal Flush: 10, J, Q, K, A of the same suit

  • Straight Flush: Five adjacent denominations of the same suit

  • Other hands include Four of a Kind, Full House, etc.

Process for Finding Hands with Two Pairs

1. Choose denominations for pairs

2. Choose cards from smaller denomination

3. Choose cards from larger denomination

4. Choose one from remaining cards

Total Number of Five-Card Hands

• Total hands possible with two pairs: Computation based on combinatorics

Example 9.5.11 – Permutations of Repeated Elements

• Arrangements of letters in the word MISSISSIPPI

• Distinguishable orderings are calculated based on steps outlined for placing letters.

r-Combinations with Repetition Allowed

• Choosing r elements from n categories where repetition is allowed.

• Formula: C(n+r-1, r)

Example Scenario - Selecting Cans of Soft Drinks

• Determine selections for 15 cans of soft drinks from 5 types

• a. Total selections: C(19,15)

• Consider cases where at least 6 cans of one type are chosen using the formulas above.

Integral Solutions of an Equation

• For the equation x1 + x2 + x3 + x4 = 10 with nonnegative integers, apply the selection formula.

Summary of Choosing Elements

• Different situations for selection (order matters or not, repetition allowed or not) summarized in a table format for clear reference.