Fundamental Principle of Counting: In a tw o-step process: if there are m w ays to do step1 and n w ays t o do step 2 (regardless ofwhat w as done in step 1), t hen there are mCn w ays t o do t he process.But sometimes the difficult y is t o see the st eps.THE HANDSHAKE PROBLEM. If there are 20 people at a part y, and ev ery person m ust shakehands with every other person at the party, how many handshakes are necessary? (Ans: 1 90 )ONE APPROACH to an answ er: Just t ry it! (But start small... )People # of handshakes required. 1 0 (NONE) A There is no one w ith w hom t o shake hands! 2 1 A B Draw a line betw een A & B to represent the req uir ed han dsh ake.A B Here w e show t he h and shake b et w een A & B. 3 1+ C Add (draw in) the new handshakes required when Cjoins the party. Add the required number to theone already show n in t he t able.A B The t hr ee han dshak es required am ong A , B & C 4 3+ are represented by t he lines shown. Add (draw ) C Dthe new handshakes required when D walks in!Add t he required number t o the table.Predict the number of handshakes required ifthere are 5 party-goers. A B 5 + Here we show the handshakes required f or 4 persons. C D Coun t them, and v erif y y our conclus ion abov e. E Draw t he new handshak es required w hen a fifth person,E, joins the par y. Enter the t ot al in the t able.Carry on.... (Colored pencils can be usef ul here. ) 6 + C C C C C C 7 + C C C C C C C 8 + C C C C C C C C n ?(See nex t page. )Rs07A SECOND LOOK at t he question: CAHere’s another way t o think about it :We have n noncollinear point s (for example n= 9, 9 point s) C CBStart counting w ith t he point A; how many segmentsC CC are needed t o c onnec t t o eac h of t he ot her poin t s? How many segments are needed to connect B C C w it h each of the remaining (not A) point s? C CContinue w ith t he remaining point s. Add up t he segments t hat w ere needed.* non collinear (no 3 in a l ine)A THIRD LOOK.. .(This may be the most eff icient w ay to arrive at the tot al.)Let’ s say there are three people at t he party, A, B & C.The num ber o f hand shak es requir ed (so that ever yo ne shakes hands wit h everyone else) is thesame as the number of w ays to select a pair of persons to shake hands. One can reason thatthere are 3 w ays to select t he first person (A or B or C) and, once that person is selected, 2ways to select t he second person. By t he Fundament al Principle o f Coun ting , t he t ot al nu mberof w ays t o select the pair is 3C2. However, that assumes that the order in which t hey wereselected makes a difference! (And t he order does not make a dif f erenc e.) Here t hey are:Select person 1 Select person 2 Who shakes hands … …A B A with BC A with CB A B with AC B with CC A C with AB C with BAs stated above, the ord er do es not make a dif f erenc e; for inst ance, if A shakes han ds w it h B,then B shakes hands w it h A , so t he t hir d ou t come list ed is the sam e as t he f irst . Likew ise, “ A w it h C” is t he sam e hand shak e as “ C w it h A ” , and shoul d no t be count ed t w ice.Finally , “ B w it h C” is t he same handshak e as “ C w it h B” , an d shoul d not be coun t ed t w ice.In fact, every handshake that should have been counted was counted tw ice by our method.Thus t he correct number of handshakes among t hree persons is (3C2)'2.This same method, corrected by dividing by 2 so as to not count t he handshakes tw ice, predictsthat for n individuals, the number of handshake pairs is n(n!1)))))) 2Check that t his “ formula” agrees wit h the results in your t able (see page 1).Thi s is also called t he nu mber of combinat ion s of n t hin gs t aken 2 at a t ime.