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 10%10\% 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 tt successive steps where step 1 can be done in n1n_1 ways, step 2 in n2n_2 ways, and so on up to step tt in ntn_t ways, then the total number of different activities is n1×n2×⋯×ntn_1 \times n_2 \times \dots \times n_t.

    • 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: 3×4=123 \times 4 = 12.
      • Dinners with one main course and an optional beverage: 3×5=153 \times 5 = 15 (the 5th option represents no beverage).
    • String Formation: Number of strings of length 4 from the letters ABCDE without repetition: 5×4×3×2=1205 \times 4 \times 3 \times 2 = 120.
      • Strings beginning with B: 1×4×3×2=241 \times 4 \times 3 \times 2 = 24.
      • Strings not beginning with B: 120−24=96120 - 24 = 96 (or 4×4×3×2=964 \times 4 \times 3 \times 2 = 96).
    • Digital Encoding: Encoding light amounts as an eight-bit string results in 28=2562^8 = 256 possible values.
  • Addition Principle: Suppose that X1,…,XtX_1, \dots, X_t are sets and the ithi^{th} set XiX_i has nin_i elements. If the family of sets is pairwise disjoint (meaning if i≠ji \neq j, Xi∩Xj=∅X_i \cap X_j = \emptyset), the number of elements that can be selected from X1 or X2… or XtX_1 \text{ or } X_2 \dots \text{ or } X_t is n1+n2+⋯+ntn_1 + n_2 + \dots + n_t.

    • Example (Book Selection): Selecting two books from different subjects among 5 computer science, 3 mathematics, and 2 art books:
      • CS and Math: 5×3=155 \times 3 = 15
      • CS and Art: 5×2=105 \times 2 = 10
      • Math and Art: 3×2=63 \times 2 = 6
      • Total ways (Addition Principle): 15+10+6=3115 + 10 + 6 = 31.
    • Example (Committee Selection): A committee of Alice, Ben, Connie, Dolph, Egbert, and Francisco selecting chairperson, secretary, and treasurer.
      • Alice or Ben as chairperson: (1×5×4)+(1×5×4)=20+20=40(1 \times 5 \times 4) + (1 \times 5 \times 4) = 20 + 20 = 40.
  • Inclusion-Exclusion Principle: Generalizes the Addition Principle for sets that are not necessarily disjoint.

    • Two Finite Sets: ∣X∪Y∣=∣X∣+∣Y∣−∣X∩Y∣|X \cup Y| = |X| + |Y| - |X \cap Y|.
    • Three Finite Sets: ∣X∪Y∪Z∣=∣X∣+∣Y∣+∣Z∣−∣X∩Y∣−∣X∩Z∣−∣Y∩Z∣+∣X∩Y∩Z∣|X \cup Y \cup Z| = |X| + |Y| + |Z| - |X \cap Y| - |X \cap Z| - |Y \cap Z| + |X \cap Y \cap Z|.
    • 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 nn distinct elements. There are n!n! permutations of nn elements.

    • Formula for r-permutations: P(n,r)=n!(n−r)!P(n, r) = \frac{n!}{(n-r)!}.
    • Selection Example: Selecting a chairperson, vice-chairperson, secretary, and treasurer from 10 people: P(10,4)=10!6!=5040P(10, 4) = \frac{10!}{6!} = 5040.
    • Logical Application: Assigning 5 computers to 3 people: 5×4×3=605 \times 4 \times 3 = 60 ways.
  • Combinations: An unordered selection of rr elements from a set of nn distinct elements (an r-element subset).

    • Formula: C(n,r)=(nr)=n!r!(n−r)!C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}.
    • Committee Example: Selecting a committee of three from 10 people: C(10,3)=10!7!3!=120C(10, 3) = \frac{10!}{7!3!} = 120.
    • Gender-specific Selection: Selecting 2 women from 5 and 3 men from 6: C(5,2)×C(6,3)=10×20=200C(5, 2) \times C(6, 3) = 10 \times 20 = 200.

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:

    • 0≤P(Ei)≤10 \leq P(E_i) \leq 1
    • ∑P(Ei)=1\sum P(E_i) = 1
  • Approaches to Probability:

    • Classical Probability: Outcomes have equal probability.
    • Relative Frequency: Outcomes are not equally likely; calculated as P(A)=fnP(A) = \frac{f}{n} 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.
    • P(male)=60100=0.60P(\text{male}) = \frac{60}{100} = 0.60.
  • Conditional Probability: The probability an event will occur given another event has already occurred.
    • Notation: P(A∣B)P(A|B).
    • Example: P(in favor|male)=1560=0.25P(\text{in favor|male}) = \frac{15}{60} = 0.25.
  • Independent vs. Mutually Exclusive Events:
    • Independent: Events where occurrence of one does not affect the probability of the other. Checked by P(A∣B)=P(A)P(A|B) = P(A).
    • Mutually Exclusive: Events that cannot occur together (e.g., scoring an odd number and even number on a die). P(A∩B)=0P(A \cap B) = 0.
  • Complementary Events: Denoted by Aˉ\bar{A}, includes all outcomes not in A. P(A)+P(Aˉ)=1P(A) + P(\bar{A}) = 1.
  • Multiplication Rule:
    • Dependent: P(A∩B)=P(A)P(B∣A)P(A \cap B) = P(A)P(B|A).
    • Independent: P(A∩B)=P(A)P(B)P(A \cap B) = P(A)P(B).
  • Addition Rule:
    • For any events: P(A∪B)=P(A)+P(B)−P(A∩B)P(A \cup B) = P(A) + P(B) - P(A \cap B).
    • For mutually exclusive: P(A∪B)=P(A)+P(B)P(A \cup B) = P(A) + P(B).

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:
    • 0≤P(x)≤10 \leq P(x) \leq 1
    • ∑P(x)=1.000\sum P(x) = 1.000
  • Mean and Expected Value: Denoted as μ\mu or E(x)E(x).
    • μ=∑xP(x)\mu = \sum x P(x).
  • Standard Deviation: Measures the spread of the probability distribution.
    • Example (Lorraine Corporation): Annual profit scenarios (4.5million,4.5 million,1.2 million, loss of 2.3million)withassociatedprobabilities(0.32,0.51,0.17)resultin2.3 million) with associated probabilities (0.32, 0.51, 0.17) result in\mu = 1.661andand\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 (p)andfailure() and failure (q = 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})andandP(\text{fraudulent|Canada})$$.