I'm working on some assignments in my discrete math class for the sum & product combinatorics rules and I'm having trouble understanding their definitions and how they work. I'm hoping someone can help me visualize things a bit to understand this a bit more. Here are my current working definitions:
Sum Rule DefinitionThe rule of sum is another basic counting principle. Stated simply, it is the idea that if we have a ways of doing something and b ways of doing another thing and we can not do both at the same time, then there are a + b ways to choose one of the actions.
Here is a formal statement of the sum rule, expressed in terms of sets:
Consider n sets, $A_{1}, A_{2},\cdots,A_{n}$. If the sets are mutually disjoint $(A_{i} \cap A_{j} = ∅$ for $i \ne j)$, then,
$|A_{1}\cup A_{2}\cup \cdots \cup A_{n} | = |A_{1} | + |A_{2} | + … + |A_{n} |$
Product Rule DefinitionIn combinatorics, the rule of product or multiplication principle is a basic counting principle (a.k.a. the fundamental principle of counting). Stated simply, it is the idea that if there are a ways of doing something and b ways of doing another thing, then there are a ∙ b ways of performing both actions.
In set theory, this multiplication principle is often taken to be the definition of the product of cardinal numbers.[1] We thus have:
Let $A_{1}, A_{2},\cdots,A_{n}$ be finite sets. Then,
$|A_{1} × A_{2} × … × A_{n}| = |A_{1}|\bullet|A_{2}| \bullet\cdots\bullet |A_{n}|$
where $×$ is the Cartesian product operator. These sets need not be finite, nor is it necessary to have only finitely many factors in the product;
Assignment problem I had and answers I gave:
In a particular state, the license plates have 7 characters. Each character can be a capital letter or a digit except for 0. (The set of possible digits is {1; 2; 3; 4; 5; 6; 7; 8; 9}.) A person witnesses a crime and remembers some information about the license plate of the getaway car. The authorities would like to figure out how many license plates need to be checked in each case. For each constraint given below, indicate the number of license plates that satisfy that constraint. Note: you do not need to calculate the number. You may keep the multiplications and powers in your answers
$A={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z}$
$B={1,2,3,4,5,6,7,8,9}$
$|A|=26$
$|B|=9$
Problem 10.1.1a: No constraints
Since each of the 7 characters of a license plate can be a capital letter OR a digit, then each character has |A| + |B| possibilities, namely 35 possibilities for each character. There are 7 characters, meaning there are 35^{7} license plate possibilities.
Problem 10.1.1b: The license plate starts with a digit
$35^{6}\bullet 9$ possibilities
Problem 10.1.1c: First three are letters
$35^{4}\bullet 26^{3}$possibilities
Problem 10.1.1d: First three are letters and last four are numbers
$26^{3}\bullet 9^{4}$ possibilities
I was just hoping someone could help clarify the definitions a help me visualize things. I really appreciate your time.
$\endgroup$1 Answer
$\begingroup$For the sum rule, imagine you can either choose an element from set $A$ containing $m$ elements or choose an element from set $B$ containing $n$ elements. If you choose from set $A$, you have $m$ choices and if you choose from set $B$, you have $n$ choices. Assuming we dont know from which set you choose, you have a total of $m+n$ ways of choosing an element.
Now for the product rule, assume the same situation but now you have to choose one element from each set at the same time. Let us assume you chose any one element from set $A$, you would have $n$ choices to choose an element from set $B$. Thus for each element you choose from set $A$, you would have $n$ choices to choose an elements from set $B$. As there are $m$ elements in set $A$, the total ways of choosing one element from each set at the same time is $m\cdot n$
$\endgroup$
