Unit 5: Counting methods and Probability

Part 1: Counting Methods

1. Principles of Counting

The foundation of combinatorics is built upon two fundamental principles of counting:

• The Rule of Addition (OR Principle): If a task can be performed in ways and another independent task can be performed in ways, then either of the two tasks can be performed in ways. This applies when the choices are mutually exclusive.
• The Rule of Multiplication (AND Principle): If a task consists of two steps, where the first step can be done in ways and the second step can be done in ways, then the entire task can be performed in ways.

2. Numerical Permutation

Permutation refers to the arrangement of objects in a specific order.

• Formula for Permutation: The number of ways to arrange objects taken from distinct objects is denoted by .

A. Formation of Numbers

• Without Repetition: Forming a 3-digit number from digits 1, 2, 3, 4, 5 without repetition requires selecting and arranging 3 digits out of 5. ().
• With Repetition: If repetition is allowed, each of the 3 places can be filled in 5 ways ().
• Note on Zero: When forming numbers, the first digit (highest place value) cannot be 0. If forming a 3-digit number from 0, 1, 2, 3, the hundreds place has 3 options (1, 2, 3).

B. Sum of Numbers Formed
To find the sum of all -digit numbers formed using distinct non-zero digits (without repetition):

• Formula:
• Example: Sum of all 3-digit numbers formed by 2, 3, 4 is .

3. Alpha Permutation (Words and Letters)

A. Rearrangement of Words

• Distinct Letters: Arranging a word with distinct letters can be done in ways.
• Repeating Letters: If a word has letters where one letter repeats times, another times, and another times, the number of distinct permutations is:
  • Example (MISSISSIPPI): 11 letters (4 I's, 4 S's, 2 P's). Arrangements = .
• Vowels/Consonants Together: Treat the grouped elements as a single entity (string method), arrange the entities, and then multiply by the internal arrangement of the grouped elements.

B. Rank of a Word
Finding the rank of a word in a dictionary formed by its own letters:

1. Write the letters of the word in alphabetical order.
2. Count the number of words starting with letters that come before the first letter of the target word using factorials.
3. Fix the first letter, then repeat the process for subsequent letters until the target word is formed. Add 1 for the word itself.

4. Circular Arrangement

Arranging objects in a circle removes the concept of a fixed starting point.

• Standard Circular Permutation: The number of ways to arrange distinct objects in a circle is .
• Clockwise and Counter-Clockwise Indistinguishable: If the arrangement can be flipped (like a necklace made of beads or a garland of flowers), the number of arrangements is halved: .

5. Distribution Based Questions

Distributing items into groups or boxes involves combinations and permutations, heavily relying on the nature of the items and boxes.

• Distinct Items into Distinct Boxes: Each of the items has choices. Total ways = .
• Identical Items into Distinct Boxes (Stars and Bars Method):
  • Number of ways to distribute identical items into distinct boxes such that each box can receive zero or more items:
  • Number of ways to distribute identical items into distinct boxes such that each box receives at least one item (where ):

6. Formation of Committee

Committees do not require a specific order, making this an application of Combinations.

• Formula for Combination: Selecting objects from distinct objects without regard to order: .
• Mixed Selection: Forming a committee of 3 men and 2 women from a group of 6 men and 5 women:
  • Select men:
  • Select women:
  • Total ways (AND Principle):
• At least / At most constraints: Calculate the combinations for all possible valid scenarios and add them together (OR Principle).

7. Geometry Based Problems

Combinatorics applies heavily to counting geometric figures formed by a set of points. Given distinct points in a plane:

• Number of Straight Lines: (If points are collinear, lines = )
• Number of Triangles: (If points are collinear, triangles = )
• Number of Diagonals in an -sided polygon: or
• Parallelograms from intersecting parallel lines: If parallel lines intersect parallel lines, parallelograms formed = .

Part 2: Probability

1. Concept of Probability

Probability measures the likelihood or chance that a specific event will occur.

• Experiment: An action that produces a well-defined outcome (e.g., rolling a die).
• Sample Space (): The set of all possible outcomes of an experiment.
• Event (): A subset of the sample space.
• Mathematical Definition: The probability of an event is the ratio of favorable outcomes to the total number of possible outcomes.
• Axioms:
  • (Probability of a certain event)
  • (Probability of the complement/not occurring)

2. Classification of Events

• Simple Event: An event containing only a single outcome (e.g., rolling a 3 on a die).
• Compound Event: An event containing more than one outcome (e.g., rolling an even number).
• Mutually Exclusive Events: Events that cannot occur simultaneously. If and are mutually exclusive, , and .
• Exhaustive Events: A set of events that together encompass all possible outcomes. .
• Independent Events: The occurrence of one event does not affect the probability of another. .
• Dependent Events: The occurrence of one event affects the probability of the other (e.g., drawing cards without replacement).

3. Conditional Probability

Conditional probability is the probability of an event occurring given that another event has already occurred.

• Formula: The probability of event given that event has occurred is denoted by .
  • , where
• Multiplication Theorem: Derived from conditional probability, .

4. Problems Based on Coins, Dices, and Cards

A. Coins
When a coin is tossed, there are 2 outcomes: Head (H) or Tail (T).

• 1 Coin: Sample Space = {H, T}. .
• 2 Coins: Sample Space = {HH, HT, TH, TT}. .
• Coins: Total outcomes = .
• Typical Problem: Probability of getting exactly 2 heads in 3 tosses. has 8 outcomes, favorable are {HHT, HTH, THH}. .

B. Dices
A standard die has 6 faces numbered 1 through 6.

• 1 Die: Sample Space = {1, 2, 3, 4, 5, 6}. .
• 2 Dices: Sample Space consists of 36 pairs (from (1,1) to (6,6)). .
• Dices: Total outcomes = .
• Typical Problem: Probability of getting a sum of 8 with two dice. Favorable outcomes = {(2,6), (3,5), (4,4), (5,3), (6,2)}. .

C. Cards
A standard deck contains 52 cards, divided equally into 2 colors (Red, Black) and 4 suits (Spades, Clubs, Hearts, Diamonds).

• Structure:
  • Black suits: Spades (13), Clubs (13)
  • Red suits: Hearts (13), Diamonds (13)
  • Cards per suit: Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King.
• Face Cards: Jacks, Queens, and Kings are face cards. There are face cards in a deck.
• Typical Problem: Probability of drawing a Red King or a Black Jack. Total outcomes = 52. Favorable outcomes = 2 Red Kings + 2 Black Jacks = 4. . Selecting multiple cards requires the use of Combinations ().