Appendix A Some elementary countingproblems
Suppose you haveNdistinguishable objects.
1.In how many different ordered sequences can they be arranged?
The answer isN!
The explanation is not hard, but in this case as always the reader is encouraged to
test the resultwithafew simple examples (e.g.tryarrangingthree objects, A, B and
C, and identifythe 3! = 6 arrangements). Ingeneralyou should convinceyourself that
in first position in the sequence there areNchoices of object; in second place (having
madethefirst-place choice) there areN−1; andso on, until for theNthplace thereis
just one object left to choose. Hence the required result isN×(N− 1 )×(N− 2 )...1,
i.e.N!.
2.In how manyways can theNobjects be split up into two piles, ordering within the
pilesbeing unimportant? The first pile is to containnobjects andthe secondm.
The answerisobviously zero, unlessn+m=N.Ifthe numbersdoaddup, then the
answerisN!/(n!×m!).
The zero answer may seem trivial, but it is analogous to the requirements of getting
the totalnumber ofparticles rightin a statisticaldistribution. There are severalways
ofseeingthe correct answer, ofwhichoneisasfollows. Callthe requirednumbert.
We can recognize that theN! arrangements (problem 1) can be partitioned so that the
firstnplacedobjects are putinto thefirst pile, andthe remainingmplacedobjectsinto
the secondpile. However, theseN!arrangements will not allgive distinct answers to
the present question, since the order within each pile is unimportant.
Hence, we can see that
N!=t×n!×m! (A.1)where then!andm!factors allowfor thisdisordering(againusingthe resultof
problem 1). Again convince yourself with a small-number example.
Beforeleaving the problem,itisimportant to recognize thatitisidenticalto
thebinomialtheoremquestion: whatisthe coefficient ofxnymintheexpansion of
181