 聯系方式 您當前位置：首頁 >> OS作業OS作業

日期：2018-09-30 05:55

Problem 1

How many distinct (identical-looking) arrangements of the word COMMANDING are there if:

(a) There are no restrictions other than the normal one that the two 'M's look the same and the two 'N's look

the same?

(b) If you do not change the order of the vowels or consonants?

(c) If you do not change the order of the vowels but consider any order of the consonants?

Hint: Obviously, you will use multinomial coefficients; for (b) and (c) you may use the "unordering principle"

(accounting for duplicate letters) or you may think about replacing vowels with the letter "V" (which

represents the "slot" where a vowels goes, since if vowels must be in order, once you know the locations of

the vowels, you can only put them in the slots in one way); and similarly for consonents (replacing by the

letter "C").

Solution:

In?[?]:

(a): 10!/(1!1!2!1!2!1!1!*1!) = 907200

(b): #vowels:O, A, I

#consonants:C, M, N, D, G

(7!3!)/(2!2!) = 7560

(c): 7!/(2!*2!) = 1260

Problem 2

2018/9/28 hw03

(Circular Permutations) In how many ways can 7 people { A, B, C, D, E, F, G } be seated at a round table if

(a) A and B must not sit next to each other;

(b) C, D, and E must sit together (i.e., no other person can sit between any of these three)?

(c) A and B must sit together, but neither can be seated next to C or D.

Consider each of these separately.

Hint: Conceptually, think of the groups of two or three people as one "multi-person" entity in the overall

circular arrangement. It may help to draw a diagram, fixing a particular person at the top of the circle

(thereby eliminating the duplicates due to rotations).

Solution:

In?[?]:

(a)

(b)#CDE, CED, DCE, DEC, ECD, EDC

6*(4!) = 6*24 = 144

(c)

Problem 3

(Permutations and maybe Combinations) Suppose 2 cards are drawn without replacement from an ordinary

deck of 52 randomly shuffled cards. Find the probability that:

(a) The first card is not a ten of clubs or an ace;

(b) The first card is an ace, but the second is not;

(c) The cards have the same denomination (i.e., both are Aces, both are 2's, both are 3's, etc.);

(d) At least one card is a diamond;

(e) Not more than 1 card is a picture card (Jack, Queen, King).

Solution:

Problem 4

2018/9/28 hw03

(Permutations) We draw 5 cards at random from an ordinary deck of 52 cards (as usual, without

replacement). In this case, we will think of the 5 cards as a sequence.

(a) If the first 2 are spades, what is the probability that the remaining 3 are also spades?

(b) If the first 2 cards are spades, what is the probability that among the remaining 3 cards there will be no

diamonds?

(c) The first two cards drawn are of different suits.

(d) The last two cards drawn are of different suits.

Hint: For (a) and (b) you can do this with conditional probabilities or not. For (d), ask yourself whether

reversing a sequence changes the probabilities.

Solution:

Problem 5

(Permutations with Duplicates) Let K be the number of distinct birthdays among four persons selected

uniformly at random. Assume that all years have 365 days and birthdays are randomly distributed

throughout the year.

(a) What is the probability that K = 1?

(b) What is the probability that K = 3?

(c) What is the probability that K = 4?

(d) What is the probability that K = 2?

Here (not all possibilities, just some examples) is what I mean by distinct birthdays:

"1 distinct birthday": Alice, Bob, Raul, and Yi-Fei were all born on January 1st

"2 distinct birthdays": Alice and Bob were born on Jan 1st, but Raul and Yi-Fei were born on July

23rd;

"2 distinct birthdays": Alice was born on Jan 1st, but Bob, Raul, and Yi-Fei were born on July 23rd;

"3 distinct birthdays": Alice and Bob were born on Jan 1st, Raul was born on July 3rd, and Yi-Fei

was born on Dec 4th

"4 distinct birthdays": All 4 were born on different days.

Hint: It is simpler to think of this as choosing a sequence of k distinct birthdays for k = 1, .., 4, and then

figuring out the number of patterns of shared birthdays; the non-shared birthdays are counted by the original

permutation. The messiest one is K = 2, but is trivial if you do the others first!

Solution:

2018/9/28 hw03

Problem 6

(Combinations and Permutations with Duplicates) In this problem, we have a deck of 52 cards and we

shuffle them randomly and deal the whole deck out to 4 people, so that each player has 13 cards. As usual,

when dealing cards, it is without replacement and the "hand" that each player has is a set.

(a) What is the probability that each player will receive all cards of one suit (i.e., one gets all clubs, another all

hearts, another all diamonds, and another all spades)?

(b) What is the probability that each player will receive exactly three face cards?

Hint: (a) is a simple application of combinations and permutations with duplicates; start with counting the

number of ways of assigning suits to the players. (b) is permutation with duplicates; think of dealing out all

52 cards in a sequence, and then giving the first 13 to the first player, the second 13 to the second player,

and so on. This is the sample space. Then consider how many such arrangements satisfy the constraint.

Solution:

Problem 7

(Combinations -- Poker Probabilities) Suppose you deal a poker hand of 5 cards from a standard deck as

discussed in lecture.

(a) What is the probability of a flush (all the same suit) of all red cards?

(b) What is the probability of a full house where the 3-of-a-kind include two black cards, and the 2-of-a-kind

are not clubs?

(c) What is the probability of a pair, where among the 3 non-paired cards, we have 3 distinct suits?

(d) What is the probability of a pair, where 3 of the 5 cards are black and 2 are red?

Hint: These are straight-forward modifications of the formulae given in lecture, except for (d). For that, think

about the two different parts of the problem, and observe that they are independent (the colors are

independent of the ranks/denominations). You may quote formulae already given in lecture or lab without

attribution and without explaining how to get the formula.

Solution:

2018/9/28 hw03

Problem 8

(Combinations) Consider the following problem: "From an ordinary deck of 52 cards, seven cards are drawn

at random and without replacement. What is the probability that at least one of the cards is a King?" A

student in CS 237 solves this problem as follows: To make sure there is a least one King among the seven

cards drawn, first choose a King; there are C(4,1) possibilities; then choose the other six cards from the 51

cards remaining in the deck, for which there are C(51,6) possibilities. Thus, the solution is C(4,1)*C(51,6) /

C(52,7) = 0.5385.

However, upon testing the problem experimentally, the student finds that the correct answer is somewhat

less, around 0.45.

(a) Calculate the correct answer using the techniques presented in class;

(b) Explain carefully why the student's solution is incorrect.

Hint: The problem with the student's solution is overcounting.

Solution:

Problem 9

(Combinations, Subsets, and Partitions) Suppose you have a committee of 10 people.

(a) How many ways are there to choose a group of 4 people from these 10 if two particular people (say, John

and Dave) can not be in the group together?

(b) How many ways are there to choose a team of 5 people from these 10 with one particular person being

designated Captain and another particular person being designated Co-Captain?

(c) How many ways are there to separate these 10 people into two groups, if no group can have less than 2

people?

(d) How many ways are there to separate these 10 people into two teams of 6 and 4 people?

(e) How many ways are there to separate these 10 people into four groups of 2, 2, 3, and 3 each?

Hint: For (c) -- (e), think about whether or not you are... (wait for it!).... over-counting.

Solution:

Problem 10

2018/9/28 hw03