MTH 481
Old Assignments

• Welcome to Math 481. This page will have all assignments and notes. Check here frequently for homework updates and corrections.

• Homework before first lecture: Quiz 1/9 will cover the following problem. Given two people chosen at random, what is the probability that they have the same birthday? (It is clearly small, but not zero.)

Corrections and recent revisions are in red.

• Old Homework

• 1/9: Ch 2 Introduction, p.129-132
  HW:
  1. There are six students in a class.
     1. How many ways for the students to line up? If they all line up at random, what is the chance the line is in alphabetical order?
     2. How many ways to choose a class president, vice-president, and secretary (with no one holding two positions)?
     3. Write each counting problem above in set notation. That is, the answer is |A| for what set A?
  2. The four-digit numbers are: 1000, 1001,…,9999.
     1. How many four-digit numbers are there? Justify your answer using the Product Principle.
     2. How many have all four digits different? Example: 1234 or 5203, but not 5202 ? Justify your answer using the Product Principle.
     3. If you choose a random four-digit number, what is the percentage probability that all four digits are different?
  3. A fair coin is tossed 10 times.
     1. What is the chance of 10 heads in a row?
     2. What is the chance of at most one tail?
     3. What is the chance of at least two tails?
  4. Set notation.
     1. Let a,b,c be distinct elements, and A={a,b}, B={b,c}. Write out A∩B, A∪B, A\B, A×B .
     2. By definition, S is a subset of T, written S ⊂ T, if all elements of S are also elements of T. Write out all subsets of A, B, and A×B. How many are there in each case?
     3. Is it ever true that A ⊂ A×B ?
     4. Use set-notation to define the set L whose elements are all lists of 3 elements of A. For example, (a,b,a) ∈ L.
     5. We often write coordinate 3-dimensional space as R³, where R is the set of real numbers. What does this have to do with Cartesian product of sets?
  5. Extra Credit: In class, we found that the probability of k people having a coincidence of birthdays is: 1 - 365^k / 365^k , assuming 365 days in a year.
     1. Do the k = 4 version of this problem by positive counting (splitting into cases).
     2. Redo this problem, taking leap-years into account. Hint: Consider all the days in a four-year period, in which the leap-day Feb 29 occurs once.

  Solutions: 1a. A line is an ordering of the 6 students (Basic Problem 1), with 6! = 720 possibilities. There is only 1 alphabetical ordering, so the probability of getting it is 1/720.   1b. This is a list of 3 students from 6 (Basic Problem 2), so the number of possibilities is 6³ = 6×5×4 =120.   1c. Let S be the set of 6 students. For the first problem, let A = { (a,b,c,d,e,f) s.t. {a,b,c,d,e,f} = S }; that is, the set whose elements are lists (a,b,c,d,e,f) which, when considered as sets {a,b,c,d,e,f}, make the set of students. For the second problem, let A = { (a,b,c) s.t. a,b,c ∈ S and a≠b, a≠c, b≠c }; that is, the set whose elements are triples of distinct elements of S.   2a. The first digit can be 1,...,9, the rest can be 0,1,...,9, so there are 9×10×10×10 = 9000.   2b. The first digit can be 1,...,9, the second can be 0,1,...,9 but different from the first digit, etc., so there are 9×9×8×7 = 4536.   2c. 4536/9000, a bit over 50%.   3a. A result is a list of 10 heads or tails, so the possibilities are 2¹⁰ = 1024. There is only one way to get all heads, so the probability is 1/1024.   3b. There is 1 way to get no tails and 10 ways to get exactly one tail, so the probability is 11/1024, about 1%.   3c. This is the complement of 3(b): (9000−11) / 9000 = 1 − 11/1024 4a. We have A∩B = {b}, A∪B = {a,b,c}, A\B = {a}, A×B = {(a,b), (a,c), (b,b), (b,c)}.  4b. A ⊃ {a,b}, {a}, {b}, {};   B ⊃ {b,c}, {b}, {c}, {}; each have 4 subsets. The set A×B has 16 subsets, for example {(a,b),(b,b),(b,c)}.   4c. Usually, no. A×B is a set whose elements are pairs (a,b), so no element a∈A can be an element of A×B. However, if A = {}, the nullset with no elements, then A×B = {} also has no elements, and A ⊂ A×B. Also, we might manage it for some weird sets of inifinite lists. 4d. L = A³ = A×A×A.   4e. R³ = R×R×R = {(x,y,z) s.t. x,y,z ∈ R}, the set of possible coordinates for the points of space.

• 1/11: Ch 2.1 Binomial coefficients, pp. 131-134.
  HW:
  1. A class has 20 students.
     1. How many ways to choose a basketball team of 5 from the 20 students? (There is no order among team-members.)
     2. How many ways to choose two teams of 5 (an A team and a B team)?
  2. How many four-digit numbers have distinct, increasing digits? Example: 1234 or 4679, but not 4659.
  3. In a standard deck of 52 cards, each card has one of 13 face values (A,2,3,...,J,Q,K) and one of 4 suits (♠,♣,♥,♦). A hand is an unordered set of 5 distinct cards. Compute the number of ways of dealing the following hands, and the corresponding probability.
     1. Two pairs: two cards with a common face value, another two with a different common face value, and one extra card with a third face value. Hint: First choose the face values of the cards, then the suits.
     2. Full house: three cards with a common face value, another two with a different common face value.
     3. Straight: all face values in sequence (e.g. A,2,3,4,5; or 7,8,9,10,J; or 10,J,Q,K,A), but not all of the same suit (which would make a straight flush).
     4. High-card: all cards of different face values (but not a straight), and not all cards of the same suit.
  4. In a grid of city streets, you want to walk to a store 5 blocks north and 10 blocks east. At each corner you must choose whether to walk north or east. How many possible routes?
  5. You have 5 red balls and 3 black balls, which you lay out in a row.
     1. How many different arrangements are possible? Example: • • • • • • • •
     2. How many arrangments with no two black balls next to each other? Example: • • • • • • • •
  Solutions: 1a. Basic Problem 3: Choose a set of 5 out of 20. Ans: (20 | 5) = 20⁵ / 5! = 15504.  1b. First choose 5 from 20, then 5 from the remaining 15. Ans: (20 | 5) (15 | 5) = 46558512.   2. A list of 4 increasing digits corresponds to a set of 4 digits chosen from {1,...,9}, since a set (without order) can always be written in increasing order. For example {2,3,5,9} corresponds to 2359. Ans: (9 | 4) = 9⁴/4! = 126.   3a. A hand like {6♠, 6♥, J♦, J♥, 8♠} corresponds to the following choices: a set of two face values {6,J} from the possible 13, then another face value (8) from the remaining 11; then a set of two suits {♠,♥} from 4 for the smaller pair and two suits {♦,♥} for the larger pair, and finally a suit ♠ for the last card. Ans: (13 | 2) (13−2) (4 | 2) (4 | 2) 4 = 123552. Note: The choice of face values for the two pairs is a set {6,J} = {J,6}, since 6,6,J,J is the same two pairs as J,J,6,6.   3b. Choose a face value for the triple, then a different one for the pair; then choose a set of 3 suits and a set of 2 suits. Ans: 13 (13−1) (4 | 3) (4 | 2) = 3744. Note: The choice of face values is a list like (6,J) ≠ (J,6), since 6,6,6,J,J is a different full house from J,J,J,6,6.   3c. Choose the low face-value of the straight A,2,3,...,10, then choose the 5 suits arbitrarily, but exclude all suits the same (4 cases). Ans: 10 (4⁵ - 4) = 10200.   3d. Choose a set of 5 face values from 13, but exclude a straight (10 cases); then choose 5 suits arbitrarily, but exclude a flush (4 cases). Ans: ((13 | 5) - 10) (4⁵ - 4) = 1302540.   4. Of the 15 steps, choose which 5 are north (the other 10 must be east). Ans: (15 | 5) = 3003.   5a. Given a lineup of balls, record the positions of the black balls. The example • • • • • • • • corresponds to the set {3,5,6}, since there is a black ball in the 3rd, 5th, and 6th positions. This gives a 1-to-1 correspondence between the ball lineups and 3-element subsets of {1,2,...,8}. Ans: (8 | 3) = 56.   5b. Think of the 5 red balls as having 6 spaces between them (counting the two end spaces), and choose which 3 of these spaces is occupied by a black ball. Ans: (6 | 3) = 20.

• 1/13: Multi-set numbers ((n | k)) in Notes 1/13 below.
  HW:
  1. How many ways to choose a basket of 10 fruits, which can be apples, bananas, oranges, or peaches? Example: 3 apples, 0 bananas, 5 oranges, 2 peaches. Write the result as a multi-set number ((n | k)), and compute it using the formula ((n | k)) = (n+k−1 | k) in the Notes below.
  2. How many four-digit numbers are there with increasing (but not necessarily distinct) digits? Example: 2556. Hint: Again use multi-set numbers.
  3. Distributing items among classes.
     1. How many solutions (a,b,c) are there to a+b+c = 10, assuming a,b,c are whole numbers ≥ 0? Example: (a,b,c) = (4,5,1) with 4+5+1 = 10. Hint: Multi-sets can be specified by how many of each kind there are.
     2. A soccer team consists of 11 members, with 1 goalie and the other 10 designated as defenders, midfielders, or strikers. How many configurations of a soccer team are there? Example: 1 goalie, 6 defenders, 0 midfielders, 4 strikers.
     3. How many soccer team configurations are there, if there must be 1 goalie and at least 2 players in each of the other positions?
  Solutions: 1. Ans: ((4 | 10)) = (4+10-1 | 10) = 286.   2. Ans: ((9 | 4)) = (9+4-1 | 4) = 495.   3a. A solution like (a,b,c) = (4,5,1) correpsonds to a multiset {1,1,1,1,2,2,2,2,2,3}, in which there are 4 ones, 5 twos and 1 three. Ans: ((3 | 10)) = (12 | 10) = (12 | 2) = 66.   3b. A configuration is determined by the triple (d,m,s), the number of defenders, midfielders, and strikers, with d+m+s = 10. Ans: ((3 | 10)) = 66.   3c. Since 1 goalie, 2 defenders, 2 midfielders, 2 strikers are fixed, the remaining 4 members are determined by (d,m,s) with d+m+s = 4. Ans: ((3 | 4)) = (6 | 4) = 15.

• 1/18: Ch 2.2. Properties of binomial coefficients. Also: Notes 1/18, Position Transformation.
  HW:
  1. In the game of bridge, the deck of 52 cards is dealt into 4 hands of 13 each to players North, South, East, West. How many possible deals? Here each hand is unordered, but it matters which player gets which hand. Hint: First consider the deals of 13 to N, then to S, etc.
  2. 5 identical gold rings are put on 10 fingers.
     1. If at most one ring can go on each finger, how many arrangements of rings are possible? Example: A ring each on left pinky, left index, left thumb, right index, right ring finger. Hint: Which fingers have a ring?
     2. If any number of rings can go on each finger, how many arrangements possible? Example: 2 rings on left thumb, 1 on right thumb, 2 on right ring finger.
  3. The Notes describe the Stretching Transformation from multi-sets with k elements of n kinds, and sets of k elements chosen from n+k−1, showing that ((n | k)) = (n+k−1 | k). Work out this correspondence in the case of ((4 | 3)) = (6 | 3). In one column, list all the multi-sets M counted by ((4 | 3)), namely {1,1,1}, {1,1,2},..., {3,4,4}, {4,4,4}; and next to each one, write the corresponding set S. For example, M = {2,4,4} corresponds to S = {2+0, 4+1, 4+2} = {2,5,6}. Verify that all (6 | 3) sets S appear in the second column, each just once.
  4. Algebra of (n | k)
     1. Show that (n | k) = n! / k!(n−k)! .
     2. Use (a) to show that (n | k) = (n | n−k).
  5. Extra Credit: Binomials and multi-set numbers
     1. Reverse the equality ((n | k)) = (n+k−1 | k) to write (n | k) as a multi-set number ((m | k)), where m is some expression depending on n.
     2. Using part (a), translate the equality (n | k) = (n | n−k) into an equality between multi-set numbers.
     3. The equality (n | k) = (n | n−k) can be proven by correspondence: the left side counts k-element subsets S ⊂ {1,2,...,n}; the right side counts (n−k)-element subsets S' ⊂ {1,2,...,n}; and the two are related by the transformation S → S' = {1,2,...,n}\S. That is, S' is the complement of S.
        Problem: Find a transformation that directly proves the equality between multi-set numbers you found above.
  Solutions: 1. Note that after N,S,E have their cards, there is no choice for W. Ans: (52 | 13) (52−13 | 13) (52−26 | 13), which simplifies to: 52! / (13!)⁴.   2a. An arrangement of rings is equivalent to a set of 5 fingers out of 10 (i.e. the fingers having rings). There are (10 | 5) such subsets.   2b. Now an arrangement is equivalent to a multi-set of 5 fingers (with repeats indicating multiple rings) among 10 fingers. Ans: ((10 | 5)) = (10+5−1 | 5) = (14 | 5).   3. Here is the table with two rows instead of two columns:

  M

  {1,1,1}

  {1,1,2}

  {1,1,3}

  {1,1,4}

  {1,2,2}

  {1,2,3}

  {1,2,4}

  {1,3,3}

  {1,3,4}

  {1,4,4}

  {2,2,2}

  {2,2,3}

  {2,2,4}

  {2,3,3}

  {2,3,4}

  {2,4,4}

  {3,3,3}

  {3,3,4}

  {3,4,4}

  {4,4,4}

  S

  {1,2,3}

  {1,2,4}

  {1,2,5}

  {1,2,6}

  {1,3,4}

  {1,3,5}

  {1,3,6}

  {1,4,5}

  {1,4,6}

  {1,5,6}

  {2,3,4}

  {2,3,5}

  {2,3,6}

  {2,4,5}

  {2,4,6}

  {2,5,6}

  {3,4,5}

  {3,4,6}

  {3,5,6}

  {4,5,6}

  In both rows, the entries are listed in "dictionary order" with no skipping, so all the elements are listed just once.
  4a. (n | k) = n(n−1)...(n−k+1) / k! = n(n−1)...(n−k+1)(n−k)...2 1 / k!(n−k)! = n! / k!(n−k)! .   4b. (n | k) = n! / k!(n−k)!, whereas (n | n−k) = n! / (n−k)!(n−(n−k))! = n! / k!(n−k)!, the same as before.

• 1/20: 2.2. Pascal's triangle, binomial theorem.
  HW:
  1. Recall the recursive formula for n-choose-k which defines Pascal's Triangle: (n | k) = (n−1 | k−1) + (n−1 | k).
     • We proved this equality by a transformation, giving a one-to-one correspondence between the objects naturally counted by the left side and those counted by the right side.
     • The left side counts k-element subsets S ⊂ {1,2,...,n}.
     • The right side counts both k-element and (k−1)-element subsets S' ⊂ {1,2...,n−1}.
     • The transformation takes a set S to the set S' = S\{n}, removing n if it is present; and leaving S' = S otherwise.
     1. Find the inverse transformation: given S', what set operations take it back to S? (Your rule can involve cases.)
     2. Make a table of this transformation in the case of (6 | 3) = (5 | 2) + (5 | 3). In the first column, list all the sets S (see HW 1/18 #3), and next to each S write the corresponding S' = S\{6} or S' = S. Write S' in the second column if |S'| = 2, and in the third column if |S'| = 3 . At the end, observe that S' runs over all (5 | 2) sets of size 2 and all (5 | 3) sets of size 3, each just once.
     3. Extra Credit: Use the same transformation to get a formula for the multi-set number ((n | k)) in terms of smaller multi-set numbers. (Alternatively, you can find this formula by the method of HW HW 1/18 #5b, translating the formula for binomial coefficients into multi-set numbers.) Write a version of Pascal's Triangle for multi-choose numbers, with entries defined recursively in some way.
  2. The Binomial Theorem says that the n^th row of Pascal's Triangle gives the coefficients for expanding the n^th power of the binomial (x + y): (x + y)ⁿ = xⁿ + (n | 1) x^n-1 y + (n | 2) x^n-1 y² + ...+ (n | n-1) x y^n-1 + yⁿ For example, the row 1,3,3,1 gives the formula: (x+y)³ = x³ + 3 x² y + 3 x y² + y³ .
     1. Compute Pascal's Triangle by hand up to the 10^th row: (10|0) = 1, (10|1) = 10, etc. Make sure you know which number is which (n | k).
     2. Give the formula for (x + y)¹⁰ .
     3. Use the above to explicitly compute 11⁴ and 1001¹⁰ without a calculator. Hint: 11 = 10 + 1, and 10^k has k zeroes. Similarly, 1001 = 1000 + 1, and 1000^k has 3k zeroes.
  3. Sums of binomial coefficents.
     1. Using the previous problem, work out by hand the sum of the 10^th row of Pascal's Triangle: (10|0) + (10|1) + ... + (10|10). (We know it should come to 2¹⁰ =1024.) Explain this result using the Binomial Theorem. Hint: the result is (x+y)¹⁰ for certain values of x,y.
     2. Compute the alternating difference (10|0) − (10|1) + (10|2) + ... − (10|9) + (10|10) . Again explain the result using the Binomial Theorem, and generalize to the n^th row.
     3. Extra Credit: The above problem implies the identity: (n|0) + (n|2) + (n|4) + ... = (n|1) + (n|3) + (n|5) + ... Give a transformation proof of this: the left side counts the subsets of even size inside {1,...,n}, and the right side counts the subsets of odd size. To prove the equality, we want a reversible transformation between these two types of sets.
     4. Extra Credit: Give a transformation proof of the equality: (k | k) + (k+1 | k) + (k+2 | k) + … + (n−1 | k) + (n | k) = (n+1 | k+1) The left side counts the pairs (i,S), where i is a number from k to n, and S is a k-element subset of {1,2,...,i}; and the right side counts (k+1)-element susbsets of {1, 2,...,n, n+1). Give a reversible transformation between these two types of data.
  Solutions: 1a. The transformation is defined by two cases: if |S'| = k, then S = S'; if |S'|= k−1, then S = S'∪{n}. We easily see that this is reverses the previous transformation, and vice versa.
  1b.

  S

  {1,2,3}

  {1,2,4}

  {1,2,5}

  {1,2,6}

  {1,3,4}

  {1,3,5}

  {1,3,6}

  {1,4,5}

  {1,4,6}

  {1,5,6}

  {2,3,4}

  {2,3,5}

  {2,3,6}

  {2,4,5}

  {2,4,6}

  {2,5,6}

  {3,4,5}

  {3,4,6}

  {3,5,6}

  {4,5,6}

  S'

  {1,2}

  {1,3}

  {1,4}

  {1,5}

  {2,3}

  {2,4}

  {2,5}

  {3,4}

  {3,5}

  {4,5}

  S'

  {1,2,3}

  {1,2,4}

  {1,2,5}

  {1,3,4}

  {1,3,5}

  {1,4,5}

  {2,3,4}

  {2,3,5}

  {2,4,5}

  {3,4,5}

  Again, each row lists the appropriate sets in dictionary order, without skipping.
  2a. (10 | k) = 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1.   2b. x¹⁰ + 10x⁹y + 45x⁸y² + 120x⁷y³ + 210x⁶y⁴ + 252x⁵y⁵ + 210x⁴y⁶ + 120x³y⁷ + 45x²y⁸ + 10xy⁹ + y¹⁰.   2c. 1001¹⁰ = 1,010,045,120,210,252,210,120,045,010,001. Each triple of digits is an entry in Pascal's Triangle, e.g. 045 corresponds to (10 | 2) = 45.
  3a. (10|0) + (10|1) + ... + (10|10) = (1+1)¹⁰ = 2¹⁰. Similarly ∑_k=0ⁿ (n | k) = (1+1)ⁿ = 2ⁿ
  3b. (10|0) + (10|1)(−1) + (10|2)(−1)² + ... + (10|10)(−1)¹⁰ = (1+(−1))¹⁰ = 0. Similarly ∑_k=0ⁿ (−1)^k(n | k) = (1−1)ⁿ = 0 for any n > 0. (What about n = 0?)

• 1/23: 2.5 Principle of Inclusion-Exclusion (PIE), pp. 156-158.
  HW:
  1. The PIE formula for 4 bad sets is:
     |A \ (A₁∪…∪A₄)|   =   |A| − ∑ _i |A_i| + ∑ _i,j |A_i∩A_j| − ∑ _i,j,k |A_i∩A_j∩A_k| + |A₁∩A₂∩A₃∩A₄| ,
     where the indices run over all numbers with 1 ≤ i < j < k ≤ 4.
     Problem: Write out this formula without summation signs, listing each pairwise and triple intersection. How many terms are there of each kind? How many terms total? How could you have predicted the number of terms?
  2. 6 rings are to be put on 10 fingers. Determine how many arrangements of rings are possible under each assumption.
     1. The rings are identical (plain gold bands), with at most one allowed on each finger. Example: 11010 10110, where 1 = a ring, 0 = no ring, and the 10 positions correspond to fingers. Hint: Positive counting.
     2. The rings are identical, with any number allowed on each finger. Example: 03000 01200, where the number indicates how many rings on each finger. Hint: Positive counting.
     3. The rings are identical, with at most one allowed on each thumb, any number on the other fingers. Hint: PIE with A = {all arrangements from part (b)}, and forbidden sets A₁ = {arrangements with at least 2 rings on right thumb}, A₂ = same for left thumb.
     4. The rings are identical, with at most two allowed on each finger. Hint: PIE, with A = {all arrangements from part (b)}, A₁ = {at least 3 rings on finger 1},..., A₁₀ = {at least 3 rings on finger 10}. There are 10 forbidden sets, but the PIE formula is still manageable, because...
     5. The rings are distinguishable (Diamond, Emerald, Ruby, Sapphire, Turquoise, Catseye), with at most one on each finger. Example: 0R0E0 T0CSD. Hint: Positive counting using a Position Transform: e.g. the arrangement 0R0E0 T0CSD puts D,E,R,S,T,C into positions (10,4,2,9,6,8).
     6. The rings are distinguishable, with at most one on each finger, but the Diamond and Emerald do not fit on either thumb.
     7. Extra Credit: The rings are distinguishable, with any number on each finger. Hint: First put on 6 identical rings, then replace each with one of the jewelled rings. Another method: Put the D,E,R,S,T,C rings on one by one, and keep track of how many choices are available at each step.
     8. Extra Credit: There are k distinguishable rings and n fingers, with at least one on each finger. Hint: Use the previous part, and PIE.
  3. Six different jobs (J1,...,J6) are assigned to 6 people (P1,...,P6), one job to each.
     1. How many ways to assign the jobs? That is, count all possible job rosters.
     2. Impose the restriction that P1 cannot do J1, P2 cannot do J2, and P3 cannot do J3 (but P4,P5,P6 can do any job). How many allowed job rosters?
        Hint: PIE with A = {all job rosters} and forbidden sets A₁ = {rosters with P1 doing J1}, and similarly A₂, A₃.
     3. How many ways to assign the jobs, with the restriction that P1 cannot do J1 or J2, and P2 cannot do J3 or J4?
        Hint: PIE with A = {all job rosters} and 4 forbidden sets.
  Solutions: 1. The pairwise intersections involve choosing 2 of the 4 sets A₁,...,A₄, and there are (4 | 2) = 6 ways to do this. Similarly, there are (4 | 3) triple intersections, and (4 | 4) = 1 quadruple intersection. Even the first few terms are (4 | 0) = 1 term |A| with no A_i's, and (4 |1) = 4 terms with a single A_i. Hence the total number of terms is (4 | 0) + (4 | 1) + … (4 | 4) = 2⁴ = 16. Similar reasoning holds in general: for r bad sets, the PIE formula has 2^r terms.
  2a. The Position Transformation shows this is (10 | 6) = 210.
  2b. Think of each ring as a choice of finger 1,2,...,10, with repetition allowed. Thus, ring arrangements correspond to multi-sets of 5 elements of 10 kinds. Ans: ((10 | 6)) = (15 | 6) = 5005.
  2c. Ans: ((10 | 6)) − ((10 | 4)) − ((10 | 4)) + ((10 | 2)).
  2d. Since there are only 6 rings total, we cannot have an intersection of more than 2 subsets A_i∩A_j . Ans: |A \ (A₁∩...∩A₁₀)| = |A| − ∑_i=1¹⁰ |A_i| + ∑_i,j |A_i∩A_j| = ((10 | 6)) − 10 ((10 | 3)) + (10 | 2) ((10 | 0)) = 2850. 2e. Write an arrangement by recording which finger has D, which has E, which has R, etc. Then the arrangements correspond to lists of 6 distinct numbers from {1,2,...,10}. Ans: 10⁶.
  2f. PIE with A = {arrangements of D,E,R,S,T,C on 10 fingers, at most 1 per finger} and A₁ = {arrangements with D on left thumb}, A₂ = {arrangements with D on right thumb}, A₃ = {arrangements with E on left thumb}, A₄ = {arrangements with E on right thumb}. Ans: 10⁶ − 4×9⁵ + 2×8⁴.
  Positive counting: There are 8 choices for D and for E, 8 for R, 7 for S, 6 for T. Ans: 8×8³.
  3a. A job roster is a list of all the jobs in some order. Ans: 6! .
  3b. Note |A₁| = 5! since we assign the remaining 5 jobs to 5 people. Similarly for the rest of the terms in PIE formula. Ans: 6! − 3×5! + 3×4! -3!
  3c. PIE with A = {all job rosters}, A₁ = {P1 doing J1}, A₂ = {P1 doing J2}, A₃ = {P2 doing J3}, A₄ = {P2 doing J4}.
  Then |A₁| = 1×5×4×3×2×1, figuring the number of choices for Person 1, Person 2, etc. Similarly for |A₂| , |A₃|, |A₄|. Also |A₁∩A₃| = 1×1×4×3×2×1 , and similarly for |A₁∩A₄|, |A₂∩A₃|, |A₂∩A₄|, but |A₁∩A₂| = |A₃∩A₄| = 0. All triple intersections are empty.
  Ans:     6! − 4×5! + 4×4!

• 1/25: 2.5 Principle of Inclusion-Exclusion (PIE), pp. 156-161.
  HW:
  1. In class, we discussed the Derangement Problem (Secret Santa). Let us introduce the notation n¡ for the answer to this problem: it is to be the number of permutations (rearrangements or ordered lists) of n objects such that no object is returned to its previous place. (In terms of HW 1/23 #3, this is the same as job rosters for n people in which Person i cannot do Job i, for i = 1,...,n.) For example, 3¡ = 2, since the derangements of {1,2,3} are: (2,3,1) and (3,1,2). In class, we used PIE with A = {all permutations} and A_i = {permutations fixing the ith position}, to get the formula: n¡ = n! − (n | 1) (n-1)! + (n | 2) (n-2)! − (n | 3) (n−3)! + ... + (−1)ⁿ .
     1. Show that you can re-write this as: n¡ = n! (1 − 1 + 1/2! − 1/3! + ... + (−1)ⁿ/n!) .
     2. Secret Santa: Suppose n = 10 people put their names in a bag, and each draws out a name at random. What is the probability that no one draws his own name? Also compute this for n = 20.
     3. Extra Credit: Prove that if n is very large, the probability that no one gets his own name does not approach 0, as one might expect, but rather 1/e, where e = 2.718... is the base of the natural logarithm.
  2. One more on job rosters of 6 people assigned 6 jobs. Suppose P1 cannot do J1 or J2, and P2 cannot do J2 or J3. How many allowed rosters?
  3. You have 10 friends {1,...,10}, and you invite a set of 5 to dinner. However, some pairs hate each other, and cannot be invited together: they are {1,2), {2,3}, and {3,4}. How many allowed sets of guests?
  Solutions: 1a. In the original formula for n¡, write out (n | k) = n! / k!(n−k)! ; then factor out n! and cancel (n−k)! in each term to get the desired formula.   1b. For both cases the answer is n¡/n! ≅ 0.36788 up to many digits of accuracy.   2. A = {all rosters}, A₁ = {P1 does J1}, A₂ = {P1 does J2}, A₃ = {P2 does J2}, A₄ = {P2 does J3}. Then all terms in PIE are zero except: |A| = 6! , |A_i| = 5! , |A₁∩A₃| = |A₁∩A₄| = |A₂∩A₄| = 4! . Ans: 6! − 4×5! + 3×4! .   3. PIE: A = {sets of 5 from 10}, A₁ = {sets containing 1,2}, A₂ = {sets containing 2,3}, A₃ = {sets containing 3,4}. Clearly |A| = (10 | 5), |A_i| = (8 | 3), and |A₁∩A₂| = (7 | 2), etc. Ans: (10 | 5) − (3 | 1)(8 | 3) + (7 | 2) + (6 | 1) + (7 | 2) − (6 | 1) = 126.

• 1/27: Notes 1/27 below. Method of Generating Functions, pp. 164-165.
  Recall our direct proof of the Binomial Theorem.
  • In multiplying out the expression (x+y)ⁿ without simplifying or collecting terms, we get a sum of terms which are products with n factors of x or y, like xxyxy...x . We can interpret each term as picking out a subset S ⊂ {1,...,n}. If the first factor is x, we interpret this as 1 ∈ S ; if it is y, we interpret this as 1 ∉ S ; and similarly for the other x-or-y factors.
  • Example: For n = 2, we compute: (x+y)(x+y)  =  x(x+y) + y(x+y)  =  xx + xy + yx + yy. The term xx corresponds to 1 ∈S and 2 ∈S, so S = {1,2}. The term xy corresponds to 1 ∈S and 2 ∉ S, so S = {1}. The term yx corresponds to 1 ∉ S and 2 ∈S, so S = {2}. The term yy corresponds to 1 ∉ S and 2 ∉ S, so S = {}.
  • Every term equal to x^ky^n−k corresponds to an S with |S| = k, so the coefficient of x^ky^n−k is the number of k-element subsets of n elements: namely, (x+y)ⁿ = (n | n) xⁿ + (n | n−1) xⁿ⁻¹y + (n | n−2) xⁿ⁻²y² + ... + (n | 0) yⁿ, which is one form of the Binomial Theorem.
  • Notice that we never used any formula or recurrence for (n | k) in this discussion, only the definition that (n | k) counts subsets of size k out of n.
  HW
  1. Binomial Theorem
     1. Multiply out (x+y)³ using the distributive law, but without simplifying or collecting terms. Make a table of how the 8 terms xxx + xxy + xyx + ... + yyy correspond to subsets S⊂{1,2,3}. Do this so that terms which are algebraically equal (like xxy, xyx, yxx) are adjacent in the table.
     2. Do the same for (x+y)⁴, getting 16 terms.
  2. Logical algebra of multisets. Suppose you have 2 apples and 2 bananas and you put any or all of them in your lunch bag, for example 2 apples and 0 bananas (a multi-set). What are all the possibilities for the contents of the bag?
     1. Figure this by letting "0A" stand for the choice of no apples, "1A" the choice of one apple, etc., and logically expanding the expression:
        (0A or 1A or 2A) and (0B or 1B or 2B)
        using the logical distributivity rule from the notes. Expand until you have an expression like:  (0A and 0B) or (0A and 1B) or .... or (2A and 2B). Match each case at the end to a particular lunch-bag multiset. For example, (2A and 2B) is the multiset M = {A,A,B,B}.
     2. Re-imagine the entire computation in (a), replacing 0A, 0B by x⁰;  1A, 1B by x¹;  2A, 2B by x²;   "or" by + ;  "and" by ×.  Start with (x⁰ + x¹ + x²) (x⁰ + x¹ + x²) and expand using algebraic distributivity. Collect like terms to get a polynomial a₀ + a₁ x +...+ a₄ x⁴ .
        Question: What is the combinatorial meaning of the coefficients a₀,...,a₄? That is, what do these values count about ways of filling the bag?
     3. Now expand f(x) = (1 + x + x²)² again, this time using the binomial theorem (a+b)² = a² + 2ab + b² twice: first with a = 1,  b = x + x², and then again with a = x,  b = x². Thus, re-compute the coefficients a₀,...,a₄ using only algebra.
  Solutions: 1a. (x+y)³ = (xx + xy + yx + yy)(x + y) = xxx + xyx + yxx + yyx  +  xxy + xyy + yxy + yyy.

  term	xxx	xxy	xyx	yxx	xyy	yxy	yyx	yyy
  S	{1,2,3}	{1,2}	{1,3}	{2,3}	{1}	{2}	{3}	{}

  Thus, there are clearly (3|2) terms algebraically equal to x²y and (3|1) terms equal to xy².
  1b. Multiply (xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy)(x + y) to get 16 terms. Check these off one by one when you put them in the table. The term x⁴ comes from the set {1,2,3,4}, the terms equal to x³y come from the sets with 3 elements, the terms equal to x²y² come from the sets with 2 elements, etc.
  2b. Multiply out (x⁰ + x¹ + x²)² to get: x⁰x⁰ + x⁰x¹ + x⁰x² + x¹x⁰ + x¹x¹ + x¹x² + x²x⁰ + x²x¹ + x²x², where each term corresponds to a multiset M. Write each term as x^k, where k is the size of M. Collect like terms to get 1 + 2x + 3x² + 2x³ + x⁴, and the coefficient a_k of x^k is the number of M with k elements. Thus, a_k is the number of lunch-bag multisets with k pieces of fruit.

• 1/30: Ch 2.6.1 Double Decks, pp. 166-167. Notes 1/30 below on the Method of Generating Functions.
  HW:
  1. A trial example for the Method of Generating Funcitons (HHM p. 166 #2). A drawer contains some beads:   3 Green, 4 Blue, 5 Red.   Let a be the number of ways to select a handful of 6 beads. Example: 3 Green, 3 Red. Find a by the Method of Generating Functions.
     • Step 0: Think of a as one of a sequence of problems a₀, a₁, a₂,..., a_n. How high does the sequence go: what is n?
     • Step 1: Let f(x) = a₀ + a₁ x + a₂ x² + ...+ a₁₂x¹² be the generating function coefficients a_k. We do not know these a_i, so we do not yet know f(x). But use the Product Principle for a₀ + a₁ + ... + a_n: (choosing a handful of beads)  ⇔  (0G or 1G or 2G or 3G) and ... where 0G means no Green, means 1 Green, etc. Now re-imagine this logical equivalence as algebra: replace each logical term with an algebraic one, as in the Notes 1/30. The left-hand side is replaced with f(x), which encodes all possible handfuls. The right-hand side is a product, which multiplies out so that each term x^k corresponds to a handful of k beads. Thus we have an explicit product formula for f(x)
     • Step 2: Given the formula from Step 1, use algebra to expand f(x) and find the coefficient of x⁶, which is the number a = a₆ which we originally wanted. In this case, there is no algebraic trick which can help expand, so type in the formula for f(x) into the algebra engine Wolfram Alpha, which will expand out for you. The explicit coefficients you obtain will be the values of a_k.
  2. HHM p. 166 #3. Now the drawer of beads contains 10 red, 8 blue, 11 green. Let a_k be the number of ways to select a handful of k beads with one of the restrictions below. Do Step 1 as above. For Step 2, you may once again use the algebra engine.
     1. No restrictions on the handful.
     2. Restriction: you must take an even number of reds, an odd number of blues, and a prime number of greens.
     3. Restriction: you must take exactly 2 reds, at least 5 blues, at most 4 greens.
  3. Re-do the example of 5-card hands from a double deck from class (see Ch 2.6.1). We did Step 0: a_k is the number of k-card hands from the double deck. Example: a₁₀₄ = 1 since there is only 1 hand with all 104 cards.) In Step 1, we used the Product Principle to find the generating function f(x) = (1 + x + x²)⁵².
     1. Now do Step 2. Use the Binomial Theorem for (a + b)⁵² applied to a = 1, b = (x+x²); then use it again applied to (x + x²)^m. Since we are only looking for a₅, you only need to find all the x⁵ terms, which come from (52 | 3) (x + x²)³, (52 | 4) (x + x²)⁴, and (52 | 5) (x + x²)⁵. Your result will be a specific formula for a₅ in terms of binomial coefficients, found purely by algebra, with no reasoning about hands except for the Product Principle in Step 1.
     2. Look at your formula for a₅, and explain what each of the terms means combinatorially.
     3. Compute a₆ by the same method, and explain the result combinatorially.
     4. Extra Credit: Is each of the above hands equally likely, assuming we deal in the usual way from the double deck? Actually, no. Explain.
        This means we cannot use this model to compute probablilities by counting. What model should we use instead?
  Solutions: 1. Step 0: Define a_k as the number of handfuls with k beads, where k = 0,...,12 (since there are 12 beads altogehter).
  Step 1: (choosing a handful of beads)  ⇔  (0G or 1G or 2G or 3G) and (0B or 1B or ... or 4B) and (0R or 1R or ... or 5R) .
  f(x) = (1+x+x²+x³) (1+x+x²+x³+x⁴) (1+x+x²+x³+x⁴+x⁵)
  Step 2. f(x) = 1 + 3x + 6x² + 10x³ + 14x⁴ + 17x⁵ + 18x⁶ + 17x⁷ + 14x⁸ + 10x⁹ + 6x¹⁰ + 3x¹¹ + x¹². Thus a₆ = 18.
  2a. f(x) = (1+x+...+x¹⁰) (1+x+...+x⁸) (1+x+...+x¹¹)
  2b. f(x) = (1+x²+x⁴+x⁶+x⁸+x¹⁰) (x+x³+x⁵+x⁷) (x²+x³+x⁵+x⁷+x¹¹)
  2c. f(x) = x² (x⁵+x⁶+x⁷+x⁸) (1+x+x²+x³+x⁴)
  3. f(x) = 1 + (52 | 1)(x+x²) + (52 | 2)(x+x²)² + (52 | 3)(x+x²)³ + (52 | 4)(x+x²)⁴ + (52 | 5)(x+x²)⁵ + ...
  We want to extract the x⁵ terms. Now (x+x²)^m has lowest term x^m, highest term x^2m, so we only need to look at: (52 | 3)(x+x²)³   ,   (52 | 4)(x+x²)⁴   ,   (52 | 5)(x+x²)⁵. The three x⁵ terms are then: (52 | 3)(3 | 2)x(x²)²   ,   (52 | 4)(4 | 1)x³(x²)   ,   (52 | 5)(5 | 0)x⁵. Our final answer is: a₅ = (52 | 3)(3 | 2) + (52 | 4)(4 | 1) + (52 | 5)(5 | 0) = 3,748,160 distinct 5-card hands from a double deck. Compare this to (52 | 5) = 2,598,960 from a single deck.

• 2/1: Ch 2.6.2 Counting with Repetition, pp. 168-169.
  HW:
  1. Review of Taylor Series. Let f(x) = a₀ + a₁x + a₂x² + ... + a_nxⁿ be a polynomial function. Here a₀, a₁,..., a_n are some constants which are the coefficients.
     1. Note that a₀ = f(0), since substituting x = 0 makes all other terms vanish. Note also that the derivative of f(x) is: f '(x) = a₁ + 2 a₂ x + 3 a₃ x² + ... + n a_n xⁿ⁻¹. Substituting x = 0, we find a₁ = f '(0). Find a similar formula for a₂, and for a general a_k. Hint: Compute f ^(k)(x), the k-th derivative of f(x).
     2. This gives a new way to compute any row of Pascal's Triangle, for example n = 10. We think of (10 | k) as the coefficient a_k in f(x) = (x+1)¹⁰ = a₀ + a₁x + a₂x² + ... + a₁₀x¹⁰. Use the formula from part (a) to compute (10 | k). Hint: Use the Chain Rule to differentiate (x+1)¹⁰.
     3. Taylor's formula in calculus says that most common functions f(x) can be expressed as Taylor series (infinite polynomials): f(x)  =  a₀ + a₁ x + a₂ x² + ....  =  ∑_k=0^∞ a_k x^k .
        This equation might be valid only for small x, such as |x| < 1. The coefficients are given by the same formula as for polynomials above, since a polynomial is its own Taylor series:   a_k = f ^(k)(0) / k! , where f ^(k)(0) means the k^th derivative of f(x) at x = 0.
     4. Let f(x) = e^x, which is its own derivative. Use this to compute the Taylor series for e^x. Look up Taylor or Maclaurin series in your old Calc II notes or text. What are some functions which don't have a Taylor series?
     5. Compute the Taylor series for 1/(1−x) = (1−x)⁻¹.
     6. Compute the Taylor series of f(x) = sin(x) , using the derivatives sin'(x) = cos(x) and cos'(x) = −sin(x). That is, compute the coefficients a₀, a₁, a₂,...., until you see the pattern. Write the answer in "dot-dot-dot" notation (writing out enough terms to make the pattern clear, then "..."), and also in terms of summation notation. (For summation notation, your exponent should be x^2k+1 since the even terms are zero.)
     7. Approximate sin(π/6) by substituting x = π/6 into your Taylor series, and adding the terms up to x⁵. How good is the approximation?
  2. Practice with geometric series
     1. Compute the Taylor series of the function f(x) = 1/(1-ax), where a is a constant. Hint: You can use Taylor's Formula directly, or substitute ax in place of x in the known geometric series formula.
     2. Compute the Taylor series of f(x) = 1/(x+b), where b is a constant.
     3. Find a simple formula for the generating series f(x) = ∑_{k ≥ 1} k x^k . Hint: Differentiate known series.
     4. Use geometric series to find the value of the infinite repeating decimal 0.1111.... Hint: Write out the meaning of the decimal in terms of 1/10, 1/100,....
     5. Denote a general decimal number as: 0.d₁d₂d₃... where d_k are digits between 0 and 9. Use geometric series to evaluate a general repeating decimal as a fraction: 0.d₁d₂...d_nd₁d₂...d_n... = a/b, where a and b are whole numbers. Hint: Use the whole number D = d₁10^n-1 +d₂10^n-1 + ... + d_n-110 + d_n .
  Solutions: 1a. f ''(x) = 2 a₂ + 3 (2) a₃ x + … so a₂ = f ''(0)/2 = f ⁽²⁾(0) / 2. In general, a_k = f ^k(0) / k!.
  1b. f ^(k)(x) = 10^k(x+1)^10−k since (x+1)' = 1. Thus (10 | k) = a_k = f ^(k)(0) / k! = 10^k / k!. This is not really a new formula, but a way to get the old formula purely through algebra, without reasoning much about sets.
  1c. A function which is badly behaved near x = 0 might not have a Taylor series. For example, f(x) = 1/x has a vertical asymptote, and cannot be approximated by polynomials. Also, f(x) = |x| is not differentiable at x = 0, we cannot apply the formula for a_k, and there is not Taylor series.
  1d. f ^(k)(x) = e^x, so f ^(k)(0) = 1. Hence a_k = 1 / k! and e^x = 1 + x + x² / 2! + x³ / 3! + .... This converges for all x, and so a finite number of terms give an approximation to e^x.
  1e. f ^(k)(x) = k! (1−x)^−(k+1), so a_k = k! / k! = 1 and 1/(1−x) = 1 + x + x² + x³ + ..., an infinte geometric series, which converges for |x| < 1.
  1f. sin(x) = x − x³/3! + x⁵/5! − x⁷/7! + ...
  1g. sin(π/6) = 0.5. The polynomial p(x) = x − x³/3! + x⁵/5! gives p(π/6) = 0.48, which is pretty close.
  2a. 1/(1−ax) = 1 + (ax) + (ax)² + (ax)³ + ... = 1 + ax + a²x² + a³x³ + ...
  2b. 1/(x+b) = 1 / b(1−(−x/b)) = 1/b (1 − x/b + x²/b² − x³/b³ + ...) = 1/b − x/b² + x²/b³ − x³/b⁴ + ...
  2c. We know 1 / (1-x) = ∑_k x^k. Differentiating both sides gives: 1/(1−x)² = ∑_k≥1 k x^k−1. Hence x / (1−x)² = ∑_k≥1 k x^k
  2d. 0.11111... = 1/10 + (1/10)² + (1/10)³ + ... = − 1 + 1/(1 − 1/10) = 1/9.
  2e. The decimal is 10⁻ⁿD (1 + 10⁻ⁿ + (10⁻ⁿ)² + ...) = 10⁻ⁿD / (1 − 10⁻ⁿ) = D / (10ⁿ − 1). Example: 0.325325... = 325/999.

• 2/3: Ch 2.6.3 Changing Money, p 171-175.
  HW:
  1. Practice for Step 2 of the Method: Find the Taylor series of the following functions as explicitly as possible. In each case, write the coefficients in as simple form as possible. Hint: Modify known series. Also use ((n | k)) = (n+k−1 | k) = (n+k−1 | n−1).
     (a)   f(x) = 1/(1−x⁴)     (b)   f(x) = 1/(1−x)⁴     (c)   f(x) = 1/(1−x²)²     (d)   f(x) = x²/(1−x)⁴     (e)   f(x) = (2−x)/(1−x)²    
  2. Difference of powers trick
     1. Verify the formula: aⁿ − bⁿ   =   (a − b) (aⁿ⁻¹ + aⁿ⁻²b + aⁿ⁻³b² + ... + bⁿ⁻¹) by multiplying out the right side and cancelling terms.
     2. Find the Taylor series of: f(x) = 1 / (1−x)(1−x²). Hint: Use the trick of multiplying top and bottom by 1+x, then simplifying the bottom with the difference-of-squares formula to get (1−x²)². Finally use the known Taylor series 1/(1−z)² = ∑_k≥0 ((2 | k))x^k.
     3. Do the same for 1 / (1−x)(1−x³). Hint: Multiply top and bottom by (1+x+x²), and use (1+x+x²)(1−x) = 1−x³.
  3. Making Change Problem. Let N_k be the number of ways to make change for k cents with pennies (1¢) and nickels (5¢). For example, N₁₀ = 3, which counts the cases: 5+5, 5+1+1+1+1+1, and 1+...+1.
     1. Compute an explicit formula for N_k by the Method of Generating Functions. Hint: For Step 1, use the Product Principle. For Step 2, use the Difference of Powers trick to get the denominator to be (1−x⁵)², which can be expanded by a known series; finally multiply it all by the polynomial in the numerator, which shifts around the powers of x.
     2. Explain the formula for N_k by purely combinatorial reasoning.
     3. In class we will show (and it's in the book), that if D_k is the number of ways to make change for k cents with pennies, nickels, and dimes, then D_10j = ((3 | j)) + ((3 | j−1)). Simplify this to give a simple polynomial formula in the variable j. What about D_10j+5?
     4. Extra Credit: Explain the result D_10j = (j+1)² by transforming a choice of a handful of change with value 10j¢ into two independent choices, each with j+1 possibilities. (??)
  Solutions: 1a. Geometric series 1/(1−z) = 1 + z + z² + ... with z = x⁴, so f(x) = 1 + x⁴ + x⁸ + x¹² + ... = ∑_k≥0 x^4k , and a_4k = 1, all other a_m = 0.
  1b. Binomial with negative exponent: f(x) = ∑_k≥0 ((4 | k)) x^k, so a_k = ((4 | k)) = (k+1)(k+2)(k+3)/6 .
  1c. Binomial with negative exponent: f(x) = ∑_k≥0 ((2 | k)) x^2k, so a_2k = ((2 | k)) = k+1, a_m = 0 for m odd.
  1d. f(x) = x² (1 + ((4 | 1))x + ((4 | 2))x² + ...) = ((4 | 0))x² + ((4 | 1))x³ + ((4 | 2))x⁴ + .... = ∑_k≥2 ((4 | k−2)) x^k, so a_k = ((4 | k−2)) = (k−1)k(k+1)/6.
  1e. f(x) = (2−x) ∑_k≥0 ((2 | k)) x^k = ∑_k≥02 ((2 | k)) x^k − ∑_k≥0 ((2 | k)) x^k+1
     = ∑_k≥02 ((2 | k)) x^k − ∑_k≥0 ((2 | k−1)) x^k    =    ∑_k≥0 [2 ((2 | k)) − ((2 | k−1))] x^k ,
     so a_k = 2 ((2 | k)) − ((2 | k−1)) = 2(k+1) − k = k + 2.
  2b. Use (1+x)(1−x) = 1−x² to massage the denominator into the form 1 / (1−x²)². Then use the known series formula: 1 / (1−z)² = ∑_k≥0 ((2 | k))z^k, with z = x². f(x)  =  (1+x) / (1+x)(1−x)(1−x²)  =  (1+x) / (1−x²)(1−x²)
   =  (1+x) / (1−x²)²  =  (1+x) ∑_k≥0 ((2 | k))(x²)^k
   =  [((2|0)) + ((2|1))x² + ((2|2))x⁴ + ...]  +  [((2|0))x + ((2|1))x³ + ((2|2))x⁵ + ...]

  Thus a_2j = a_2j+1 = ((2|j)) = j+1.
  2c. Use (1+x+x²)(1−x) = 1−x³ to massage the denominator into the form 1 / (1−x³)². Then use the known series formula: 1 / (1−z)² = ∑_k≥0 ((2 | k))z^k, with z = x³.

  f(x)  =  (1+x+x²) / (1+x+x²)(1−x)(1−x³)  =  (1+x+x²) / (1−x³)(1−x³)
   =  (1+x+x²) / (1−x³)²  =  (1+x+x²) ∑_k≥0 ((2 | k))(x³)^k
   =  [((2|0)) + ((2|1))x³ + ((2|2))x⁶ + ...]  +  [((2|0))x + ((2|1))x⁴ + ((2|2))x⁷ + ...]  +  [((2|0))x² + ((2|1))x⁵ + ((2|2))x⁸ + ...]

  Thus a_3j = a_3j+1 = a_3j+2 = ((2|j)) = j+1.
  3a. Step 1:     (choose a handful of change of any value)  ⇔  (0P or 1P or ...) and (0N or 1N or ...)
  is re-imagined algebraically as:

  f(x) = ∑_k≥0 N_kx^k = (1+x+x²+x³+...) (1+x⁵+x¹⁰+x¹⁵+...) = 1 / (1−x)(1−x⁵). Step 2: Just as for 2(b),(c), we get N_5j = N_5j+1 = N_5j+2 = N_5j+3 = N_5j+4 = j+1.
  3b. A handful of pennies and nickels worth k = 5j cents is determined by how many nickels: either 0 or 1 or ... or j−1 or j nickels, making j+1 choices. Thus N_5j = j+1. Similarly for k = 5j+1, etc.
  3c. ((3 | j)) + ((3 | j−1)) = (3+j−1 | j) + (3+(j−1)−1 | j−1)
  = (j+2 | j) + (j+1 | j−1) = (j+2 | 2) + (j−1 | 2)
  = (j+2)(j+1)/2 + (j+1)j/2 = (j+1)(j+2+j)/2 = (j+1)².

• 2/6: Read Notes on Generating Functions below.
  Finish HW 2/3, especially Step 2 techniques.
  Know the Binomial Theorem for Negative Exponents: 1 / (1−z)ⁿ = ∑_k≥0 ((n | k))x^k.

• Old Notes

• Notes 1/13: A multi-set is an unordered collection of objects with repeats allowed, like {1,1,1,3,4,4,5}. The number ((n | k)), pronounced 'n multi-choose k', counts the multi-sets of k elements of n possible kinds. Examples:
  • ((3 | 2)) counts the multi-sets of 2 elements from the three kinds {1,2,3}; they are:   {1,1} {1,2} {1,3} {2,2} {2,3} {3,3}.   Since there are 6 such multi-sets, ((3 | 2)) = 6.
  • ((2 | 3)) counts the multi-sets of 3 elements from the two kinds {1,2}; they are:   {1,1,1} {1,1,2} {1,2,2} {2,2,2}.   Thus ((2 | 3)) = 4.
  • A typical real-world example of a multi-set is a handful of 7 jellybeans taken from a big jar with 5 flavors (Red, Yellow, Green, Blue, White): this is equivalent to a multi-set of 7 elements from 5 kinds. For example, a handful with 3 of R, none of Y, 1 of G, 2 of B, 1 of W, corresponds to the multi-set {R,R,R,G,B,B,W}. The number of different handfuls is thus ((5 | 7)), which we compute below.
  • We can also describe a multi-set by the list of multiplicities for each possible kind. For example, the above multi-set of jelly beans could be described by the multiplicity-list (3,0,1,2,1), and the size is 3+0+1+2+1 = 7.

  The Stretching Transformation changes multi-sets into into ordinary sets, which will allow us to compute ((n | k)). This is a reversible transformation (one-to-one correspondence) defined as follows. We assume the elements of the multi-set M are listed in order: a₁ ≤ a₂ ≤ … ≤ a_k; and we define the elements of the set S by adding 0 to the first entry of M, 1 to the second entry, etc.

  M = {a₁,...,a_k}   →   S = {b₁,...,b_k} = {a₁+0, a₂+1, a₃+2,..., a_k+k−1} . Since 1 ≤ a₁ ≤ a₂ ≤ … ≤ a_k ≤ n, we have: 1 ≤ b₁ < b₂ < … < b_k ≤ n+k−1. The set S is thus a k-element subset of {1, 2,..., n+k−1}

  We show the Stretching Transformation is a one-to-one correspondence by defining its inverse, the Shrinking Transformation, which changes sets back into multi-sets:

  S = {b₁,...,b_k}   →   M = {a₁,...,a_k} = {b₁−0, b₂−1, b₃−2,..., b_k−k+1} . These two transformations clearly undo each other, in either order (Stretching, then Shrinking; or Shrinking, then Stretching).

  Conclusion: the multi-sets counted by ((n | k)) are in one-to-one correspondence with the sets counted by (n + k − 1 | k), meaning that these numbers are equal:

  ((n | k))   =   (n + k − 1 | k) , where we know how to compute the right-hand side. For example, ((5 | 7)) = (5+7−1 | 7) = (11 | 7) = (11 | 4) = 11⁴ / 4! = 330.