DM unit 4 notes

https://drive.google.com/file/d/1ktkfEyM6WTEDskh8cLjXqf7uHlRqd57-/view?usp=sharing

This document provides an introduction to elementary combinatorics, focusing on fundamental counting principles, permutations, combinations, and theorem applications. The basic rules of counting, the Sum Rule and the Product Rule, are defined and illustrated with examples. Permutations are introduced as arrangements of elements in a sequence, with formulas for both arrangements of distinct objects ($n P_r$) and permutations with repetition. Combinations are defined as unordered selections, and the formula for selecting $r$ elements from $n$ distinct elements ($n C_r$) is provided. The document also covers the Binomial Theorem and the Multinomial Theorem, which generalize binomial expansions to expressions with more than two variables. Finally, the Principle of Inclusion-Exclusion for two and three sets is presented as a method for counting the size of a union of sets.

Here are 5 key bullet points of the specific topics covered with a brief definition for each:

• Sum Rule: If a first task can be done in $n_1$ ways and a second task in $n_2$ ways, and the tasks cannot be done at the same time, there are $n_1 + n_2$ ways to do either task.
• Product Rule: If a procedure can be broken down into a sequence of two tasks, with $n_1$ ways to do the first task and $n_2$ ways to do the second task for each of the $n_1$ ways, then there are $n_1 \times n_2$ ways to do the procedure.
• Permutations ($n P_r$): The number of ways to arrange $r$ elements from a set of $n$ distinct elements, given by the formula $n P_r = \frac{n!}{(n-r)!}$.
• Combinations ($n C_r$): The number of ways to select an unordered selection of $r$ elements from a set of $n$ distinct elements, given by the formula $n C_r = \frac{n!}{r!(n-r)!}$.
• Principle of Inclusion-Exclusion: For two sets $A_1$ and $A_2$, the number of ways to do task $T_1$ or task $T_2$ is $n(A_1 \cup A_2) = n(A_1) + n(A_2) - n(A_1 \cap A_2)$.