Today we look at some counting theories:
Counting theories explain how many without actually enumerating how many. This is very helpful when it is not only daunting to count a set of items but also when it is difficult to make the set.
Consider for example how many different ways can we arrange n distinct elements ?
We review some of the elements of counting theory.
A set of items that we wish to count can sometimes be expressed as a union of disjoint sets or as a Cartesian product of sets.
The rule of sum says that the number of ways to choose an element from one of two disjoints sets is the sum of the cardinalities of the sets.
The rule of product says that the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element.
We look at them in detail now.
If A and B are two finite sets with no members in common, then the number of ways to choose an item from one of the sets is the count of items in both sets. For example, a license plate may have either alphabets or numbers in each of the position. Since there are 26 alphabets and 10 numbers, there is only one pick out of 36. We can now extend this to sets that have duplicates and the answer does not change because it depends on cardinalities.
If we use the same sets A and B we can express the number of ways to choose an ordered pair is to choose the first element times that from the other set. For example, an icecream with 28 flavors and 4 toppings can be mixed and matched to give 28*4 different icecreams.
Counting theories explain how many without actually enumerating how many. This is very helpful when it is not only daunting to count a set of items but also when it is difficult to make the set.
Consider for example how many different ways can we arrange n distinct elements ?
We review some of the elements of counting theory.
A set of items that we wish to count can sometimes be expressed as a union of disjoint sets or as a Cartesian product of sets.
The rule of sum says that the number of ways to choose an element from one of two disjoints sets is the sum of the cardinalities of the sets.
The rule of product says that the number of ways to choose an ordered pair is the number of ways to choose the first element times the number of ways to choose the second element.
We look at them in detail now.
If A and B are two finite sets with no members in common, then the number of ways to choose an item from one of the sets is the count of items in both sets. For example, a license plate may have either alphabets or numbers in each of the position. Since there are 26 alphabets and 10 numbers, there is only one pick out of 36. We can now extend this to sets that have duplicates and the answer does not change because it depends on cardinalities.
If we use the same sets A and B we can express the number of ways to choose an ordered pair is to choose the first element times that from the other set. For example, an icecream with 28 flavors and 4 toppings can be mixed and matched to give 28*4 different icecreams.
No comments:
Post a Comment