COT3100 Summer’2001Recitation 05/10Combinatorics.1. Consider a set of five distinct computer science books, three distinct math books, and two distinct art books. a) In how many ways can these books be arranged on a shelf?10!b) In how many ways can these books be arranged on a shelf if all five computer science books are on the left and both art books are on the right?5!3!2!In how many ways can these books be arranged on a shelf if all books of the same discipline are grouped together?5!3!2!3!c) In how many ways can these books be arranged on a shelf if the two art books are not together? There are 9! arrangements where two art books are together. Then there are (10!-29!) arrangements where two art books are not together. ( 9! arrangements for each of two permutations of two art books).Ans: 8 9!2. a) How many integers should be selected from the first 10 positive integers (1, 2, …10) to ensure that there exists a pair of these integers with the sum equal 11?6 b) How many integers should be selected from the first 10 positive integers to ensure that there exist at least two pairs of these integers with the sum equal 11?73. A club has 25 members. a) In how many ways the four members can be chosen to serve on an executive committee?C (25, 4) = 25!/(21!4!)b) How many ways are there to choose a president, vice president, secretary and treasurer?P(25,4) = 252423224. How many strings of six lowercase letters from the English alphabet contain a) the letter a (at least one) and any other letters may be used any number of times?266-256b) the letters a and b in consecutive positions with a preceding b, with all the letters distinct?242322215You can represent the result as a two step task. First you select four letters in addition to a and b. Since each letter can be used only once you have 24232221 ways to performthis. The second step is to insert an ab tag. You have 5 slots to do this. By the product rulethe final answer is the product of these two numbers.d) the letters a and b, where a is somewhere to the left of b in the string, with all letters distinct? 24232221151Let’s consider a two-step task again. First arrange four letters out of 24, and this step can be performed in 24232221 different ways. The second step is to insert a and b in 5 slots between four other letters. Since a must come to the left of b, you performthis task in 5+4+3+2+1 different ways. By the product rule the answer is 24232221155. Suppose a 5-card poker hand is drawn from the 52-card deck.a) How many hands contain three cards of one kind and two cards of a second kind?15646=3744.Consider any outcome as the three-step procedure. First, there are P(13, 2)=1312=156 ways to select two different kinds out of 13, the kind of the three cards and the kind of two cards. After this you have C(4,3)=4 choices for the suites of 3 cards of one kind. And finally, suites for the two cards of the same kind can be selected in C(4, 2)=6 different ways. The answer is 15646=3744.b) How many hands contain all five cards of different kind (any suit)?128745= 1,317,888.Let’s first select five different kinds of cards out of 13 available. This task can be done in C(13, 5)=13!/(8!5!)=1287 ways. Then we have four choices for the suit of each card, i. e. there are 45 choices to perform the second step. The answer is 128745= 1,317,888.c) A flush is a hand when all cards have the same suit. How many five-card flushes are possible?Ans: 4131211109/5!=5,148C(13,5) ways to choose 5 cards from 13 with the same suit. It should be multiplied by 4 different ways to choose a suit.d) A straight is a hand with five consecutive cards. How many five-card straights are there?945.There are 9 ways to select five consecutive cards. Each card can have four suits, so there are 45 choices for suits.e) How many 5-card straight flushes are there? 364 choices for a suit and 9 choices for the 5 consecutive cards from
View Full Document