New version page

UIUC ECE 307 - Review of Combinatorial Analysis

Documents in this Course
Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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


View Full Document
Download Review of Combinatorial Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Review of Combinatorial Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Review of Combinatorial Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?