CMSC 250 Fall 2004 -- Homework 11

Due Wed., Nov. 17 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Solve each of the following giving the formula used, explanation in English of why that formula was used and the answer (only needs to be taken to a fomula that involves exponents, factorial, addition, subtraction, multiplication and/or division).
   1. A farmer with 7 cows likes to milk them in a different order each morning. How many days can he do this before he has to repeat an order already used?
   2. A man has 5 sport coats, 4 pair of slacks, 6 shirts and 1 tie. How many different outfits can he make if an outfit must at least consist of a pants and shirt? (He does not care about matching, and notice coat and tie are optional.)
   3. A dinner special for 4 at a Chinese restaurant allows one shrimp dish (from 3), one beef dish (from 5), one chicken dish (from 4) and one pork dish (from 4). Each individual diner can also choose either soup or an egg roll. Assuming a group of 4 diners has come in and agreed on the items in the special, how many different orders could be sent from the kitchen?
   4. You are the judge in a child's costume contest. You want to make sure everyone gets a prize. There are 21 contestants. You develop 7 categories and give out first, second and third place prizes in each category. You can assume that each child gets one and only one prize.
      1. Assuming every prize is different, how many different ways can the 21 prizes be given to the 21 children?
      2. Assume you take pictures of the winners in each category (this would be 7 pictures with 3 people in each picture). You do not indicate who won first second or third place - it is just a picture of which of the 7 categories the children are in, how many different ways can they be placed into those 7 categories?
      3. Assuming the prizes handed out for first place are all the same, the prizes for second place are the same and the prizes for third place are all the same, how many different ways can children leave with their prizes?
      CONTINUED ON THE OTHER SIDE
   5. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants and broccoli croissants. Assume the shop has as many of each of these type as you need to answer the questions below. How many ways are there to choose
      1. a dozen croissants?
      2. three dozen croissants?
      3. two dozen crossants with at least two of each kind?
      4. two dozen croissants with no more than two broccoli croissants?
      5. two dozen croissants with at least one plain, at least two cherry, at least three chocolate, at least one almond and at least two apple, and no more than one broccoli croissants?
   6. The following questions are all about a standard deck of 52 playing cards.
      1. Assuming you are planning to deal the entire deck of 52 cards to 4 players so that each player gets 13 cards randomly, how many ways could these cards be distributed to 4 distinguishable players?
      2. If you deal all of the cards randomly to 4 players so that each player gets 13 cards, what is the probability that each and every player will have 13 cards that are all of the same suit?
      3. If you deal all of the cards randomly to 4 players so that each player gets 13 cards, what is the probability that each and every player has exactly one ace?
   7. There are 10 questions on a discrete math exam. How many ways are there to assign scores to the problems if the sum of the scores is 100 and each question is worth at least five points?
2. Let $m$ be any nonnegative integer. Use mathematical induction and Pascal's formula to prove that for all integers $n\geq 0$,
   
   $${m\choose 0}+{m+1\choose 1}+\cdots+{m+n\choose n} = {m+n+1 \choose n}.$$
   
   

3. Express each of the sums in closed form (without using a summation symbol and without using an ellipsis $\cdots$).
   1. $$\sum_{i=0}^m {m\choose i} 4^i$$
   2. $$\sum_{k=0}^n (-1)^k{n\choose k} 3^{2n-2k}2^{2k}$$

Web Accessibility