ECE 307 – Techniques for Engineering Decisions Lecture 9. Review of Combinatorial AnalysisCOMBINATORIAL ANALYSISBASIC PRINCIPLE OF COUNTINGBASIC PRINCIPLE OF COUNTINGEXAMPLE 1: PAIR FORMATIONGENERALIZED VERSION OF THE BASIC PRINCIPLE GENERALIZED VERSION OF THE BASIC PRINCIPLEEXAMPLE 2: SUBCOMMITTEE CHOICES EXAMPLE 3: LICENSE PLATE EXAMPLE 4: n POINTSPERMUTATIONSPERMUTATIONS EXAMPLE 5: BASEBALLEXAMPLE 6: CLASSROOMEXAMPLE 7: BOOKSEXAMPLE 8: BOOKS EXAMPLE 9: PEPPEREXAMPLE 9: PEPPERGENERAL STATEMENTEXAMPLE 9: COLORED BALLSCOMBINATIONSCOMBINATIONSGENERAL STATEMENT ON COMBINATIONSBINOMIAL COEFFICIENTSEXAMPLE 10: COMMITTEE SELECTIONEXAMPLE 11: GROUP FORMATIONGENERAL COMBINATORIAL IDENTITYMULTINOMIAL COEFFICIENTSMULTINOMIAL COEFFICIENTSMULTINOMIAL COEFFICIENTSMULTINOMIAL COEFFICIENTSEXAMPLE 12: POLICEEXAMPLE 13: TEAM FORMATIONEXAMPLE 13: TEAM FORMATIONEXAMPLE 14: TEA PARTY© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 1ECE 307 – Techniques for Engineering DecisionsLecture 9. Review of Combinatorial AnalysisGeorge GrossDepartment of Electrical and Computer EngineeringUniversity of Illinois at Urbana-Champaign© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 2 Many problems in probability theory may be solved by simply counting the number of ways a certain event may occur We review some basic aspects of combinatorial analysis combinations permutationsCOMBINATORIAL ANALYSIS© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 3BASIC PRINCIPLE OF COUNTING Suppose that two experiments are to be performed:  experiment 1 may result in any one of the mpossible outcomes for each outcome of experiment 1, there exist n possible outcomes of experiment 2 Therefore, there are mn possible outcomes of the two experiments© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 4BASIC PRINCIPLE OF COUNTING The basic approach to prove this statement is via exhaustive enumeration: the set of outcomes for the two experiments is listed as:(1, 1), (1, 2), (1, 3), (1, n) ;(2, 1), (2, 2), (2, 3), (2, n) ;(m, 1), (m, 2), (m, 3), (m, n) with (i , j) denoting outcome i in experiment 1and outcome j in experiment 2© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 5EXAMPLE 1: PAIR FORMATION We need to form pairs of 1 boy and 1 girl by choosing from a group of 7 boys and 9 girls There exist a total of (7)(9) = 63 possible pairs since there are 7 ways to pick a boy and 9 ways to pick a girl© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 6GENERALIZED VERSION OF THE BASIC PRINCIPLE  For r experiments with the first experiment having n1possible outcomes; for every outcome of the first experiment, there are n2possible outcomes for the second experiment, and so on1222. . . . . . .. . . . . . .. . . . . . .21n1...© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 7 There arepossible outcomes for all the r experiments, i.e.,there are possible branches in the illustration – high dimensionality even for a moderately small number r of experimentsGENERALIZED VERSION OF THE BASIC PRINCIPLE1231...ririn nnn n==⋅⋅⋅⋅Π 1riin=Π© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 8EXAMPLE 2: SUBCOMMITTEE CHOICES The executive committee of an Engineering Open House function consists of: 3 first year students 4 sophomores 5 juniors 2 seniors We need to form a subcommittee of 4 with each year represented:3 4 5 2 120⋅⋅⋅= different sub -committees are possible© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 9EXAMPLE 3: LICENSE PLATE We consider possible combinations for a six-place license plate with the first three places consisting of letters and the last three places of numbers Number of combinations with repeats allowed is(26) (26) (26) (10) (10) (10) = 17,576,000 Combination number if no repetition allowed is(26) (25) (24) (10) (9) (8) = 11,232,000© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 10EXAMPLE 4: n POINTS Consider n points at which we evaluate the function Therefore, there are 2npossible function values( ) { ,1 } , 1,2, ... ,fi 0 i n∈=© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 11PERMUTATIONS A set of 3 objects { A, B, C } may be arranged in 6different ways:  Each arrangement is called a permutation The total number of permutations is derived from the basic principle: there are 3 ways to pick the first element there are 2 ways to pick the second element there is 1 way to pick the third elementBCA ABC CBABAC ACB CAB© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 12PERMUTATIONS Therefore, there are = 6 ways to arrange the 3 elements In general, a set of n objects can be arranged into n! = n ( n – 1 ) ( n – 2 ) . . . 1different permutations321 6⋅⋅ =n nn n! ( 1)( 2) ... 1=−−© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 13EXAMPLE 5: BASEBALL Number of possible batting orders for a baseball team with nine members is9! = 362,880 Suppose that the team, however, has altogether 12 members; the number of possible batting orders is the product of the number of team formations and the number of permutations is9! 362,880=© 2006 – 2021 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved. 14EXAMPLE 6: CLASSROOM A class with 6 boys and 4 girls is ranked in terms of weight; assume