Mathematics 357 – Combinatorics Review Sheet for Midterm Exam 1 February 18, 2005

General Information

As announced in the course syllabus and on the course homepage, the first midterm exam will be given in class on Friday, February 25. The exam will cover the material we have studied since the start of the semester, through the material on generalizations of the binomial theorem that we will discuss on Friday, February 18. (This includes sections from Chapters 2,3,4,5 in the text – see detailed list of topics you are responsible for below). This will be an individual, closed-book, closed-notes exam. No collaboration of any kind will be permitted during the exam period. You may bring a calculator if you want one; however, answers written terms of powers, factorials, binomial coefficients, etc. can always be left in that form, so a calculator should be of truly minimal value for your work on the exam. My advice: leave it home!

If there is interest, I would be happy to run a late afternoon or evening review session next week to help you prepare. Schedule constraints: I will have to leave campus no later than 5:15pm on Thursday and we are giving an evening exam in MATH 132 on Wednesday evening, so I will be busy from 6:00pm to 9:00pm or so that day. In addition, I will not be available Monday evening after 5:30pm or so.

Topics to be Covered

1) Chapter 2: The Pigeonhole Principle (basic and strong forms), applications.

2) Chapter 3: Basic counting principles, permutations and combinations of sets, permutations and combinations of multisets. (Note: some counting problems may come from considerations of “sets” and other structures in the Set card game. Review Discussion 1 to make sure you recall how all that works!)

3) Chapter 4: Generating combinations. (Note – we only discussed a portion of the material in this chapter, and you’re only responsible for the stuff from sections 3 and 4 that we did cover.)

5) Chapter 5: Binomial coefficients, identities, algebraic and combinatorial proofs, applications to counting problems. (Omit the material in sections 4 and 7 of this chapter.)

Note: Some problems may ask you to find algebraic and/or combinatorial arguments to prove identities concerning binomial or multinomial coefficients, etc. The best way to prepare for these is to study the examples we did in class and make sure you understand the basic ideas.

Some Good Practice Problems

• Chapter 2/3, 16, 17, 19, 27

• Chapter 3/11, 12, 14, 23, 26, 37, 39 • In the card game Set, the cognoscenti sometimes call “sets” where the three cards are

all different in each of the four attributes “null sets”. How many different “null sets” are there in the Set deck?

• Chapter 4/11, 12, 15, 16, 18 (see Discussion 2!)

• Chapter 5/11, 18, 19, 20, 23, 29, 30, 38, 39, 44.

Warning: The above problems cover the ideas you will need to understand in order to do the exam problems, but the exam problems may be organized and formatted differently, may draw on different types of examples, etc. Be prepared!