Category Archives: Homework

Study Guide For Test 3

Posted on by

For your upcoming test:

  • Know how to verbally and mathematically describe a set
  • Know the definition and how to use unions, intersections, and complements
  • Know how to represent set(s) with a Venn diagram
    • Know how to shade the appropriate region of a Venn diagram corresponding to a given set
  • Know how to use the principle of inclusion-exclusion for counting
  • Know how to find the number of objects in a each of the non-overlapping regions of a circle Venn diagram
  • Know how and when to use multiplication in counting
  • Know the definition of C(n,k), and its formula
  • Know Pascal’s Identity: C(n,k) = C(n-1,k) + C(n-1,k-1)
    • C(n,k) counts k-element subsets of the the set {1,2,..,n}. Which of these subsets are counted by C(n-1,k-1) in Pascal’s Identity.
  • You should be able to use Pascal’s triangle to compute various C(n,k)
  • Know when a counting problem involves counting subsets
    • Examples:
      • Selecting balls and putting them in a box
      • Handshakes
      • Number of matches in a league
      • Many many more!
      • n coin tosses with exactly k heads (see Section 5.6)
      • Routes through a city (see Section 5.6)
  • When counting routes in a city (see Section 5.6): Given a route you should be able to write down the subset that corresponds to it.

In general, the best thing to do to study for this test is to review the examples from lecture and homework. The more practice you have, the better you’ll be able to handle the questions on the test!

 

Extra Credit!

Posted on by

I know all of you are thinking: Man! I’m totally going to miss finite math and all of these counting problems over spring break!

Well never fear! Here are some additional practice problems. Hand in these problems 5 minutes before class on Tuesday March 15 (or via email) to receive up to 10 extra credit points toward your quiz grade.

  1. (5 points) Verify that the formula $latex \binom{n}{r}$ satisfies Pascal’s Indentity. In your solution, do not plug in numbers for n and r. (Hint: A small example may be helpful–check out your lecture notes from Tuesday March 1.)

For the next two problems you will use the Binomial Theorem which says:

$latex (x+y)^n = C(n,0)x^n y^0 + C(n,1) x^{n-1}y^1 + C(n,2) x^{n-2}y^2 + \ldots + C(n,n) x^0 y^n$

So for example, $latex (x+y)^3 = x^3y^0 + 3x^2y + 3xy^2 + y^3$.

  1. (2.5 points) Use the Binomial Theorem to show that the number of all subsets of the set {1,2,…,n} is $latex 2^n$. (Hint: problem number 5 from the practice problems for Pascal’s Triangle may be helpful.)
  2. (2.5 points) Use the Binomial Theorem to show that the alternating sum of each row of Pascal’s Triangle is zero. (Hint: problem number 6 from the practice problems for Pascal’s Triangle may be helpful.)

Practice Problems Section 5.6 and Pascal’s Triangle

Posted on by

These practice problems are not in the text book:

  1. Generate the first 11 rows of Pascals Triangle (stop when you’ve reached C(10,10)).
  2. Use your answer to number one to find C(8,6) (do not use the formula $latex \binom{8}{6}$).
  3. Check that the sum of all of the entries in the last row in your triangle is 2^10. What are you counting when you add the entries in a row of Pascal’s Triangle? (Solution: When you add all of the entries of the last row in your triangle you’re counting all of the subsets of the set {1,2,3,…,10}.)
  4. Verify that the number of all subsets of the set {1,2,3,4} is 2^4 either by using Pascal’s Triangle or by writing down all possible subsets.
  5. Use multiplication to count all of the subsets of the set {1,2,3,4}. (Hint: for each number between 1 and 4, there are two options: either the number is In the subset or it is Out. For each subset, write down a corresponding sequence of I‘s and O‘s. Now the problem looks just like counting all possible outcomes when we toss a coin 4 times.)
  6. Verify that the alternating sum of the last row from your triangle is 0. (The alternating sum means that we alternate between adding and subtracting. For example, the alternating sum of the 4-th row in Pascal’s Triangle is 1-3+3-1.)

The follow problems come from Section 5.6 of your text book:

  • 1,2,3,4,9,11,13,15 (For 9-15 odd, shortest possible route means that only South and East steps are allowed.)
  • Solutions:
    • 2 Part a: 2^9, Part b: C(9,2)
    • 4 Part a: C(6,0)+C(6,1)+C(6,2), Part b: 2^6-22 (Hint: Think about our solution to number 1 in Quiz 7),

 

Here are selected solutions for problems not in your text book:

Download (PDF, 186KB)

Here’s a link to download: Selected solutions

Practice Problems Project 5

Posted on by

Here are some practice problems to help you work through Pascal’s Identity:

From the Chapter 5 (see pages 241-242) project try:

  • 1
  • 2 We did this at the end of class–this is essentially your extra credit assignment
  • 3 This is what we spent most of the class period talking through. Try to write down an explanation, and then check your work with your lectures notes.
  • 4
  • Challenge problem: 5 part a

The following problems are not in your text book:

  • Use Pascal’s Identity to generate C(n,r) for all n and r less than or equal to 8.
  • Assuming that C(6,2)=C(6,4), use Pascal’s Identity to show that C(7,2) is equal to C(7,5). Do not use the formula $latex \binom{n}{r}$. (Hint: Convince yourself that C(6,1)=C(6,5)=6.)
  • A student group is forming a committee with 3 members. Assuming there are 56 possible ways to choose the members of the committee, how many members does the student group have? (Hint: Use your work from the first of these problems.)

Selected Solutions:

Download (PDF, 571KB)

Here is a link to download: Selected solutions