Discrete Mathematics - Counting, Probability, and Distributions Study Notes
Discrete Mathematics Assessment: Quiz 4 Overview
- Course Details: HELP Bachelor of Information Technology (Hons), May Semester 2026.
- Subject: Discrete Mathematics (BIT108).
- Quiz Date: 23/8/2026.
- Assessment Weight: Quiz 4 accounts for of the overall marks for the subject.
- Format:
- Duration: 2 hours.
- Total Marks: 100.
- Structure: Three (3) specific questions.
- Question Distribution:
- Question 1: Application of counting techniques including the Multiplication Principle, Addition Principle, Inclusion-Exclusion Principle, Permutation, and Combination.
- Question 2: Problem-solving involving marginal and conditional probability. Requires knowledge of outcomes, sample space, and properties of probability.
- Question 3: Probability distributions. Requires building distribution tables from data and computing the mean and standard deviation of a probability distribution or Binomial Distribution.
Fundamental Counting Principles
Multiplication Principle: If an activity can be constructed in successive steps where step 1 can be done in ways, step 2 in ways, and so on up to step in ways, then the total number of different activities is .
- Menu Example (Kay’s Quick Lunch): The menu features 2 appetizers, 3 main courses, and 4 beverages.
- Dinners with one main course and one beverage: .
- Dinners with one main course and an optional beverage: (the 5th option represents no beverage).
- String Formation: Number of strings of length 4 from the letters ABCDE without repetition: .
- Strings beginning with B: .
- Strings not beginning with B: (or ).
- Digital Encoding: Encoding light amounts as an eight-bit string results in possible values.
- Menu Example (Kay’s Quick Lunch): The menu features 2 appetizers, 3 main courses, and 4 beverages.
Addition Principle: Suppose that are sets and the set has elements. If the family of sets is pairwise disjoint (meaning if , ), the number of elements that can be selected from is .
- Example (Book Selection): Selecting two books from different subjects among 5 computer science, 3 mathematics, and 2 art books:
- CS and Math:
- CS and Art:
- Math and Art:
- Total ways (Addition Principle): .
- Example (Committee Selection): A committee of Alice, Ben, Connie, Dolph, Egbert, and Francisco selecting chairperson, secretary, and treasurer.
- Alice or Ben as chairperson: .
- Example (Book Selection): Selecting two books from different subjects among 5 computer science, 3 mathematics, and 2 art books:
Inclusion-Exclusion Principle: Generalizes the Addition Principle for sets that are not necessarily disjoint.
- Two Finite Sets: .
- Three Finite Sets: .
- Application (Course Enrollment): In a group of 191 students, 10 take French, business, and music; 36 take French and business; 20 take French and music; 18 take business and music; 65 take French; 76 take business; and 63 take music. Students not taking any of the three: 51.
- Integers Example: Number of integers between 1 and 10,000 that are multiples of 3, 5, or 11 is 5152.
Permutations and Combinations
Permutations: An ordering of distinct elements. There are permutations of elements.
- Formula for r-permutations: .
- Selection Example: Selecting a chairperson, vice-chairperson, secretary, and treasurer from 10 people: .
- Logical Application: Assigning 5 computers to 3 people: ways.
Combinations: An unordered selection of elements from a set of distinct elements (an r-element subset).
- Formula: .
- Committee Example: Selecting a committee of three from 10 people: .
- Gender-specific Selection: Selecting 2 women from 5 and 3 men from 6: .
Probability Concepts and Experiments
Probability Applications in IT:
- Programming games and simulation software (predicting future outcomes like stock prices).
- Project Risk Management (calculating probability of risks in software projects).
- Communications (assessing probability of error in data transfer).
Definitions and Notation:
- Experiment: A process that results in one and only one of many observations.
- Outcome: The specific observation resulting from an experiment.
- Sample Space: The collection of all possible outcomes.
- Event: Consists of one or more outcomes.
- Simple Event: One and only one outcome.
- Compound Event: Contains more than one outcome.
Probability Properties:
Approaches to Probability:
- Classical Probability: Outcomes have equal probability.
- Relative Frequency: Outcomes are not equally likely; calculated as based on repeated experiments.
- Subjective Probability: Outcomes are not equally likely and experiments cannot be repeated.
Probability Rules and Calculations
- Marginal Probability: The simple probability of a single event without considering others. Example: Gender-based favor/against CEO salaries among 100 employees.
- .
- Conditional Probability: The probability an event will occur given another event has already occurred.
- Notation: .
- Example: .
- Independent vs. Mutually Exclusive Events:
- Independent: Events where occurrence of one does not affect the probability of the other. Checked by .
- Mutually Exclusive: Events that cannot occur together (e.g., scoring an odd number and even number on a die). .
- Complementary Events: Denoted by , includes all outcomes not in A. .
- Multiplication Rule:
- Dependent: .
- Independent: .
- Addition Rule:
- For any events: .
- For mutually exclusive: .
Probability Distributions
- Random Variables:
- Discrete: Assumes countable values (integer values).
- Continuous: Can assume any value within an interval (measurement values).
- Characteristics of Discrete Probability Distributions:
- Mean and Expected Value: Denoted as or .
- .
- Standard Deviation: Measures the spread of the probability distribution.
- Example (Lorraine Corporation): Annual profit scenarios (1.2 million, loss of \mu = 1.661\sigma = 2.314.\n\n# Binomial Probability Distribution\n\n* **Conditions for a Binomial Experiment**:\n * There are n identical trials.\n * Each trial has 2 outcomes: Success or Failure.\n * Probability of success (pq = 1-p) remain constant.\n * Trials are independent.\n* **Binomial Formula**: P(x) = C(n, x) p^x q^{n-x}.\n * **Mean and Standard Deviation**:\n * \mu = np\n * \sigma = \sqrt{npq}\n* **Example (Delivery Service)**: 2% packages fail. For 10 packages:\n * P(x=1) = C(10, 1)(0.02)^1(0.98)^9 = 0.1667.\n * P(x \leq 1) = P(0) + P(1) = 0.8171 + 0.1667 = 0.9838.\n\n# Application to Information Technology and Management\n\n* **Expected Value in Decision Making**: Project managers use expected values to choose between development strategies.\n * **Scenario**: In-house (65% success, $100k gain; 35% failure, $50k loss) vs. Outsourced (80% success, $80k gain; 20% failure, $70k loss).\n * E(\text{In-house}) = (0.65 \times 100000) + (0.35 \times -50000) = 47500.\n * E(\text{Outsourced}) = (0.80 \times 80000) + (0.20 \times -70000) = 50000.\n * Conclusion: The outsourced option is preferable as it has a higher expected value.\n* **Contest Strategy**: Expected winnings from a contest with primary prize of $100,000, two $40,000 prizes, and two $10,000 prizes across 2,000,000 entries compare against the entry cost of $0.50.\n\n# Practice Exercises\n\n* **Counting Numbers**:\n * How many 4-digit numbers from digits 1, 4, 7, 8 without repetition?\n * How many 4-digit numbers from digits 1, 2, 4, 5, 7, 9 without repetition?\n* **Strings and Sets**:\n * How many eight-bit strings begin with 11, end with 10, or both?\n * Integers between 1 and 1000 inclusive that are multiples of 2 or 7.\n* **Sample Spaces**:\n * Choosing a letter from the word 'GARDENS': {G, A, R, D, E, N, S}.\n * Revision hours assumed between 7:00 pm and 12:00 midnight (0 to 5 hours).\n* **Fraud Analysis Case Study**:\n * Total transactions: 2500.\n * Fraudulent transactions: 250.\n * Canadian transactions: 750.\n * Canadian and fraudulent: 95.\n * Task: Determine independence between Canadian and fraudulent transactions by comparing P(\text{fraudulent})P(\text{fraudulent|Canada})$$.