文档介绍：2016-11-27Discrete MathematicsDiscrete MathematicsShandong University Qilu Software College2016-11-27鸬鹚lú cí2016-11-27计数问题?AB2016-11-27计数问题?十进制数串中有偶数个0的数串个数。。。。2016-11-27Chapter 3Counting2016-11-27§ The basics of counting (1) Basic counting principlesDefinition:Suppose that a procedure can be broken down into a sequence of two there are n1 ways to do the first task and n2 ways to do the second task after the first task has been done,then there are n1?n2 ways to do the procedure. (1)The product rule2016-11-27§ The basics of counting (2)…n1:ways to do T1…n2:ways to do T2……………n1*n2: ways to do the procedure 2016-11-27§ The basics of counting (3) Basic counting principles An extended version of the product rule:Suppose that a procedure is carried out by performing the tasks T1,T2,…,Tm in task Ti can be done in ni ways after tasks T1,T2,…,and Ti-1 have been done,then there are n1?n2?…?nm ways to carry out the procedure. (1)The product rule2016-11-27§ The basics of counting (4) Basic counting principles Definition:If a first task can be done in n1 ways and a second task in n2 ways,and if these tasks cannot be done at the same time, then there are n1+n2 ways to do one of these tasks. (2)The sum rule2016-11-27§ The basics of counting (5) Basic counting principles An extended version of the sum rule:Suppose that the tasks T1,T2,…,Tm can be done in n1,n2,…,nm ways,respectively,and no two of this tasks can be done at the same the number of ways to do one of these tasks is n1+n2+…+nm . (2)The sum rule