Ch04

Counting Basics

• Counting is fundamental in discrete mathematics, aiding in the computation of probabilities for discrete events such as lottery winnings.

Basic Counting Principles

Types of Counting Problems

• Examples include determining the number of possible 8-letter passwords or the ways to choose 11 soccer players from a team of 20.

Sum Rule

• Definition: If task 1 can be done in n1 ways and task 2 in n2 ways and these tasks cannot occur simultaneously, the total ways to perform either task is n1 + n2.

• Example: Free computer awarded to either a DS student (530 students) or a DS lecturer (15 lecturers) gives 530 + 15 = 545 choices.

Product Rule

• Definition: If a task can be subdivided into two sequential tasks where task 1 has n1 possibilities and task 2 has n2 possibilities proceeding after task 1, the total methods to complete this procedure is n1 * n2.

Example of Product Rule

• Scenario: Calculating different 3-letter license plates. Each letter has 26 options (A-Z). Thus, total combinations = 26 * 26 * 26 = 17,576.

Fundamental Counting Principle

• Illustrates the outcomes for combined events.

Example: Die and Coin

• When rolling a die and flipping a coin:

  • Outcomes of Die: 6

  • Outcomes of Coin: 2

  • Total Outcomes = 6 * 2 = 12

Example: College Interview Attire

• Combinations available to Robert who has:

  • 4 slacks, 3 shirts, 2 shoes, 5 ties.

  • Total possible outfits = 4 * 3 * 2 * 5 = 120.

Permutations

• Definition: An arrangement of items where order is crucial.

• Formula: To find permutations of n items, the Fundamental Counting Principle or factorial notation is used.

Example: Arranging ABC

• Arranging letters ABC:

  • Choices for the first blank: 3

  • Choices for the second: 2

  • Choices for the third: 1

  • Total arrangements = 3 * 2 * 1 = 6 (3!)

  • Possible permutations are ABC, ACB, BAC, BCA, CAB, CBA.

Permutations of r from n

• If selecting r items from n, the permutations can be calculated using the formula:

  • P(n, r) = n! / (n-r)!

Practice Problem: Lock Combinations

• Determine the number of 3-number combinations from 1 to 30.

Practice Problem: Elected Offices

• From a club of 24 members elected as President, Vice President, Secretary, Treasurer, and Historian:

  • Total ways = 24 * 23 * 22 * 21 * 20 = 5,100,480.

Combinations

• Definition: Arrangement of items where order is not vital.

• Combinations represent a part of permutations as order does not affect the selection.

Combinations Formula

• Number of ways to choose r items from n, denoted as C(n, r) or nCr:

  • C(n, r) = n! / [r!(n-r)!]

Practice Problems

Essay Questions

• A student must select 3 out of 5 essay questions:

  • Total ways = C(5, 3) = 10.

Basketball Team Lineup

• Selecting a center, forwards, and guards:

  • 2 Centers, 5 Forwards, 4 Guards.

  • Selection: 2 ways for center, 10 for forwards, 6 for guards.

  • Total combinations = 2 * 10 * 6 = 120.