CS202 Study Guide

2a. Describe counting, permutation, and combination rules

• Why is it insufficient to only calculate the number of raw members of a given set?
• How is it possible to estimate the amount of work needed to account for a range of possibilities?
• How are counting techniques used to enumerate options? How so?

In Unit 1, we learned to calculate |<set>|, to count the number of members contained in a given set. While it is important to know how many members a set has, that is only the beginning. We can also enumerate options and evaluate the impact of those options on a given situation. For instance, let's take those members as the itemization of steps in a particular process. If each step can be taken independently of the other steps, it is possible to arrange their accomplishment in numerous ways (permutations), depending on the resources available at any given time. If there is only one step-performance resource available, then only one step can be taken at a time. Yet, "independently" means that it does not matter which step happens at any given time, as long as each step happens only once. Thus, the sequence does not matter, as long as all steps are accomplished. The steps can be ranked according to time-to-accomplish and then do the quickest steps first in order to show rapid progress. If all steps take the same amount of time, then any order will do. It depends on the situation. Similar thinking applies to situations where more than one step-performance resource is available.

Other performance criteria come into play in situations where order matters or when repetition is allowed. For example, consider combinations of steps and how the steps can be arranged if they are taken two at a time. The main point is that mathematics exists to calculate and enumerate the options. We can then study the options and decide which course of action to take. What is most needed in the beginning is to study carefully so that all members of the set, all factors impacting a domain, are known. 

Review Introduction to the Rule of Products.

2b. Compute the number of permutations and combinations of the members of a given set

• What is the difference between the number of a set's subsets and the number of ways to order the members of that same set?
• The "key" to a database management system is a unique attribute value assigned to each record. How does that concept apply to the ordering of a set's members?
• Computing a factorial, N!, is often used in various forms of mathematics. How is it useful in set theory?

We continue our study of various ways to organize members of a set, and how to project the number of ways a set's members can be organized. We can count the members of a set, project the number of subsets of those members, and the number of ways those subset members can be arranged. We can also determine the method by which those members have to be arranged. Such is the benefit of set theory.

There is a certain unity in mathematics. For instance, taking the factorial of a given number, $\prod_{n=1}^{N}$ where 0! = 1, is used, for instance, in Taylor Series, a means of estimating the result of various equations. In set theory, factorials are used to calculate the number of ways the members of a set can be ordered, |<set>|!. This gives the number of unkeyed orderings. If we select a key, some criteria unique to each member, then there is only one ordering. But, if the key is not unique, then the number of possible orderings is ≤ |<set>|! Set theory provides for exact calculation but also allows for estimates, in this sense.

Review Ordering Elements of a Set.

2c. Determine the number of all possible outcomes of a collection of events

• What is the difference between counting groups of ordered elements and counting groups of unordered elements?
• What is an example of cost estimation when creating groups of unordered elements?
• Is it possible, using set theory, to estimate the number of members of a group under imperfect conditions? How so?

Remember it is possible to calculate the number of groupings of a set's members. However, we assumed that there was only one way to order each group. In our present area of learning, we assume that groups can be unordered, that a new group is formed if the order of membership of that group changes. First, determine the number of ordered groups and then determine the number of ways the members of each group can be arranged. (Note that some literature uses the term "subset" for "group").

The ability to list all groups and all options in a given situation can have serious implications for cost estimating. For example, let's take set members as a list of tasks, the sequence of which does not matter. If we list all unordered groups, we assume that each ordering has the same cost to carry out. However, each ordering can be assigned an estimated cost of carrying out that task sequence, if one task is performed at a time. We could, for instance, rank tasks in a subset by their ability to support other members of that subset. Then, of all the arrangements of the original ordered collection of subsets, we could select the one having the highest-ranked member as the first member. In this way, we evaluate all possibilities according to some clear metric. This moves our decision from subjectivity to objectivity, a very data-centric approach to things.

So much of "theory", including set theory, that inhibits its practical application is that theory assumes certain, sometimes unspoken or unrealized, conditions. An example from our readings is the flipping of a coin. For the examples to play out as written, one must assume the coin is evenly balanced so that there is always an equal chance of heads or tails being rolled. But what if the coin is not evenly balanced? What if there is a 75% chance of heads being rolled and 25% of tails. (We assume the coin is thin enough that it cannot land on its side.) We might multiply the count under perfect conditions by the count under imperfect conditions, as a start. One must consider all factors impacting the situation at hand.

Review: 

• Ordering Elements of a Set
• Combinations and the Binomial Theorem

Unit 2 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• combinations 
• enumerate
  
• key
• factorials
• ordered 
• permutations
• subset
• unkeyed orderings 
• unordered