AMTH 108 - Chapter 1 Notes

Elementary Ideas and Notions

1.1 Remembrance of Things Past

• Factorials: The notation for factorial is defined as n! = n(n - 1)(n - 2)…3 · 2 · 1

  • Special case: By convention, 0! = 1.

1.2 Some Set Theory

• Set Definition: A set denoted as X is
  a collection of objects, which can be finite or infinite.

• Membership:

  • If x ∈ X, x is a member of the set X.

• Subset:

  • Denoted A ⊂ B means set A is a subset of set B; all elements of A are also in B.

• Union:

  • A ∪ B represents the union of sets A and B, which includes all elements of both sets, removing duplicates.

• Intersection:

  • A ∩ B (often written as AB) denotes the set of elements common to both A and B.

• Complementation:

  • The complement of A, denoted Ac, is the set containing everything not in A. It must refer to a universal set X where A is a subset.

• Empty Set:

  • Represented by ∅, it denotes a set with no elements.

Some Set Theory Examples

• Let X = {1, 2, 3, 4, 5, 6}, A = {1, 3, 4}, B = {1, 2, 4, 5}.

  • Membership: 1 ∈ X

  • Subset: A ⊂ X (true); A ⊄ B (false)

  • Union: A ∪ B = {1, 2, 3, 4, 5}

  • Intersection: A ∩ B = AB = {1, 4}

  • Complementation: Ac = {2, 5, 6}

  • Intersection of A and its complement: A ∩ Ac = AAc = ∅

  • Clarification: The juxtaposition AB is shorthand for A ∩ B.

1.3 Naive Probability

• In the late 1800s, mathematicians explored a theory linking numbers between 0 and 1 (probabilities) with events, leading to several foundational inferences:

  • Events with high probabilities (near 1) are likely to happen.

  • Events with low probabilities (near 0) are less likely to occur.

  • If event p has a probability less than event q (p < q), event p should occur less often than event q.

• Context: Gamblers wanted to understand outcomes in various games of chance depending on different rules.

Probability Computation

• To compute probability, the focus is on counting possible outcomes.

  • The probability of a favorable event is calculated as:

  P[favorable event] = \frac{# favorable ends}{Total # of endings}

  • Example: If Ash bets on a die roll being greater than 4:

  P[roll > 4] = \frac{2}{6}

  • Here, the favorable outcomes are 5 or 6, and total outcomes for a die roll range from 1 to 6.

• Note: This probability approach is valid when all possible outcomes are equally likely.

• Despite restrictions, numerous basic probability scenarios can be analyzed.

To Ponder (Probability Questions)

1. Two coins are tossed; represent outcomes with strings of H (heads) and T (tails).

   • If n=2, possible outcomes include HH, HT, TH, TT.

   • (a) If one coin on the table shows heads, what probability does the other coin have to be heads?

   • (b) After observing one coin showing heads, what is the probability that the other coin is also heads?

   • (c) For three coins tossed, determine the probability of exactly two heads and the probability of one head and one tail showing.

1.4 Counting

1.4.1 Multiplication Principle

• Definition #1: If there are n1 ways for experiment 1 and n2 for experiment 2 and n3 for experiment 3, then:

  • Total number of experimental combinations is $n1 * n2 * n3 … nr$.

• Definition #2: If the universe consists of objects classified by two categories with n flavors in the first and m in the second, then:

  • Total combination pairs is given by nm.

• Independence Requirement: The results of each experiment must not influence others.

1.4.2 Examples

• Coffee: At a cafe, coffee comes in sizes (4 options: small, medium, large, leviathan) and 2 temperatures (boiling, iced).

  • Total size/temperature combinations: $4 × 2 = 8$.

• Expanded Coffee Menu: If a cafe adds a blend category (5 options), the size/temperature/blend combinations become:

  • Total combinations: $4 × 2 × 5 = 40$.

Notes on Constraints

• Choices can be dependent (where restrictions exist) or independent (no restrictions).

1.4.3 Zip Codes Example

• US ZIP codes consist of 5 digits, with options for each digit ranging from 0 to 9.

• Total ZIP code combinations calculated as:

  • $10 × 10 × 10 × 10 × 10 = 10^5 = 100,000$.

  • Each digit selected from the same universe means selection can repeat (selection with replacement).

1.4.4 Selection With/Without Replacement

• Without Replacement: Chosen items are discarded, as seen in calculations of distinct digit ZIP codes:

  • Total: $10 × 9 × 8 × 7 × 6 = 30,240$.

• Counting Complementary Probabilities:

  • To find ZIP codes containing the number 4, count those without any 4. Total without 4 equals 95.

  • Hence ZIPs with 4 = Total ZIPs - ZIPs without 4: $100,000 - 95 = 40,951$.

1.4.5 Permutations

• Definition: A permutation is a tuple of k selected from n objects, where order matters. The number of permutations is expressed as:

  • $nPk = \frac{n!}{(n-k)!}$.

• The number represents k-tuples of ordered selections.

1.4.6 Executive Committees Example

• Formation of committees with titles from a group of 20 people:

  • President, vice-president, treasurer formation yields:

  • $20 × 19 × 18 = 6840$.

1.4.7 Combinations

• Definition: A combination is an unordered arrangement of k objects from n objects without replacement.

  • Number of combinations denoted as

  • $nCk = \frac{n!}{(n-k)!k!}$.

Examples of Combinations

• Committees from Members: Forming a committee from 20 people:

  • Count total un-ordered combinations, yielding: $20C3 = \frac{20!}{17!3!} = 1,140$.

• Poker Hands: From a deck of 52 cards, total ways for a 5-card hand: $52C5 = 2,598,960$.

• Lottery Tickets: Combined selections for Mega-lottery numbers, yielding an estimated large amount of combinations:

  • Total = 30 * $70C5$.

1.5 Additive Counting Principle

• Definition: For a set F of objects, partitioned by sets E1, E2, E3, … Em such that:

  • $F = \bigcup{i=1}^m Ei$

  • and $Ei \cap Ej = ∅$ when $i ≠ j$.

• The size of F can then be counted as:

  • #F = \sum{i=1}^m #Ei.

Examples of the Additive Counting Principle

• Books on the Beach: Calculation of ways to choose pairs of books by the same or different authors.

  • Same author: #E1 + #E2 + #E_3

• Two books from different authors can be similarly calculated by subtracting the cases where books are from the same author from total pairs.

  • Use of combinatorial counts of how to choose and partitioning helps simplify the process.

Problems

1. Coins: How many ways can I pull out coins composed of specific denominations?

2. Football Season: How to schedule wins and losses considering rules (not on consecutive games).

3. Club Officers: Options for selection with restrictions based on group dynamics.

Overall Takeaway: Understanding combinatorial principles, set theory, and counting are foundational for probability and various mathematical applications, emphasizing order and selection restrictions.