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
Choose denominations for pairs
Choose cards from smaller denomination
Choose cards from larger denomination
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.