1 Supplement D Advanced Counting Techniques We have seen and learned counting before in MA125 which is a process of establishing a one to one correspondence from a set to an initial segment of the sequence 1 2 3 4 5 and it is pretty easy to do when the set is very small or when the set is linearly ordered such as a long line of people waiting for flu shots However the situation will be quite different when we have a large and unordered set If you have ever seen the scene at Times Square in New York City during New Year s eve you will agree that counting the number of people in the crowd is by no means an easy task We will be counting something a bit more abstract in this chapter such as combinations and permutations and they are usually not ordered linearly We thus need to learn some special techniques Combinations and permutations exist almost everywhere They are indispensable to our lives Your social security number your phone number your car s license number and your computer password are all permutations of numbers and characters You may wonder why we need to count these abstract permutations One important reason is for security You may have an e mail account and you don t want any one else to access it so you make your password as difficult to guess as possible But other people are not stupid either they can write computer programs to guess it systematically So you need to know how many combinations and permutations there are for them to guess If this number is big enough even a supercomputer will take a long time to guess Suppose you are using six alphanumeric characters including upper and lower cases then you have about 5 68 1010 possible passwords and if some one uses a powerful computer that can check 100 times a second it still takes the computer about 18 years to check all permutations You are safe enough Enumeration techniques The most primitive way to count combinations is to list all of them in a systematic manner such as a table or a tree This may not be the most efficient way but it is the backbone of many advanced techniques and you should keep a mental picture of these tables and trees at all events Example 1 At Polar ice cream parlor there is a special every Thursday For 99 you can get a sundae with one big scoop of ice cream and one topping There are four different flavors vanilla strawberry rocky road and mint chocolate chip for the ice cream and three different toppings hot fudge caramel and nuts how many different special sundaes can be made Solution We can make a table of all possible combinations as follows 2 Vanilla hot fudge Vanilla caramel Vanilla nuts Strawberry hot fudge Strawberry caramel Strawberry nuts Rocky road hot fudge Rocky road caramel Rocky road nuts Mint hot fudge Mint caramel Mint nuts It is pretty clear that we have listed all possible combinations and nothing is listed twice Therefore the number of combinations is twelve As an alternative we can also draw a tree to represent these combinations We start from a point on the far left called the root of the tree and our tree usually grows sideways or even up side down because we write from left to right and from top to bottom The ends on the right are called leaves as we normally see on a tree Each leaf will then represent a combination and if we draw the tree correctly the number of leaves will be exactly the number of combinations For example the leaf on the top represent the combination vanilla hot fudge because if you were to travel from the root to this leave you would have to pass through the words vanilla and hot fudge Exercise Draw another tree similar to the one above but start with topping first Do you get the same number of combinations Example 2 3 At Hungry Ron s restaurant a meal consists of an entr e soup or salad and beverage Suppose that there are only 3 choices beef pork and chicken of entr e and 2 beverages Coke or Sprite how many different meals can be made Solution If you try to make a table of all combinations just like what we did before you will notice that you need a 3 dimensional table because there are three categories of food and that is beyond our ability The tree method however is still useful and all we need is to draw a bigger tree with one more level The answer 12 can then be obtained by counting the number of leaves on the tree After you have seen more examples you will agree that the tree diagram is a very powerful tool and in some difficult situations it may be the only tool we have Fundamental Counting Principle At this point you may have already figured out that there is a quicker and easier way to compute the number of combinations without drawing a table or a tree namely multiplying the number of choices in each category In the first example there are 4 flavors and 3 toppings therefore the number of combinations is 3 4 In the second example the number of combination is 3 2 2 which is also equal to 12 If you wonder why this is true you can look at the trees In the second one there are 3 branches coming out from the root each one then branches into 2 sub branches and 4 each sub branch splits into 2 even smaller branches Therefore the number of leaves must be the product 3 2 2 Any tree behaves so nicely is called a uniformly branching tree and whenever we have such a tree for the experiment the number of combination is the product of choices in each category This is basically what we call the Fundamental Counting Principle Unfortunately not all trees are uniformly branching as we will see in the next several examples and it is very important to find out the conditions that guarantee a uniformly branching tree without us drawing the tree Fundamental Counting Principle If an experiment E can be decomposed into 2 stages E1 and E2 such that i the number of outcomes in E2 is independent of the outcome of E1 ii different outcomes in E1 will give rise to different outcomes in the whole experiment E then the number of outcomes in E is equal to the product of those in E1 and E2 The above statement is difficult to understand because it has to be precise and concise but it will make much more sense if we look at its interpretations in the previous two examples An experiment is simply the activity that we do in a particular scenario The outcomes are the choices that we have In the first example the experiment is to make ice cream sundae There are clearly two stages the first stage is choosing the flavor while the second stage is choosing the topping …