Go to announcements | course information.

on homework problems

Besides finding the anwer, always try to *explain*, as well as you can, how you *know* you have the correct answer.

When solving problems, a systematic solution is better than guesswork. You often may find a solution by intelligent guessing, but then you should look for a way of showing that your solution is correct. This part needs to be systematic if it is to be completely convincing. (This will be clearer after a few days of class!)

Allow 15 minutes per problem (minimum) before you give up, even if you
feel you're getting nowhere. These problems need time for thought. If you're
still stuck, *go on* to another problem. Return to the sticky problem
later (say, the next day). Often, it then looks easier because you tried
hard the first time and then gave your mind time to grind it up--I mean,
to come up with ideas. To get the advantage of this method, you have to
start the problems well ahead of time. Last-minute effort will not work
well in this class.

- Hand in a final draft:
*neat*work that is well organized and*not cramped*. Use as much space as you need. Please also leave some extra space between problems for my comments. - You may discuss hand-in HW with other people, but you must write it up in your own words.
- No little stubbies from tearing a page out of your binder. Remove them neatly, please!
- Fasten the pages securely. Staples are best. Folding the paper over and/or tearing it is no good (not secure); paper clips don't hold well.

Due Tues. 8/31:

Due Wed. 9/1:

*Hand in* Wed. 9/1: Ch. 1, ## 5, 9, 10.

Due Fri. 9/3:

*Hand in* Tues. 9/7: Ch. 1, ## 13, 16, 25, 27

*Read* Sects. 3.1-3.3.
*Do* for discussion on

*Hand in* Wed. 9/15 (**changed!**): Ch. 3, ## 4(c), 5(b), 12, 14.

*Read* Sects. 3.4-3.5.
*Do* for discussion on

*Hand in* Fri. 9/17: Ch. 3, ## 18, 20, 27, 33, 36, 38, 39(b).

*Read* Sects. 5.1, 5.2, and 5.3 to (5.10).
*Do* for discussion on

Hand in Fri. 9/24: ## 6,8, 9, 11, 14, 18, and B2.

*Read* Sects. 5.3, 5.4, and 5.5. (In Sect. 5.4, emphasize clutters and Sperner's Theorem 5.4.3.)
*Do* for discussion on

Hand in Fri. 10/1: ## 20, 24, 32, and C3.

- B1. Prove combinatorially the formula in Ch. 5, #19:
m
^{2}= 2 C(m, 2) + C(m, 1). - B2. Give a combinatorial proof of Chapter 5, #13.

- C1. Prove Ch. 5, #22 combinatorially, assuming r, m, k are integers and r >= m >= k >= 0.
- C2. Give a combinatorial proof of formula (5.8). (Hints? The combinatorial proofs of #10 or B2 or Pascal's formula might suggest an idea.)
- C3. Give a combinatorial proof of the first equation in Ch. 5, #7.

*Read* Sections 6.1-6.2.
*Do* for discussion on

Hand in Fri. 10/15: Ch. 6, ## 2, 5, and ## D2, D3.

*Read* Sections 6.3-6.5.
*Do* for discussion on

Hand in Fri. 10/22: Ch. 6, ## 13, 14, 24(b), 26, 28, 30.

- D1. Find the number of different ways you could get one dozen doughnuts at the bakery of Ch. 6, # 6, if the bakery has 9 apple-filled, 8 maple frosted, 5 chocolate, and 7 plain doughnuts, and
- (a) there is no further restriction;
- (b) the dozen must contain every type of doughnut.
- D2. Find the number of solutions to x
_{1}+ x_{2}+ x_{3}+ x_{4}= 22 in integers that satisfy x_{1}<= 14, x_{2}<= 8, x_{3}<= 15, x_{4}<= 7, and- (a) all x
_{i}>= 0;- (b) all x
_{i}> 0.- D3. Find a formula for the number of r-combinations of the multiset M = {infty·a
_{1}, infty·a_{2}, 100·a_{3}, 100·a_{4}}, for all r >= 0. (``infty'' means infinity.)

- E1. Let t be a positive integer and let M be the multiset {t·a
_{1}, t·a_{2}, ..., t·a_{k}}. Find a formula for the number of r-combinations of M when:- (a) r = 2t.
- (b) r = 2t + 1.
- (c) r = 2t - 1.

Remember the Standard Hint: You may want to start with k = 3 (or even k = 2) to get an idea.

Read Section 2.1.

Do for discussion on:

Hand in Fri. 10/29: Ch. 2, ## 3, 6, 11, 17, 19.

- F1 (a) In # 9, prove the same is true if there are 9 people in the room.
- (b) Prove that the conclusion does
*not*necessarily follow if the number of people in the room is 6.- (c) Can you decide whether or not it is possible to draw the same conclusion if there are 8 people in the room? 7 people? (This is probably hard. I would accept a solution as a term paper (optional, for extra credit). If you want to do that, discuss it with me first -- with no obligation.)
- (b) Prove that the conclusion does

Read Sections 4.1-4.4.

Do for discussion on:

Hand in Fri. 11/12: Ch. 4, ## 9, 15(a), 20, 24, 30

Read Sections 4.5 and 5.7 (see correction).

Do for discussion on:

Hand in Fri. 11/19:

- G1. Consider the list of inversion sequences of permutations of S
_{n}= {1,2,ldots,n} that comes from listing the permutations in the order given by the ``mobility'' process of Section 4.1 and then writing down their inversion sequences in the same order. Is there any interesting property of the specific order in which the inversion sequences appear in this list? I recommend you try generating the inversion sequences for very small values of n and see what turns up. If you find something interesting, you can report your observations, even if you don't know how to prove them.

The following problems are optional but are good mathematics. I don't know the answers. I'm very interested in what you come up with.

- G2.
**NEW**What is the smallest number of inversions in a derangement of S_{n}= {1,2,...,n}, for each n >= 1? We conjecture that the answer might be the ceiling of n/2, but we're not sure. - G3.
**NEW**What is the largest number of inversions in a derangement of S_{n}? (Do Ch. 4, # 9 first.) - G4.
**NEW**Generalize Ch. 4, # 8, as far as possible. The general question is: given n, find a formula for the number of permutations having exactly k inversions, for all the several largest values of k. Specifically:

(a) Do this for n = 5, where the single largest value of k is 15 and we already did k = 15, 14, 13 in # 8. Try to extend the same type of formula for smaller values of k. Don't expect one formula to work for all values of k; at some point the answer will get more complicated, but I'm asking you to find a simple formula that works for just the large k ("near" 15).

(b) Try to develop a formula for any n. Here # 9 tells you the single largest value of k and asks you to find a solution for k = max - 1; I'm asking you to work down, i.e., k = max - 2, max - 3, and so on as far as you can find a simple formula.

Read Section 10.1 to the end of page 347. (See corrections.)

Do for discussion on:

Hand in Wed. 11/24: Ch. 10, ## 3, 8, 11, 12, 14-15(iii), and H2.

- H1. Use Ch. 10 # 1 to find
- (a) the additive inverse (``negative'') of every element of Z
_{4}(i.e., do arithmetic mod 4);- (b) the multiplicative inverse (``reciprocal'') of every element of Z
_{4}that has a reciprocal.- H2. Use Ch. 10 # 3 to do the same as in # H1 for Z
_{5}(i.e., do arithmetic mod 5). - (a) the additive inverse (``negative'') of every element of Z

Read Section 10.1 to the end of page 347.

Do for discussion on:

- Recall that S
_{n}= {1, 2, ..., n}. - For n > 0,
*D*(n) (this is a script D) is the set of all divisors of n, i.e., {m > 0 : m|n}. We partially order it by divisibility; i.e., we look at the poset (*D*(n), |). - Also for n > 0, Pi
_{n}is the poset of partitions of S_{n}, defined in Ch. 4, # 47. - For a multiset X,
*C*(X) (this is a script C) denotes the set of all combinations of X (as in Ch. 4, # 40), partially ordered by containment.

Every problem has the parts (a-c):

- I1. Do (a-c) for the poset Pi
_{3}. - I2. Do (a-c) for the poset Pi
_{4}. (I1 and I2 are designed to give you a better idea of what Pi_{n}is in general.) - I3. (A) Do (a-c) for
*D*(12).- (d) Compare this poset with the one in Ch. 5, # 45.

(B) Do (a-c) for*C*(X) where X = { 2·a_{1}, 1·a_{2}}.- (d) Compare this poset with those in (A) and Ch. 5, # 45.
- I4. (A) Do (a-c) for
*D*(16).- (d) What is special about this poset?

(B) Do (a-c) for*D*(81).- (d) Compare this poset with
*D*(16).

(C) Do (a-c) for*C*(X) where X = { 4·a_{1}}.- (d) Compare this poset with
*D*(16).- I5. (A) Do (a-c) for
*D*(2^{r}), where r is any positive integer.- (d) What is special about this poset?

(B) Do (a-c) for*D*(3^{r}).- (d) Compare this poset with
*D*(2^{r}).- I7. Do (a-c) for the poset (S
_{16}, |), that is, S_{16}ordered by divisibility. (This is similar to Ch. 5 # 45).- (d) Compare (S
_{16}, |) with*D*(16). - (d) Compare this poset with the one in Ch. 5, # 45.

Read Section 10.1, pp. 348-350 and Section 10.4 to the top of p. 384. ni Do for discussion on:

Hand in Wed. 12/8: Ch. 10, ## 13, 17(ii, v, vi), 41, 45, 48, and # J2.

- Z
_{n}, for an integer n >= 2, is the set {0, 1, ..., n-1} with arithmetic carried out modulo n. We call this system*the integers modulo*n. - A polynomial f(x) with coefficients in Z
_{p}is called*irreducible over*Z_{p}if it cannot be factored as a product of polynomials of lower degree. (Here we treat only the coefficients as elements of Z_{p}. x is an indeterminate, just as with ordinary polynomials.). - F
_{q}, for a prime power q = p^{e}(i.e., p is a prime number and e >= 1), is the set of all polynomials in i (or in x, if you prefer), with coefficients in Z_{p}, that have degree < e. Calculations in F_{q}are carried out modulo a fixed polynomial f(x) of degree e that is irreducible over Z_{p}. This polynomial is called a*modulus polynomial for*F_{q}. The meaning of ``calculating mod f(x)'' is that i satisfies the equation f(i) = 0. The system F_{q}is called a*field of order*q (that is, with q elements). - For a prime number p, Z
_{p}and F_{p}are the same. For any nonprime number, though, they are very different. (Z_{n}is not even a field, if n is not a prime.)

- J1. This problem concerns the field F
_{9}of 9 elements, with modulus polynomial f(x) = x^{2}+ x + 2, as in the lecture.- (a) Write out the 9 elements of F
_{9}. Write the addition and multiplication tables. - (b) Find the negatives (additive inverses) and reciprocals (multiplicative inverses) of all elements that have them. Which inverses don't exist?

- (a) Write out the 9 elements of F
- J2.
- (a) Construct 3 MOLS of order 9.
- (b) For (a) you have to use the finite field F
_{9}of order 9. What is the difference that explains why you can't use the product-square construction of pp. 380-382 here although you could use it to find 2 MOLS?

Go to announcements | course information.