Combinatorics and Probability

Counting Principles

Counting principles are foundational tools in statistics and probability, allowing us to determine the number of ways events can occur. These principles include the rule of product, permutations, and combinations.

• Rule of Product: If one event can occur in m ways and another in n ways, then both events together can occur in m × n ways.

• Permutations: The number of ways to arrange n distinct objects is (n factorial).

• Combinations: The number of ways to choose k objects from n without regard to order is .

Example: The number of ways to arrange the letters in the word "ADOPTION" so that T is not the last letter is .

Subsets and Set Theory

Set theory is used to describe collections of objects and their relationships. The number of subsets of a set with n elements is .

• Subset: Any collection of elements from a set, including the empty set and the set itself.

• Union and Intersection: The union of sets A and B is all elements in either set; the intersection is elements in both.

Example: If set A has 4 elements, it has subsets.

Tree Diagrams and Probability

Tree diagrams are visual tools for mapping out all possible outcomes of a sequence of events, useful for calculating probabilities and counting outcomes.

• Branches: Each branch represents a possible outcome at each stage.

• Counting Outcomes: The total number of outcomes is the product of the number of branches at each stage.

Example: If 32 symphony members attend concerts with overlapping attendance, a tree diagram helps determine how many attend all three concerts.

Permutations with Restrictions

Sometimes, arrangements must satisfy certain conditions, such as keeping items together or apart.

• Distinguishable Arrangements: If some items are identical, divide by the factorial of the number of identical items.

• Restrictions: For example, if items of the same brand must be together, treat them as a single unit.

Example: Arranging watches so that those of the same brand are together involves grouping and then permuting the groups.

Combinations with Multiple Categories

When selecting items from multiple categories, use the multiplication principle and combinations.

• Partitioning: Dividing items into groups, such as distributing toys into boxes with fixed sizes.

• Multinomial Coefficient: The number of ways to partition n items into groups of sizes is .

Example: Packing 80 toys into four boxes of 20 each: .

Applications of Counting Principles

Counting principles are applied in various real-world scenarios, such as:

• Making Change: Finding the number of ways to make a certain amount using coins of different denominations.

• Seating Arrangements: Determining the number of ways people can be seated with or without restrictions.

• Selecting Items: Choosing a subset of items from a larger set, such as selecting action figures.

Example: The number of ways to give 40 cents in change using only quarters, dimes, and nickels involves solving for non-negative integers q, d, n.

Summary Table: Key Counting Formulas

Additional info:

• These principles are foundational for probability, statistics, and discrete mathematics.

• Tree diagrams are especially useful for visualizing conditional probabilities and complex counting problems.

• Many questions in the file are typical of introductory statistics or combinatorics exams, focusing on enumeration, arrangements, and basic probability.