Computer Science > QUESTIONS & ANSWERS > University of California, Berkeley - CS 70FA19hw08sol CS 70 Discrete Mathematics and Probability The (All)

University of California, Berkeley - CS 70FA19hw08sol CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 8 ALL SOLUTIONS CORRECT

Document Content and Description Below

CS 70 Discrete Mathematics and Probability Theory Fall 2019 Alistair Sinclair and Yun S. Song HW 8 Note: This homework consists of two parts. The first part (questions 1-6) will be graded and will ... determine your score for this homework. The second part (questions 7-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare. For each problem, justify all your answers unless otherwise specified. Part 1: Required Problems 1 Captain Combinatorial Please provide combinatorial proofs for the following identities. (a) !ni" = !n!n i". (b) Ân i=1 i!ni" = n2n!1. (c) Ân i=1 i!ni"2 = n!2nn!!11". (Hint: Part (a) might be useful.) (d) Ân i=0 !ni"Ânj=!0i !n!j i" = 3n. (Hint: consider the number of ways of splitting n elements into 3 groups.) Solution: (a) Choosing i players out of n to play on a team is the same as choosing n!i players to not play on the team, i.e. !ni" = !n!n i". (b) For each i on the LHS, we can think of selecting a team of i members out of a pool of n players, and susequently choosing a captain out of the i team members. The RHS does the same by first choosing the captain out of the n players, and then a subset of the remaining n!1 players to constitute the team. (c) Assume we have n women and n men. Using part (a) we can rewrite the LHS as Ân i=1 i!ni"!n!n i", which we can interpret as selecting a team of n players by choosing i women and n!i men, and then choosing one of the women to serve as captain. Again, the RHS first chooses a captain, and then selects a remaining n ! 1 players from all remaining men and women to form the team. CS 70, Fall 2019, HW 8 [Show More]

Last updated: 2 years ago

Preview 1 out of 10 pages

Buy Now

Instant download

We Accept: