Basic Counting Rules
Fred Roberts, Barry Tesman · 2009
Chapter Basic Counting Rules THE PRODUCT RULE Some basic counting rules underlie all of combinatorics We summarize them in this chapter The reader who is already familiar with these rules may wish to review them rather quickly This chapter also introduces a widely used tool for proving that a certain kind of arrangement or pattern exists In reading this chapter the reader already familiar with counting may wish to concentrate on the variety of applications that may not be as familiar many of which are returned to in later chapters Example Bit Strings and Binary Codes Example Revisited Let us return to our binary code example Example and ask again how many letters of the alphabet can be encoded if there are exactly bits Let us get the answer by drawing a tree diagram We do that in Figure There are possible strings of bits as we noted before The reader will observe that there are choices for the rst bit and for each of these choices there are choices for the second bit and is Example DNA The total of all the genetic information of an organism is its genome It is convenient to think of the genome as one long deoxyribonucleic acid DNA molecule The genome is actually made up of pieces of DNA representing the individual chromosomes The DNA or chromosomes is composed of a string of building blocks known as nucleotides The genome size can be expressed in terms of the total number of nucleotides Since DNA is actually doublestranded with the two strands held together by virtue of pairings between specic bases a base being one of the three subcomponents of a nucleotide genome sizes are usually Barry A Tesman First Second String Figure A tree diagram for counting the number of bit strings of length expressed in terms of base pairs bp Each base in a nucleotide is one of four possible chemicals thymine T cytosine C adenine A guanine G The sequence of bases encodes certain genetic information In particular it determines long chains of amino acids which are known as proteins There are basic amino acids A sequence of bases in a DNA molecule will encode one such amino acid How long does a string of a DNA molecule have to be for there to be enough possible bases to encode dierent amino acids For example can a element DNA sequence encode for the dierent basic amino acids To answer this we need to ask How many element DNA sequences are there The answer to this question is again given by a tree diagram as shown in Figure We see that there are possible element DNA sequences There are choices for the rst element and for each of these choices there are choices for the second element the reader will notice that is Notice that there are not enough element sequences to encode for all dierent basic amino acids In fact a sequence of elements does the encoding in practice A simple counting procedure has shown why at least elements are needed The two examples given above illustrate the following basic rule PRODUCT RULE If something can happen in and how the rst a second can happen in the two together can happen in if something can happen in and how the rst a second can happen in and how the rst two happen a can happen in and all the together can happen in to bit strings we see the rule that the number of strings of exactly bits is given by there are two choices two choices for T T T T T C C C C C First Second A A A A A Figure A tree diagram for counting the number of element DNA sequences the second bit and how the rst bits are there are two choices for the in the of Example if there are choices of size for each of there are dierent possible If there are there are dierent possible that by our in Chapter it is in to the number of possible by them all of Some of counting is needed The rule such a In the of this we be with such simple of counting that A is a of a and is a of the number of to one A and one is a This is a of the rule To one example the number of element DNA sequences is is why there are enough dierent element sequences to encode for all for the The of DNA for and size of possible base pairs sequences amino is dierent the in code strings of up to bits are to encode for all letters of the alphabet not possible string is In we which element sequences encode for the amino acid with DNA we see that the number of sequences of bases is the number with bases is How long is a DNA molecule Some are given in Notice that in the genome has bases or base the number of such sequences is which is This number is by or It is a number that is to for a simple counting of all we can the possible in genetic It is not at all given the number of possible DNA sequences that there is such an variety in and that two are the It be noted that given the of the number of it not have possible to these by the simple of It to rules or for counting which the number of is one of the three basic in for counting as the number of DNA sequences is it has in and Figure A of dierent A is a of DNA that the code for a particular the genome each of its it the of the bases up each In this each with a or For on the of in and the genome see and of the and and or Example one a number given by a sequence of two letters by How many dierent there the rule one is to the answer the is it a answer for two letters on the on the to the The reader wish to a A of one is given in Figure There are three letters on all that and have letters A and C and and There in dierent The number of dierent there a such In the and to with the that of the rst two be or The number of by a The code not with a or and it to have or in the these we that the number of possible Bit string T enough to To to a as an for This up the that an code have a or in the The number of to the that with the there are on the there are possible to at a will we do are not enough Example Let be the of all bit strings of length A of is a that to each bit string of length a number or For and T on are given in The of a of a usually a of certain A a of two three or four can be in by an of to an for a given a to have a that for an this at rst to be an For how many of are there There are elements in the by a of Example by the rule there are dierent there are terms in the In total there are dierent the number of such for is and the number by of we can certain as as is we need not the for we need do it for enough that is to one of for which we have the the rst being a of at all possible of and which to one of In Chapter we how to such as this a to For a of see and or Example a who a are of the and It is not if the of one of these or a of them together The the to dierent of these to see there is a How many dierent be Each can be or there are possible In there are possible of on these four each possible of can an or Each individual to of these to a is if there are in the is if there is in the is if there is in the is if there are in the For a who an are in the or and are in the the which has and on In it is to the of a on all possible bit strings if the number of is there are many possible bit the is to to the of a that is There is on this for example and and and or in of a given a of certain we have to this in Example and in a to in an with an as a certain pattern of or and in the pattern of to an and in it does For applications see The of is If each has three is it that there be at least two with the a of answer to reader In the in Chapter each can be to of not exactly the there are at the of the chapter an is which does not of the of the To a one it does not as as it A has and the to encode each a code of letters by there enough to encode all with dierent a with of Chapter the number of strings of length at in a code for length at for length exactly with a or In our of that we the on code as in Example that we the number it to be number with the that of the rst three can be or How many are there How many are there code If we to bit strings of length at to encode not all letters of the alphabet also all is the number that is for code How many are there each of is or A has to have at least one It can at one at one at one at one and at two How many possible are there if we two and the for the and two the if have the number of of each answer How many the all of If a or to each of how many such are there A is if the of a bit string is and are For the of is the T of that is not How many of are there and In an or is by bit strings of length The bit in the string the and the rst bits are used to encode the is the number of that can be in this for a given if be one of these The of is or and can be in the a a and are The for an a bit string of length to an by the rst bits to encode a and the bits to encode with the two as in a is the number of that can be the for a given a if the is in such a that the bit for encoding the number a is a if be on applications it can be on that certain of can be to and who have of that a a How many dierent applications are possible these How many of are possible these THE RULE We to the second counting the following example Example There are and of the of A is being to see the In how many dierent can such a be if it of one and one The answer by the rule is if the is to of one of the or one of the there are possible This the second basic rule of counting the rule RULE If one can in and a second in dierent there are in which the rst or the second can not if one can in a second can in dierent a can in dierent there are in which exactly one of the can In Example we have the and and usually the rule or the rule is The rule Example A has two choices to and has the to and To a and there are by the How many are there to two if can a and and or and There are by of the There are of the second why and of the by the rule the number of of the two dierent is Example in and The for to in of be a a by a or a by a that is one of the How many dierent possible the rule there and of the two the rule there in all The need for one for For example the in has to Each can be a or an a or a that the rst be a the rule we see that the number of possible is for the rst which has by the and rules we see that the number of is This for enough In this us the rule this that A and are and we wish to exactly one element it A or the number of to this element is the number of elements in A the number of elements in How many bit strings have length or A is to be and If the is to have two of dierent how many such are there The of the rst in the is there are at least on the of in the see are there which have each being a number in and all or all Each has a number for If each can be number between and are there enough dierent for there be if the or How many with or do not have the In how many can we get a of or a of two are that a is to have For each there are choices The may be one of sizes and one of How many dierent are there How many DNA chains of length have at all or have in the rst In we of It is convenient to these A of an is an arrangement of the elements of the in It is to the number of of an Example and are for In how many dierent can be We can all possible as We see that there are possible we can observe that there are choices for the rst being For each of these choices there are choices for the second For each of these choices there is for the by the rule the number of possible is Each is a We are for the number of of a the of and If there are to be counting the number of possible can be by that is rather It is to that there are for the rst for the second and on in of for to possible in all The of Example to us the following The number of of an is given by In Example we the number of in which to dierent This is the as the number of of a it is To see again why counting by we in the of for of The number to an example is already that it is To see this that A second a to at In of the above there are it is to all of an In we an for The number can be by The of by is To see how the is that it as and as these with the in The of the is by the fact that the of to as the the as For a see an such as all of a To see why that there are in a a second can in a the number of to is How many of with How many of with and with and it to if a How many of with an number a How many of have in the second How many of have in the second and in the are there to of dierent if the one be rst and the one a In a the are on the and the are on the A is a of the to in which and are How many possible are there which with a for a have for to in the and to in the In how many dierent can the be answer to the of dierent in which the can be if all to in the We have already that not all of can be on the at least not by that a an for a such a we to if the will in a of and will a or of or The or a on the To how a is to we to a or a This is a that the in terms of or as a of the size of the For we ask how many are to two of and This number of is the of a particular on a particular will with the of the and the of the there is a in on of rather and on of the of an of the particular or used to the The to of is a Example The A to dierent and at the rst does not in which the does is to the total of that the of to is The is to an for the the of a is the of the for used in the This is a For the we be with the all possible and the of each We to the of this is the size of the that is the number of We that a and its is for each and of and at to a of the there are such of We have already shown that this number can be is and is we that is that it is to this by We return to the in It is to that the in many to of the in which this has in Example The has many Each a to to information and In the be in to This in at many of the rst to a to it in the of in Example The a each in a be and the In that be in to Example The of in an The of the will have by a a with of in and in for of of of and on Each is by and In the the in to the The to be to a and and Example A of In we a a sequence of There is a in terms of and for one How do we this and Example In many there are a number of that be or that be there is a certain we can a in terms of or or of the for the this is and it is of the or of In the be to total For on this see Example and Example in In and see the to the up that It and a the or in which to to a For information this see The is an example of a that has the of to a it to a of known as or for which it is there will be a in a of the We return to this in we and an to be a if its is by a in an is a a Example a A has to Each certain such as a a number of and an of We to the as a to the The of the the to the has a with it For if two a it to them The to the total with the The of each does not with dierent of the The that are the the to an in which to the such that the total The is a of of the in the have The of the in of a in a For a the of the see also the are in many in We them in Example and in the the of all possible of the is for it has a of and not a of this and the are by for one of these is an for the It is one of the for to that we can one and have that are to a number of which on the dierent Example a In we do not exactly how long a will For the of a of and the of a particular in to that it is possible that the in question will be rst in the in the the will be on the The of the possible is used as a of the be to the of is the of a the that all are this is by the of each up these and by the number of In our example the is to that all are to be the of a for the of the of the is given by a for this we have In we the of binary for and that the of a with a given can be by a binary tree If a a second how many it to the of Example by if is If a a second of how many it to the by if the in a in the of in for in Each which is or rst and we to the that the number of rst is as as possible that we this by all possible and for each we the number of rst is the of this procedure an the number of to the number of rst that there are in a and we wish to each of them not in two the of a for an of that the total the by if and the is given in the following C C A the of Example if and the of the to the is given by A that it to each in a If there are and we them in we the one a the the if it to each that is a of bit strings of length that A is an which determines given a bit string of length or not it is in that A to an answer A has the and that of all bit strings of the is in For if the following for given a bit string of length or not it is in First if is of the This is to for the of that it to answer this question If is not of the and that is not in If is of the if the rst of a bit string in a the of the of that not be a an that we to elements and them in an arrangement is an of the will the number of of an For example the number of letters can be by that we to dierent letters of and them in we if a has to and in which to them each one to the number of dierent can for is that if There are of an in this In it will usually be that To see how to us that in the of the there are choices for the rst for each of these there are choices for the second and for each of these there are choices for the by the rule In the of the we have choices for the rst for the second for the and for the us the if If this can be as we the We have the It for as Example We a with many In particular the has for which it in that If we have in our how many dierent can we the for our There are choices for the rst choices for the second choices for the choices for the and choices for the us we see again that a Let A a the number of sequences of length elements of A a if element of A is to be used a if the rst element of the sequence is a if the rst element of the sequence is and element of A is used Let A a the number of sequences of length elements of A a if is a if the rst in the sequence is a if the rst is and the is and letters are In how many dierent can we the rst if we need to with If a has four how many dierent are there with a If the rst be If the rst be and the second be A or has on its to It by its each at specic How many dierent can a In we will see that the is not with to Example The A that it of The is the it is possible to have on a a of of the following the the in its We be to answer this question with simple applications of the rule To answer the question in Example us the Let us ask how many there are of this The answer can be by and we that there are such The answer can also be the We think of building up a in First we think of element a or There are we element or There are again choices we element or There are again The total number of of building up the is by the rule the number of of a is and the number of of an is these with the We can think of a particular as a of the of we can think for each of it or we see that there are possible the has not the of A with A may number of them The is to its procedure and to a dierent number to two dierent to exactly the How needed If the of Example to and on its how many dierent can the that the of Example a possible that each have or have How many possible of does the If A is a of elements how many does A have If A is a of elements how many of one element does A have A on a A or to each of A a If A has elements how many dierent are there on A if A has elements In a simple see of is as or a If there is on this how many simple are there with of an is a of elements the which that does not an is an will the number of of an For example the number of to a of a of is given by If the are and the possible are We simple that is if There are of an in this will usually be It is in all of the in this arrangement of of can be by rst can be in and them can be in The by the For an see The number is by and a This is as we see this number in the see the that In we and one of the with a The can be to the or not to There are to do the this is to of the There are to do the this is to of the the rule the This can be as a on counting This can also be by Second of Let us applications of our and our basic rules In the Example the number of with exactly dierent is C The number of with at dierent is by the rule C C C C If we have being in an and we to of them to to a particular the number of in which we can do this is C If there are possible and a the number of we can the is C The number of a of is The number of the is C The number of to the of and is C C The number of bit strings with and is C C To see why think of and of them to be or of them to be A convenient of the is to the shown in Figure The number in the Each element in a given is by the two elements in the above it which are to the and to the For example C is given by up the and which are in Figure The of Figure is the and one of the of and many does The answer is that it on the This is exactly the that in The is an example of a We see many such later in the in Chapter which is to this such one to of to and the of these in How many are there to of a of How many can be a of a C C C C and answer by Figure The are to C by that a C C Figure by one C and and that for C and C a In how many can be to be to dierent for if there are in each that the are In how many can be to be to dierent for if there are in each that the are In how many can the be if there is at least in each that the are A is possible and its to at of them In how many can the the to be a In how many can be to be to dierent for if there are in each In how many can the be if there is at least in each How many with letters can be the letters of the alphabet if each or How many between and have A is to be a of dierent and dierent How many are there to the if The can be size it have of and The has and of them be a The has of each kind and a and be in the a A has dierent to of them the and the The are and are the the number of possible for the if There are The be The be and the be The that the of a to a is the of a to a is and there is to to or to is the least in which to the a if the are all each and are the A certain has in the and in the A of and is to be How many are there to the if a It at least of of each It at least of the a this an this a an of by the of How the