Homework 8 (assigned August 10, due August 16)

Reading: Rosen chapter 5, sections 5.1–5.5.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. The letters ABCDE are to be used to form strings of length 3.
   • How many strings can be formed if we allow repetitions?
   • How many strings can be formed if we do not allow repetitions?
   • How many strings begin with A if repetitions are not allowed?
   • How many strings do not contain the letter A if repetitions are not allowed?
   • How many strings contain the letter A if repetitions are allowed?

2. A coin is flipped 10 times. An outcome is a list of 10 H's and T's that gives the result of each of the 10 tosses. For example, the outcome
   H   H   T   H   T   H   H   H   T   H   H  
   represents 10 tosses where a head was obtained on the first two tosses, a tail was obtained on the third toss, a head was obtained on the fourth toss, etc.
   • Count the number of possible outcomes.
   • How many outcomes have exactly 3 heads?
   • How many outcomes have at most 3 heads?
   • How many outcomes have a head on the fifth toss?

3. In how many ways can 10 (distinct) adults and 5 (distinct) children stand in a line so that no 2 children are next to each other? In how many ways can they they stand in a circle so that no 2 children are next to each other?

4. A computer network consists of 6 computers. Each computer is directly connected to at least one of the other computers. Prove that there are at least 2 computers in the network that are directly connected to the same number of other computers.

5. Find the number of ways to arrange the letters in each of the following words. Assume all letters are lowercase.
   • indiscrete
   • paradoxical
   • ramanujan

6. In how many ways can 12 books be placed on 4 distinguishable (i.e., labeled) shelves
   • if the books are indistinguishable copies of the same title?
   • if no 2 books are the same, and the positions of the books on the shelves matter?

Assigned problems (to be handed in):

1. How many ways are there for a horse race with 4 horses to finish if ties are possible? Note: Any number of the 4 horses may tie. Show your work. (5 points)

2. Prove: At a party where there are at least 2 people, there are two people who know the same number of other people there. (5 points)

3. A poker hand consists of 5 cards from a standard 52-card deck. In terms of binomial coefficients, count the number of possible poker hands with the given property. Show your work. You can leave your answer as an unevaluated expression. (5 points for each part)
   1. One pair (2 cards of the same rank and no others of equal rank).
   2. Full house (2 cards of the same rank and 3 cards of another rank).
   3. High card (5 different ranks but not a flush and not a straight).
   4. At least 2 cards with the same rank.
   5. No ace, exactly 1 king, and at least 1 heart.
   6. At least 1 card in every suit.

4. Suppose we have 3 different toys to give away.
   1. We want to give them away to 2 girls and 1 boy, 1 toy per child. The children will be selected from 4 boys and 6 girls. How many ways can this be done? Show your work. (4 points)
   2. Suppose again that we want to give them away, 1 toy per child, to 3 children from a pool of 4 boys and 6 girls, but now we require that at least 2 boys get a toy. In how many ways can this be done? Show your work. (6 points)

5. How many solutions are there to the equation
   x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = 29,
   where x₁, x₂, x₃, x₄, x₅, and x₆ are nonnegative integers such that
   1. x_i > 1 for i = 1, 2, 3, 4, 5, 6?
   2. x₁ ≥ 1, x₂ ≥ 2, x₃ ≥ 3, x₄ ≥ 4, x₅ ≥ 5, and x₆ ≥ 6?
   Show your work. (5 points for each part)

6. The following questions investigate the effect of various assumptions on the number of ways of placing n balls into b distinct (i.e., labeled) bins.
   1. Suppose that the n balls are distinct (i.e., each ball is labeled with a different number) and that their order within a bin does not matter. What is the number of ways of placing the balls in the bins?
   2. Suppose that the balls are distinct and that the balls in each bin are ordered. What is the number of ways to place the balls in the bins? (Hint: Consider the number of ways of arranging n distinct balls and b − 1 indistinguishable sticks in a row.)
   3. Suppose the balls are identical (i.e., unlabeled), and hence their order within a bin does not matter. What is the number of ways to place the balls in the bins? (Hint: Of the arrangements in part (2), how many are repeated if the balls are made identical?)
   4. Suppose that the balls are identical and that no bin may contain more than one ball, so that n ≤ b. What is the number of ways of placing the balls in the bins?
   5. Suppose that the balls are identical and that no bin may be left empty. Assuming that n ≥ b, what is the number of ways of placing the balls in the bins?
   Show your work. (5 points for each part)