Problems to think about and research before the first class.

1. Given two people chosen at random, what is the probability that they have the same birthday out of 365 days in the year (assuming all birthdays equally likely, and ignoring leap year)?
2. Given 3 people or n people, what is the probability that at least two have the same birthday?
3. How many people do you need for a birthday coincidence to be more likely than not?

Reading: HHM text, Ch 2 Introduction, p.129-131
HW:

1. There are six students in a class. Use the Product Principle to solve the following enumeration problems.
   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, define a set A containing all cases or possibilities, so that the answer is |A|, the number of elements in A.
2. The four-digit numbers are: 1000, 1001, 1002, …, 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. Given any sets A,B, we define:
   • The element relation a ∈ A, meaning a is one of the elements in the set A.
   • The subset relation A ⊂ B, meaning A is contained in B, i.e. every element in A is also in B.
   • The union A∪B, the set of elements which are in A or in B (or both).
   • The intersection A∩B, the set of elements which are in A and in B.
   • The set difference A ∖ B, the set of elements which are in A but not in B.
   • The Cartesian product A×B, the set of pairs (a,b), where a∈A and b∈B.
   Now let a,b,c be distinct elements, and consider the sets A={a,b}, B={b,c}.
   1. Write out all elements in A ∪ B, A ∩ B, A ∖ B, and A × B.
   2. Write out all subsets of A, of B, and of A × B. How many are there in each case?
   3. Use set notation to define the set of triples T = A×A×A = A³, whose elements are all lists of 3 elements of A. For example, (a,b,a) ∈ T. How many such triples are there?
   4. We often write three-dimensional space as R³, where R is the set of real numbers. Explain this notation: how does it relate to Cartesian product of sets?
   5. Is it ever true that S ⊂ S×T, for some sets S,T?
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). Make sure you do not miss any cases, and check your answer numerically against the above formula.
   2. Redo the birthday problem for general k, but taking leap-years into account (any counting method). Hint: The answer is not 1 − 365.25^k / 365.25^k. Instead, take as your probability space all the days in a four-year period, in which the leap-day Feb 29 occurs once.
   3. Find the probability for at least two distinct pairs of coincident birthdays; also for a triple coincidence (365-day year, any counting method). Explore this topic.

1a. We can think of a line as a list of the 6 students, with no repeats. The first person in line can be any of the 6 students, the second person any of the remaining 5, etc. By the product principle, the answer is 6×5×4×3×2×1 = 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 the 6, with no repeats. We can choose the president to be any of the 6, the vice-president from the remaining 5, etc., 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  =  { (s₁, . . . , s₆) for s_i ∈ S and s_i ≠ s_j for i ≠ j }.

Another way is A = { (a,b,c,d,e,f) such that {a,b,c,d,e,f} = S }, 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 full 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 = 50.4%.

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), all lists of 10 tosses which do not contain at most one tail. Thus the probability of this case is: (1024−11) / 1024  =  1 − 11/1024  ≈  99%.

4a. We have A∪B = {a,b,c}, A∩B = {b}, A ∖ B = {a}, A×B = {(a,b), (a,c), (b,b), (b,c)}

4b. A has 4 subsets {a,b}, {a}, {b}, {}. B has 4 subsets {b,c}, {b}, {c}, {}. The set A×B has 16 subsets, for example {(a,b), (b,b), (b,c)}. Can you find a general rule predicting how many subsets a set will have?

4c. T = A³ = A×A×A = {(x,y,z) for x,y,z ∈ A}. Since A has two elements, there are 2³ = 8 elements of T.

4d. R³ = R×R×R = {(x,y,z) s.t. x,y,z ∈ R}, the set of possible coordinates for the points of space.

4e. Usually, no: S×T is a set whose elements are pairs (s,t), which are different from individual elements s∈S. For example:

{a,b} ⊄ {a,b}×{c} = {(a,c), (b,c)}.

However, if S = {}, the nullset with no elements, then S×T = {} also has no elements, and S = S×T.
Extra Credit: We might manage T ⊂ S×T or even T = S×T for some weird sets of infinitely nested lists. Explore.

Reading: Ch 2.1 Three basic problems, pp. 131-142.   Ch 2.3 Multinomial coefficients, pp. 144-145 only.
Basic Principles We find the number of possible outcomes in a specified situation. If A is the set of all outcomes, we compute the number of outcomes |A|.

• Sum: Classify all possible outcomes into disjoint cases (no overlap). If A_i ∩ A_j = {} for all i ≠ j, then
  |A₁∪ · · · ∪A_r|  =  |A₁| + · · · + |A_r|.

• Product: Analyze each outcome as a sequence of independent choices (factors). If A₁ × · · · × A_r  =  {(a₁, . . . ,a_r) for a_i∈A_i}, then
  |A₁ × · · · × A_r|  =  |A₁| · · · |A_r|.

• Difference: The number of good outcomes equals the number of all outcomes minus the number of bad outcomes. If B ⊂ A, and the set A ∖ B means all elements of A except elements of B, then
  |A ∖ B|  =  |A| − |B|.
  ⊞ Principle of Inclusion-Exclusion (PIE)  
  Count good outcomes which must avoid several overlapping sets of bad outcomes B₁, . . . , B_r ⊂ A.

  |A ∖ (B1∪ · · · ∪Br)|	=	|A| − ∑1≤i ≤ r |Bi| + ∑1 ≤ i < j ≤ r |Bi ∩ Bj|
  		− ∑1 ≤ i < j < k ≤ r |Bi ∩ Bj ∩ Bk| + · · · + (−1)r |B1 ∩ · · · ∩ Br|

• Quotient: If A can be arranged into disjoint rows of cases, A = R₁ ∪ R₂ ∪ · · · ∪ R_m, where each row has the same number of elements |R_i| = |R_j| for all i,j, then the number of rows is m = ^|A|⁄_|Ri|. Example: Choose-numbers (n | k)  =  n^k / k! .
  ⊞ Burnside-Polya theory: Counting with symmetry  
  • Burnside's Theorem: Let a group G act as symmetries on C, and let C be the set of symmetry classes, in which we count symmetric objects of C as the same, i.e. the classes c = {σ(c) for σ ∈ G}.
    Then the number of symmetry classes is equal to the average number of fixed objects of a symmetry:
    |C|   =   ¹⁄_|G| ∑_σ∈G |C_σ|,
    where C_σ = {c ∈ C with σ(c) = c}, the set of objects of C which are fixed or symmetric under σ ∈ G.
    (In fact, this theorem was discovered by Frobenius.)
  • The main case is when C is the set of colorings of n vertices of an object X with k available colors. Then the symmetry group G = Sym(X) permutes the n vertices, making G ⊂ S_n, and induces an action on the colorings C. Then we have
    |C_σ| = k^cyc(σ),
    where cyc(σ) is the number of cycles in σ acting on the n vertices.
  • Polya's Method: Compute the color-counting generating function of the symmetry classes:
    f_C(x₁, . . . , x_k)  =  ∑_c∈C x_c(1)···x_c(n) .
    This is given by:
    f_C  =  ¹⁄_|G| ∑_σ∈G f_Cσ ,
    the average of the cycle index polynomials:
    f_Cσ(x₁, . . . , x_k)  =  ∏_i (x₁ⁱ + ··· + x_kⁱ)^cyc_i(σ),
    where cyc_i(σ) is the number of cycles of length i in σ. Note that |C| = f_C(1, . . . , 1), substituting x₁ = ··· = x_k = 1.
• Transformation: Change the data of the outcomes into a different-looking but equivalent form via a reversible transformation: then the number of objects of the original data is equal to the number of transformed objects. If there is an invertible mapping (bijective correspondence) T : A → B, then |A| = |B|.
  Common transformations: Position, Multiplicity, Bins-and-Beans, Deletion, Complement, Shift.

List means a sequence of elements in which order matters, e.g. (3,4,5) ≠ (4,3,5).
Set means a collection of elements in which order does not matter, e.g. {3,4,5} = {4,3,5}.
    We usually write sets in a standard order, increasing or alphabetical.

Basic Problems:

1. The number of ways to list n distinct elements in some order is:  n! = n(n−1)(n−2) ··· 1
2. The number of ordered lists of k distinct elements from n distinct elements is:  n^k = n(n−1)(n−2) ··· (n−k+1)
3. The number of unordered sets of k distinct elements from n distinct elements is:  (n | k) = n^k / k!
4. The number of unordered multi-sets with k elements, repeats allowed, chosen from n different kinds, is:  ((n | k))  =  (n+k−1 | k)  =  (n+k−1 | n−1)

Multinomial Coefficients: (n | k₁, . . . , k_r), is the number of ways to split an n-element set into r subsets with sizes k₁, . . . , k_r. (Here k₁ + ··· + k_r = n.) For example, (n | k, n−k) = (n | k), since choosing a subset S ⊂ [n] is the same as splitting [n] = S ∪ ([n]−S). To compute these numbers, we choose the first subset (n | k₁) ways, then from the remaining n−k₁ elements, we choose the second subset (n−k₁ | k₂) ways, etc., obtaining the formula:

(n | k₁, . . . , k_r)   =   (n | k₁) (n−k₁ | k₂) (n−k₁−k₂ | k₃) ···   =   ^n!⁄_{(k1! k2!···kr!)}

Multinomial coefficients are different from multi-choose numbers.

List means a collection in which order matters. Set means order does not matter.

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, . . . ,10,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. Any hand of 5 cards from the 52-card deck.
   2. One pair: two cards with a common face value and another three with all different face values. Ex: {7♥, 7♠ 2♣, 10♣, K♦}
      Hint: First choose the face values of the cards, then the suits.
   3. 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.
   4. Full house: three cards with a common face value, another two with a different common face value.
      Hint: There is a subtle difference between this hand and two pairs.
   5. Straight: all face values are consecutive (A,2,3,4,5 or 2,3,4,5,6 or . . . or 10,J,Q,K,A), but not all of the same suit (which would make a straight flush).
   6. Extra Credit: Give a brief but clear combinatorial analysis of each type hand in poker, and show that the ranking of their value corresponds to decreasing probability of each type (high-card the most likely, then one pair, two pair, three of a kind, straight, flush, full house, four of a kind, all the way to straight flush the least likely).
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 white 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: • ◦ ◦ • ◦ • ◦ ◦
6. Multinomial coefficients. A class has 20 students.
   1. How many ways to split the class into four teams of 5 each (teams A,B,C,D)?
   2. How many ways to choose just an A team and a B team from the class (with 5 each, no overlap)?
   3. Write each number above as a multinomial coefficient (n | k₁, k₂, . . . ), the number of ways to split a set of n objects into subsets of given sizes k₁, k₂, . . . . Verify that your answers above are equivalent to the general formula: (n | k₁, k₂, . . . ) = n! / k₁! k₂! ···

Because of the limitations of browser graphics, I write (n choose k) horizontally as (n | k). In your handwritten solutions, use the standard vertical notation.

1a. Basic Problem 3: Choose a set of 5 out of 20. Ans: (20 | 5) = 20⁵ / 5! = 20×19×18×17×16 / 5×4×3×2 = 15504. Try computing a few of these on a calculator, then on a spreadsheet using the FACTORIAL and/or BINOMIAL functions.

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 is choice of 5 unordered objects from 52, an example of Basic Problem 3: the number of possible hands is:

(52 | 5)  =  ⁵²⁵⁄_5!  =  2598960.

3b. A hand like {6♠, 6♥, 3♦, 8♠, J♥} corresponds to the following choices: one face value (6) for the pair from the possible 13, and a set of 3 face values {3,8,J} from the remaining 12; then a set of two suits {♠,♥} for the pair from the 4 suits, and a list of suits (♥,♦,♠) for the 3 distinct face values.
Ans: 13 (12 | 3) (4 | 2) 4³ = 1098240, with probability ^1098240⁄_2598960 ≈ 42.2%.
Note: The suits for the pair are interchangeable, which is why they form a set. Order matters for the suits of the other 3 cards, the suits for the lowest, middle, and highest face values: changing the order gives a different hand. Thus, these 3 suits form a list.

3c. 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.

3d. 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.

3e. Choose the low face-value of the straight: A or 2 or 3 or . . . or 10, then choose the 5 suits arbitrarily, but exclude all suits the same (4 cases). Ans: 10 (4⁵ − 4) = 10200.

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 white balls as having 6 spaces between them (including the two end spaces), and choose which 3 of these spaces are occupied by a black ball. Ans: (6 | 3) = 20.

6a. First choose 5 from 20, then 5 from the remaining 15, then 5 from the remaining 10, leaving 5 for the last team. Ans: (20 | 5) (15 | 5) (10 | 5) = 11732745024 . (I computed using Wolfram Alpha, which understands a command like binomial(20,5).) This is the same as splitting the 20 players into four subsets of size 5, so it is the multinomial coefficient (20 | 5,5,5,5).

6b. Similar to part (a), giving (20 | 5) (15 | 5). Choosing 5-person teams A and B leaves 10 students in a third set, so this is the same as (20 | 5,5,10).

6c. To see that the above answers give the formula, write the choose numbers as: (n | k) = n! / k! (n−k)!. Then in part (b), we see by cancellation that:

(20 | 5) (15 | 5)   =   (20! / 5! 15!) (15! / 5! 10!)   =  20! / 5! 5! 10!

Similarly for part (a).

Transformation Principle: Change the data of an object into a different-looking but equivalent form, via a reversible transformation. Then the number of objects of the original data is equal to the number of transformed objects. In set notation, if there is an invertible mapping T : A → B, then |A| = |B|.
Equivalent terms: reversible transformation, invertible mapping, bijection, one-to-one correspondence, one-to-one & onto function.
Position Transform: An invertible way to change lists into sets, which often makes counting easier. Example problems:

• How many ways to toss a coin 5 times with 3 heads, such as HTTHH? This naturally corresponds to lists like (H,T,T,H,H) with 3 H's and 2 T's, which cannot be easily counted with any of our usual principles or essential problems. Instead, we transform the data by recording the positions of the H's: (H,T,T,H,H) has an H in the first, fourth, and fifth positions, so it corresponds to the set {1,4,5}. Since there were 3 H's in the list, there are 3 elements in the set, which lies inside {1,2,3,4,5}. The transformation has the table:

  list	HHHTT	HHTHT	HHTTH	HTHHT	HTHTH	HTTHH	THHHT	THHTH	THTHH	TTHHH
  set	{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}

  The point of this transformation is that it outputs all 3-element subsets of {1,2, . . . ,5}, each just once, and we know how to count these: Basic Problem 3 tells us there are (5 | 3) = 10. Of course, in this case we can just write out all the lists and count them, but the argument works in general: the number of ways to get k heads out of n tosses is (n | k).
  We could also record the positions of the 2 T's instead of the 3 H's, giving the alternative expression (5 | 2) = (5 | 3): in general, this shows (n | k) = (n | n−k).
• Walks on a city grid with 10 North steps and 5 East steps. We transform a walk (a list of N's and E's) by recording the positions of the 5 E's out of the 15 positions. Ans: (15 | 5) = 3003. Note: Recording the 10 N's gives the same number, since (15 | 10) = (15 | 5).
• Rows of 5 white and 3 black balls. We record the positions of the 3 black balls out of the 8 total positions. Ans: (8 | 3).

1. Re-do all the counting problems from the previous HW, explicitly writing the transformations which reduce the given objects to an equivalent, easily counted form. Specify by writing the transform of a typical object.
   Example: Count one-pair poker hands. A typical one-pair hand is transformed into:
   {7♥, 7♠ 2♣, 10♣, K♠}   ↔   ( 7, {2,10,K}, {♥, ♠}, (♣, ♣, ♠) )
   On the right side, the face value for the pair is chosen first; then the three other face values with order irrelevant (since they can be rearranged in increasing order without changing the hand); then a set of two suits for the pair; and finally a list of suits for the other three cards (order matters, since once the three face values are written in increasing order, switching their suits gives a different hand). The transformed data on the right is clearly counted by:
   13 (12 | 3) (4 | 2) 4³.

2. Position Transform. Find the probability of tossing either 3 or 4 heads out of 7 tosses of a fair coin. Show how the objects to be counted correspond to certain sets, which are easy to count.
3. All subsets of [n]
   1. List all subsets of [3] = {1,2,3}, starting with the empty set {} and ending with the whole set {1,2,3}. How many subsets altogether?
   2. How many subsets (of any size) are there for an n-element set [n] = {1,2, . . . , n}? Write this as a sum of choose numbers, and compute it for n = 1, 2, 3, 4. Guess a pattern.
   3. To prove that the above pattern works for all n, use a Reverse Position Transform. That is, for a given subset S ⊂ [n], transform it into a sequence of n binary 0/1 choices (in computer terminology, a string of n bits). This is the inverse of the Position Transform. Now count all possible bit-strings using the Product Principle.

1-2. Four-digit numbers with increasing digits:

4679   ↔   {4,6,7,9} ⊂ [9].

Ans: (9 | 4).

1-3a. Any 5-card hands: (52 | 5) without transform.

1-3b. One pair hands: done in problem example.

1-3c. Two-pair hands:

{2♥, 2♠ 7♣, 7♥, K♠}   ↔   ( {2, 7}, K, {♥, ♠}, {♣, ♥}, ♠) )

Ans: (13 | 2) 11 (4 | 2)² 4.

1-3d. Full house hands:

{7♥, 7♠ 2♦ 2♣, 2♥}   ↔   ( (7, 2), {♥, ♠}, {♦, ♣, ♥}) )

Ans: 13² (4 | 2) (4 | 3).

1-3e. Straight hands. Face values determined by low card:

{7♥, 8♠ 9♥ 10♣, J♥}   ↔   ( 7, (♥, ♠, ♥, ♣, ♥) )

Ans: 10×(4⁵−4), removing flush hands (having all the same suit).

1-4. Walks 5 blocks N, 10 blocks E. Positions of N's:

E E E N N E E E E N E N N E E   ↔   {4, 5, 10, 12, 13} ⊂ [15]

Ans: (15 | 5).

1-5a. Row of 5 white & 3 black balls. Positions of black balls:

◦ ◦ • ◦ • • ◦ ◦   ↔   {3, 5, 6} ⊂ [8]

Ans: (8 | 3).

1-5b. Row of 5 white & 3 black balls, no black balls adjacent. White balls make 6 gap positions, 1◦2◦3◦4◦5◦6, choose 3 gaps with a black ball:

◦ ◦ • ◦ • ◦ ◦ •   ↔   {3, 4, 6} ⊂ [6]

Ans: (6 | 3).

2. Consider the data: lists of 7 H's or T's with 3 or 4 H's total. These cannot be counted directly by the Product Principle, so we transform them into equivalent data which is easier to count, using the Position Transform (see the Notes). That is, we record the positions of the H's, turning a list like (H,T,T,H,T,H,T) into the set {1,4,6} inside {1,2, . . . ,7}. For lists with 3 H's, we get all sets of 3 positions out of 7, giving a count of (7 | 3). Similarly, there are (7 | 4) lists with 4 H's. The product principle gives 2⁷ for the number of tosses with any number of H's, so the probability is ( (7 | 3) + (7 | 4) ) / 2⁷ = (35 + 35) / 128 = 35/64, a little better than even chance.

3. Count all subsets of an n-element set, S ⊂ [n]. For n = 3, we have the 8 subsets S = {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Reverse Position Transformation changes the sets S into lists L = (a₁, a₂, a₃) with a_i = 0 or 1. The elements of S give the positions of the 1's.

set S	{}	{1}	{2}	{3}	{1,2}	{1,3}	{2,3}	{1,2,3}
list L	0 0 0	1 0 0	0 1 0	0 0 1	1 1 0	1 0 1	0 1 1	1 1 1

The output is all lists of three 0/1 entries, and the Product Principle counts 2³ = 8. Similarly, the number of all subsets of [n] is 2ⁿ.

Transformation Principle: Change the data of an object into a different-looking but equivalent form, via a reversible transformation. Then the number of objects of the original data is equal to the number of transformed objects. In set notation, if there is an invertible mapping T : A → B, then |A| = |B|. (The terms reversible transformation, invertible mapping, bijection and one-to-one & onto function are synonymous.)

Multisets, Bins-and-Beans Transform, Multiplicity Transform

• A multi-set is an unordered collection of objects with repeats allowed, like {1,1,1,3,4,4,5}. The multi-set number ((n | k)), pronounced "n multi-choose k", counts the multi-sets of k elements of n possible kinds. For example, suppose you take a handful of 7 jellybeans from a big jar with 5 flavors. This is the same as a multi-set of 7 elements of 5 kinds: {1,1,1,3,4,4,5} means three of flavor #1, none of flavor #2, one of flavor #3, two of flavor #4, and one of flavor #5. Thus ((5|7)) counts how many different handfuls you could get.
• Bins-and-beans transform, also called Stars-and-bars. We start by picturing the 1's in a multi-set as beans in bin #1, the 2's as beans in bin #2, and so on, writing beans as O and bin-dividers as | . There is a total of k beans and n−1 bin-dividers. For example, this multiset of type ((5 | 7)) corresponds to a binary sequence of 7 O's and 4 |'s:
  {1,1,1,3,4,4,5}   ↔   O O O | | O | O O | O

  Next we apply the Position Transform to the beans-and-bins sequence of O's and |'s, recording which n − 1 of the k + n − 1 symbols are | ; this is a subset of n − 1 positions chosen from k + n − 1 . In the above example k + n − 1 = 11 :

  O O O | | O | O O | O   ↔   {4,5,7,10} ⊂ {1,2, . . . ,11}

  Conclusion: the multi-sets counted by ((n | k)) are in one-to-one correspondence with the sets counted by (k+n−1 | n−1), meaning that these numbers are equal. Alternatively, we could choose the k positions of the O's, giving a correspondence with (k + n − 1 | k) . Thus:

  ((n | k))   =   (k+n−1 | n−1)   =   (k+n−1 | k) ,
  which we know how to compute. For example, ((5 | 7)) = (11 | 4) = 11⁴ / 4! = 330, or ((5 | 7)) = (11 | 7) = 11⁷ / 7! = 330.
• Multiplicity transform takes a multiset M with k elements of n kinds, and transforms it into its list of multipliciities (m₁, m₂, . . . , m_n), where m₁ is the number of 1's in M, m₂ is the number of 2's in M, etc. All m_i ≥ 0, and the sum m₁ + ··· + m_n = k, the total number of elements in M. For example: M = {1,1,1,3,4,4,5}   →   (3,0,1,2,1).

1. Multi-choose numbers. 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, i.e. {A,A,A,O,O,O,O,O,P,P}. Write the result as a multi-set number ((n | k)), and compute it using the formula ((n | k)) = (n+k−1 | k).
2. The formula for multi-choose numbers states that ((3 | 3)) = (5 | 3) = 10. This can be proved using the Bins-and-Beans & Position Transforms, which change a multi-set M = {a ≤ b ≤ c} for a,b,c ∈ {1,2,3} into the equivalent data of a set S = {a' < b' < c'} = {a < b+1 < c+2} for a',b',c' ∈ {1, . . . , 5}. Make a 2-row table of the 10 multi-sets M, and underneath their corresponding sets S.
3. How many four-digit numbers are there with increasing (but not necessarily distinct) digits? Example: 2556. Hint: Again use multi-choose numbers.
4. 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?
5. Extra Credit: Find a more simple and direct way to describe our transform from multisets to sets. That is, give the same transformation in one arithmetic step, rather than as Bins-and-Beans followed by Position Transform.

1. Ans: ((4 | 10)) = (4+10−1 | 10) = 286.

3. A number like 2556 corresponds to a multiset {2,5,5,6}, with 4 objects of 9 possible kinds. Ans: ((9 | 4)) = (9+4−1 | 4) = 495.

4a. A solution like (a,b,c) = (4,5,1) corresponds 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.

4b. 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.

4c. 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.

• Reading: Ch 2.2, p. 138-139.    
• Transformation Principle for Identities: To prove an identity equating two algebraic expressions α = β, find a set A counted by the left side, and a set B counted by the right side: α = |A| and β = |B|. Now find a reversible transformation which pairs each object in A with one object in B (formally, define an invertible mapping T : A → B). This proves |A| = |B|, hence α = β.
• Complement Transform: Proves the symmetry of Pascal's Triangle:
  (n | k)  =  (n | n−k).
  Denote [n] = {1, . . . ,n}. Let A contain all sets S ⊂ [n] with size |S| = k, and B contain all sets S' ⊂ [n] with |S'| = n−k. The transform T : A → B takes each S to its complement S' = T(S) = [n] ∖ S, namely the elements not in S. The inverse transform T⁻¹ takes complement again, S = T⁻¹(S') = [n] ∖ S'.
• Deletion Transform: Proves the Pascal's Triangle recurrence formula:
  (n | k)  =  (n−1 | k−1) + (n−1 | k).
  Here A contains all sets S ⊂ [n] with size |S| = k, and B contains all sets S' ⊂ [n−1] with size |S'| = k−1 or k. The transform takes each S to the same set with n removed (if it is present): i.e. to S' = S ∖ {n}. If n ∈ S, this means |S'| = k−1 ; otherwise S' = S and |S'| = k.

1. Workout with Basic Problems. A teacher gives an exam to 10 students (Quincy, Rhonda, Sally, Tom, Ursula, Victor, Wanda, Xavier, Ying, Zoltan).
   1. How many ways could the exams be arranged in a stack? Example: top-to-bottom X,S,U,Y,Q,R,T,V,Z,W.
   2. Students are listed alphabetically in the grade book, and each receives a grade of A,B,C,D, or F. Example: Q gets C, R gets A, S gets C, . . .. How many possible grade lists?
   3. The teacher writes all the grades in order, highest-to-lowest. Example: A,A,B,B,B,C,C,C,D,F. How many possible grade lists of this kind?
   4. The teacher gives a gold star to 3 of the students. Example: R,T,W each get a star. How many ways to distribute stars?
   5. The teacher gives 3 prizes (a pen, a pencil, and a bag of skittles) to three different students. Example: pen to S, pencil to Q, skittles to Y. How many ways to distribute prizes?
   6. Same as (e), but a given student may receive more than one prize. Example: pen and skittles to U, pencil to V. How many ways to distribute prizes?
   7. 6 identical gold rings are to be put on 10 fingers, with at most one ring allowed on each. Determine how many arrangements of rings are possible. Example: 11010 10110, where 1 = a ring, 0 = no ring, and the ten positions correspond to fingers. Hint: Transform.
   8. Same as (g), 6 rings on 10 fingers, but with multiple rings allowed on each finger. Example: 03000 01200, where the number indicates how many rings on each finger.
2. Count the anagrams (rearrangements) of the word MISSISSIPPI. Example: SPSPSSIIMII. Hint: For each anagram, use the Position Tranform to split the 11 positions into four "teams" corresponding to the 4 I's, 1 M, 2 P's, and 4 S's. The multinomial (not multichoose) numbers count such splits of a set into subsets of specified sizes. (See the Toolkit above.)
3. In Pascal's triangle, the n^th row contains the numerical values of (n | 0), (n | 1), . . . , (n | n). The left and right ends are always (n | 0) = 1 and (n | n) = 1, and each (n | k) is the sum of the entries (n−1 | k−1) and (n−1 | k) above it in the previous row. This reflects the recursive formula from class: (n | k)  =  (n−1 | k−1) + (n−1 | k). This exercise explores various properties of this triangle
   1. Compute by hand the first 10 rows of Pascal's triangle using the recursive formula above, adding pairs of entries in each row to get the entry below and between them. (It only takes 1 minute.)
   2. Re-compute the entries for (6 | 0), (6 | 1), . . . , (6 | 6) using our formula (n | k) = n^k / k! . Which method of computing (6 | k) is more efficient?
   3. Starting with (n | k) = n^k / k!, show the formula (n | k) = n! / k!(n−k)!. Use this formula to compute (6 | 0), . . . , (6 | 6) one more time. Which is more efficient?
   4. Pascal's triangle has an obvious left-right symmetry in the entries, which we proved combinatorially using the Complement Tranform. Give an algebraic proof using part (c). (An algebraic proof computes with formulas, whereas a combinatorial proof examines the underlying sets.)
   5. Prove the recurrence formula (n | k) = (n−1 | k−1) + (n−1 | k) algebraically, substituting a formula for each binomial coefficient and checking that the resulting equality is valid.
   6. Add up each row of Pascal's triangle: that is, compute (n | 0) + (n | 1) + ··· + (n | n). Verify that this sum is always 2ⁿ. Can you explain and/or prove this for a general n?
   7. Now alternately add and subtract each entry in a row: that is, compute (n | 0) − (n | 1) + (n | 2) − ··· ± (n | n). Predict a general formula for every n. Explanation?
4. Deletion Transform proof of the recursive formula: (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 Deletion Transform takes a set S to the set S' = S\{n}, deleting n if it is present; and leaving S' = S otherwise.
   Problems:
   1. Define the reverse transformation (the Insertion Transform): given S', what set operations take it back to S? (Your rule can involve cases.)
   2. Make a table of the Deletion Transform in the case of (6 | 3) = (5 | 2) + (5 | 3). In the first column, list all the sets S, 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 a multi-version of the Deletion Transform 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 writing each choose number in the usual Pascal's Triangle recursion as a certain multi-choose number.) Write a version of Pascal's Triangle containing all multi-choose numbers, with entries defined recursively by the formula above, starting with the base values ((n | 0)) = ((1 | n)) = 1.
5. Standard Transformations (See Notes above and in the previous HW.)
   1. Write out all 2⁴ = 16 subsets of {1,2,3,4}, and under each, write the corresponding binary sequence (a₁, . . . , a₄) with a_i = 0 or 1, using the Reverse Position Transformation. For example, the set S = {1,4} corresponds to the sequence (1,0,0,1), where the i^th position is 1 if i ∈ S, and 0 if i ∉ S.
   2. Write out all multi-sets with 4 objects of 3 kinds, and under each, write the corresponding list of non-negative whole numbers (a,b,c) with a+b+c = 4, using the Multiplicity Transform. For example, M = {1,1,1,3} corresponds to (3,0,1), since M has 3 ones, 0 twos, and 1 three.
   3. Add to your table from part (b), by drawing under each multi-set the corresponding bins-and-beans diagram. For example, M = {1,1,1,3} corresponds to [OOO | | O], since there are 3 beans in the first bin, none in the second bin, and one in the third bin.
   4. Continuing (b) and (c), for each bins-and-beans diagram, write the corresponding set of 4 positions out of 6. The diagram [OOO | | O] corresponds to {1,2,3,6}, since the beans O occupy the 1st, 2nd, 3rd, and 6th positions inside the brackets [······], and the remaining positions are bin-dividers |.
   5. Composing the mappings (c) and (d) gives our transformation from multi-sets to sets from the previous lecture. What combinatorial identity is proved by this transform?

1a. Ways to order 10 distinct objects. Basic Problem #1:   10!

1b. Lists of 10 independent entry grades, each with 5 choices. Product Principle: 5¹⁰

1c. Multi-sets of 10 grades of 5 kinds (with repeats). Requiring increasing order is the same as saying order is irrelevant, since switching the order does not give a new case to count. Basic Problem #4:   ((5 | 10)) = (5+10−1 | 10) = (14 | 10) = (14 | 4) = 14×13×12×11 / 4×3×2.

1d. Sets of 3 names out of 10 (order irrelevant). Basic Problem #3:   (10 | 3).

1e. Lists of 3 distinct names from 10 (pen-winner, pencil-winner, skittles-winner). Basic Problem #2:   10³.

1f. Lists of 3 independent names with 10 choices for each. Product Principle: 10³.

1g. The Position Transformation shows this is (10 | 6) = 210.

1h. An arrangement of rings is a list of 10 whole numbers adding up to 6. By the Multiplicity Transform, this corresponds to multi-sets of 6 elements of 10 kinds (think of each ring as a choice of finger 1,2, . . . ,10, with repetition allowed). Ans: ((10 | 6)) = (15 | 6) = 5005.

2. Given an anagram like SPSPSSIIMII, let S₁ = {7,8,10,11} be the positions of the I's, S₂ = {9} be the position of the M, etc. giving the set partition:

[11] = {7,8,10,11} ∪ {9} ∪ {2,4} ∪ {1,3,5,6}.

This correspondence can be reversed, so by the Tranformation Principle, the number of anagrams is equal to the number of such set partitions, which are counted by the multinomial coeffcient (11 | 4,1,2,4) = ^11!⁄_4!1!2!4! = 34,650.

You can also think of this as choosing the I positions in (11 | 4) ways, then the M position in (7 | 1) ways, then the P positions in (6 | 2) ways, finally the S positions in (4 | 4) = 1 way, making

(11 | 4,1,2,4) = (11 | 4) (7 | 1) (6 | 2) (4 | 4).

3a. See HHM p. 139, or Wolfram Alpha.

3b. The triangle is more efficient for computing a whole row, while the formula is better if you only need one value.

3c. The formula (n | k) = n! / k!(n−k)! is very inefficient, since n! is usually much larger than n^k. However, this formula is useful for seeing the properties of (n | k), as in the next problem.

3d. There is a left-right mirror symmetry in the entries, which can be proved by noting that (n | k) = n! / k!(n−k)! whereas:

(n | n−k) = n! / (n−k)!(n−(n−k))! = n! / (n−k)!k! .

3e. See HHM p. 139.

3f. (n | 0) + (n | 1) + ··· + (n | n) = 2ⁿ for all n, which follows from the Binomial Theorem next time.

3g. (n | 0) − (n | 1) + ··· ± (n | n) = 0 for all n ≥ 1, which also follows from the Binomial Theorem.

4a. 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 reverses the previous transformation, and vice versa.

4b. Here we use 3 rows instead of columns.

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}

Note that each row lists the appropriate sets in dictionary order, without skipping; that is, the Deletion transform is compatible with dictionary order.

5a. Imitate the Position Transformation table at the bottom of notes,

5b,c,d,e. There are ((3 | 4)) = (6 | 4) = (6 | 2) = 15 multi-sets M, each corresponding to a multiplicity list (a,b,c), a bins-and-beans diagram, and a position set S (see notes, Multi-sets). These transformation mappings, pictured below, give a combinatorial proof that ((3 | 4)) = (6 | 4).

M

{1,1,1,1}

{1,1,1,2}

{1,1,1,3}

{1,1,2,2}

{1,1,2,3}

{1,1,3,3}

{1,2,2,2}

{1,2,2,3}

{1,2,3,3}

{1,3,3,3}

{2,2,2,2}

{2,2,2,3}

{2,2,3,3}

{2,3,3,3}

{3,3,3,3}

(a,b,c)

(4,0,0)

(3,1,0)

(3,0,1)

(2,2,0)

(2,1,1)

(2,0,2)

(1,3,0)

(1,2,1)

(1,1,2)

(1,0,3)

(0,4,0)

(0,3,1)

(0,2,2)

(0,1,3)

(0,0,4)

B&B

OOOOII

OOOIOI

OOOIIO

OOIOOI

OOIOIO

OOIIOO

OIOOOI

OIOOIO

OIOIOO

OIIOOO

IOOOOI

IOOOIO

IOOIOO

IOIOOO

IIOOOO

S

{1,2,3,4}

{1,2,3,5}

{1,2,3,6}

{1,2,4,5}

{1,2,4,6}

{1,2,5,6}

{1,3,4,5}

{1,3,4,6}

{1,3,5,6}

{1,4,5,6}

{2,3,4,5}

{2,3,4,6}

{2,3,5,6}

{2,4,5,6}

{3,4,5,6}

1. Keep it short. No one wants to read your explanation, they only want to extract the information quickly. More words = more pain.
2. Begin with the setup and purpose of the document. Don't assume the reader knows what you are talking about.
3. Adapt to your audience. Explain details and background they would find confusing, and leave out the obvious. To make a proof rigorous, you do not have to spell out every detail: rather, must make clear to your audience how to spell out every detail, if needed.
   Here, imagine your audience as other students in our class who have not done this assignment. Don't write for me, since I already know the problem and don't need any explanation.

Reading: Ch 2.2 p. 139-140.    

1. Another counting workout: Board games. In each turn, you move your game piece on a track.
   1. In the One-Step Game, for each turn you either stay in place, or advance one step. How many possible outcomes in 8 turns?
      Example: The 8 turns are: step, stay, stay, step, stay, step, step, stay.
   2. In the One-Step Game, how many ways can you advance 5 steps in 8 turns?
      Example: step, stay, stay, step, stay, step, step, step.
   3. In the Many-Step Game, for each turn you advance any number of steps: 0,1,2,3, . . . . How many ways can you advance 5 steps in 8 turns?
      Example: 1 step, 0 steps, 0 steps, 3 steps, 1 step, 0 steps, 0 steps, 0 steps.
   4. In the Dice-Roll Game, for each turn you roll 1,2, . . . , 6 and advance that number of steps. How many ways can you advance 18 steps in 8 turns?
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ⁿ⁻¹ y + (n | 2) xⁿ⁻² y² + ··· + (n | n−1) x yⁿ⁻¹ + 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. Pascal Triangle identities.
   1. Use the Binomial Theorem to prove that the sum of the n^th row of Pascal's Triangle is:
      (n | 0) + (n | 1) + (n | 2) + · · · + (n | n)  =  2ⁿ.
      Compare this algebraic proof with our previous transformation proof of the formula.
   2. Use the Binomial Theorem to prove that the sum of the n^th row of Pascal's Triangle, counted with alternating ± signs, is zero:
      (n | 0) − (n | 1) + (n | 2) − · · · ± (n | n)  =  0.

   3. Extra Credit: Give a transformation proof of the alternating sum formula, in the form:
      (n | 0) + (n | 2) + (n | 4) + · · ·   =   (n | 1) + (n | 3) + (n | 5) + · · · .
      That is, find a reversible transformation from subsets of [n] with an even number of elements to subsets with an odd number of elements.
   4. Extra Credit: Here is a remarkable identity:
      (2n | n)  =  ∑_k (n | k)².
      For example, (4 | 2) = (2 | 0)² + (2 | 1)² + (2 | 2)² = 6. Prove this by a combinatorial transformation. Hint: Split a set S ⊂ [2n] into parts lying in the intervals [1,n] ∪ [n+1,2n].
4. Work out the induction proof of the Binomial Theorem in the case (n = 4) ⇒ (n = 5). That is, assuming we know the formula:
   (x+y)⁴  =  (4 | 0)x⁴ + (4 | 1)x³y + (4 | 2)x²y² + (4 | 3)xy³ + (4 | 4)y⁴,
   prove the formula for (x+y)⁵. Do not compute any (n | k)'s, just use their recursive properties.
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. That is, ((m | k)) is symmetric to what other multi-set number?
   3. The symmetry formula (n | k) = (n | n−k) can be proven by transformation: the left side counts k-element subsets S ⊂ [n]; the right side counts (n−k)-element subsets S' ⊂ [n]; and the two are related by the Complement Transform S → S' = [n]\S.
      Problem: Find a transformation that directly proves the analogous formula for multi-set numbers you found above.

1a. A sequence of 8 independent choices, with 2 outcomes for each. Product Principle:  2⁸ = 256.

1b. A sequence of 8 binary choices, with 5 steps and 3 stays. Position Transformation into Basic Problem 3:  (8 | 5) = (8 | 3) = 56.

1c. A sequence of 8 whole numbers adding up to 5, (n₁, . . . , n₈) with n_i ≥ 0 and n₁ + ··· + n₈ = 5. The Multiplicity Transformation turns this into arrangements of 5 beans in 8 bins, Basic Problem 4:  ((8 | 5)) = (5+8−1 | 5) = (12 | 5) = 792.

1d. Consider the Many-Step game from (c). Moving 18 steps in 8 turns is equivalent to 8 numbers n_i ≥ 1 whose sum is 18:

n₁ + ··· + n₈  =  18.

Now, here we require that each turn move at least 1 step, n_i ≥ 1. This allows us to transform the data into 8 numbers m_i = n_i−1 with m_i ≥ 0 whose sum is 10:

m₁ + ··· + m₈  =  (n₁−1) + ··· + (n₈−1)  =  18−8  =  10.

This gives ((8 | 10)) ways for this game.

However, there is one more restriction: the Dice-Roll Game also excludes step sizes n ≥ 7, or m = n−1 ≥ 6. We remove these bad cases with negative counting. A bad step m = 6,7,8,9,10 can occur in just one of the 8 turns, leaving 10−m steps in the 7 remaining turns. Thus the answer is:

((8 | 10)) − 8((7 | 4)) − 8((7 | 3)) − 8((7 | 2)) − 8((7 | 1)) − 8((7 | 0)).

2b,c. We have:

11⁴ = (10 + 1)⁴   =   10⁴ + (4 | 1)(10³)(1) + (4 | 2)(10²)(1²) + (4 | 3)(10)(1³) + 1⁴

  =   10⁴ + 4(10³) + 6(10²) + 4(10) + 1   =   14641,

where the digits are the n = 4 row of Pascal's Triangle.

Similarly,

(1000 + 1)¹⁰ = 1000¹⁰ + 10(1000⁹)(1) + 45(1000⁸)(1²) + 120(1000⁷)(1³) + ··· + 1¹⁰

= 1,010,045,120,210,252,210,120,045,010,001,

where the blocks of 3 digits are precisely the n = 10 row of Pascal's Triangle.

3a. Substituting x = y = 1 in the Binomial Theorem gives: 2ⁿ = (1+1)ⁿ = (n | 0)1ⁿ + (n | 1)1ⁿ⁻¹1 + ··· + (n | n)1ⁿ.
For a transformation proof, recall that the left side counts binary strings of length n (whether each k ∈ [n] is in or out of a subset S), and the right side counts subsets S ⊂ [n] of any size. These are related by the Position Transform.

3b. Substituting x = 1, y = −1 in the Binomial Theorem gives:

0  =  (1−1)ⁿ = (n | 0)1ⁿ + (n | 1)1ⁿ⁻¹(−1) + (n | 2)1ⁿ⁻²(−1)² + ··· + (n | n)(−1)ⁿ

 =  (n | 0) − (n | 1)1ⁿ⁻¹(−1) + (n | 2) − ··· ± (n | n)(−1)ⁿ

4. In the equation (x+y)⁵ = (x+y)⁴x + (x+y)⁴y, expand (x+y)⁴ using the n = 4 case of the Binomial Theorem, then multiply out and collect terms. Finally, apply the Pascal recurrence (4 | k) + (4 | k−1) = (5 | k) to obtain the Binomial Theorem for n = 5.

Reading: Ch 2.5 pp. 156-158.

1. PIE. Recall our Inclusion-Exclusion formula for removing bad subsets B₁, B₂, B₃ from the set A of all objects: |A \ (B₁∪B₂∪B₃)|   =   |A| − ∑_i |B_i| + ∑_i,j |B_i∩B_j| − |B₁∩B₂∩B₃|,
   where each index runs over 1,2,3, and we have one term for every possible intersection of B₁, B₂, B₃.
   The formula for 4 subsets is:
   |A \ (B₁∪…∪B₄)|   =   |A| − ∑_i |B_i| + ∑_i,j |B_i∩B_j| − ∑_i,j,k |B_i∩B_j∩B_k| + |B₁∩B₂∩B₃∩B₄| ,
   where the indices run over all numbers with 1 ≤ i < j < k ≤ 4. Here the summation notation ∑_i |B_i| means sum up the value of |B_i| for i = 1,2,3,4; namely, a compact way to write: ∑_i |B_i|   =   |B₁| + |B₂| + |B₃| + |B₄|. Similarly ∑_i,j means sum up over all pairs of values (i,j) = (1,2), (1,3), (1,4), (2,3), (2,4), (3,4).
   Problem: Write out this formula for n = 4 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 B₁ = {arrangements with at least 2 rings on right thumb}, B₂ = same for left thumb. Alternatively, use positive counting by cases.
   4. The rings are identical, with at most two allowed on each finger.
      Hint: Here, positive counting is not practical. Use PIE, with A = {all arrangements from part (b)}, B₁ = {at least 3 rings on finger 1}, . . . , B₁₀ = {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, and the order of the rings on one finger matters. (That is, D below R is different from R below D.) 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 (and again the order on each finger matters). Hint: Use positive counting.
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 B₁ = {rosters with P1 doing J1}, and similarly B₂, B₃.
   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.
4. Consider a grid of integer points (x,y) for 0 ≤ x,y ≤ 4, and paths through this grid with steps to the North (x,y) → (x+1,y), or to the East (x,y) → (x,y+1).
   1. How many paths from (0,0) to (4,4)?
   2. How many paths that pass through the point (2,3)?
   3. How many paths that do not pass through (2,3)?

1. The pairwise intersections involve choosing 2 of the 4 sets B₁, . . . ,B₄, and there are (4 | 2) = 6 ways to do this. Similarly, there are (4 | 3) triple intersections, and (4 | 4) = 1 quadruple intersection. The first two terms have (4 | 0) = 1 term |A| with no B_i's, and (4 |1) = 4 terms with a single B_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. An arrangement of rings is a list of 10 whole numbers adding up to 6. By the Multiplicity Transform, this corresponds to multi-sets of elements of 10 kinds (think of each ring as a choice of finger 1,2, . . . ,10, with repetition allowed). Ans: ((10 | 6)) = (15 | 6) = 5005.

2c. To count B₁ = {arrangements with at least 2 rings on right thumb}, begin by putting 2 rings on the right thumb, then distribute the remaining 4 rings on any of the 10 fingers (including extras on the right thumb). Thus, |B₁| = ((10 | 4)), and the same for |B₂|. Ans:

((10 | 6)) − ((10 | 4)) − ((10 | 4)) + ((10 | 2)).

2d. Let B_i = {arrangements with at least 3 rings on i^th finger}. Since there are only 6 rings total, we cannot have an intersection of more than 2 subsets B_i∩B_j. There are (10 | 2) possible pairs B_i∩B_j chosen from B₁, . . . , B₁₀, and |B_i∩B_j| = ((10 | 0)) = 1. Ans:

|A \ (B₁∪···∪B₁₀)|  =  |A| − ∑_i=1¹⁰ |B_i| + ∑_i,j |B_i∩B_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 B₁ = {arrangements with D on left thumb}, B₂ = {arrangements with D on right thumb}, B₃ = {arrangements with E on left thumb}, B₄ = {arrangements with E on right thumb}. Ans: 10⁶ − 4×9⁵ + 2×8⁴.
Positive counting: There are 8 choices for D, 7 for E, 8 for R, 7 for S, 6 for T, and 5 for C. Ans: 8×7×8⁴.

3a. A job roster is a list of all the jobs in some order. Ans: 6! .

3b. Note |B₁| = 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}, B₁ = {P1 doing J1}, B₂ = {P1 doing J2}, B₃ = {P2 doing J3}, B₄ = {P2 doing J4}.
Then |B₁| = 1×5×4×3×2×1, figuring the number of choices for Person 1, Person 2, etc. Similarly for |B₂| , |B₃|, |B₄|. Also |B₁∩B₃| = 1×1×4×3×2×1 , and similarly for |B₁∩B₄|, |B₂∩B₃|, |B₂∩B₄|, but |B₁∩B₂| = |B₃∩B₄| = 0. All triple intersections are empty.
Ans:     6! − 4×5! + 4×4!

4a. This is the city-street problem from previous HW. The Position Transform turns a path like ENNNEENE, a list of 8 steps with 4 N's and 4 E's, into a set S ⊂ [8] with |S| = 4, so there are (8 | 4) = 70 such paths.

4b. A path from (0,0) to (4,4) containing (2,3) splits into a path from (0,0) to (2,3), and another from (2,3) to (4,4). The first paths are counted by (5 | 2), and the second paths by (4−2 + 4−3 | 4−3) = (3 | 1). The total number of pairs is (5 | 2)(3 | 1) = 30.

4c. The complement of the set of (b) paths inside the set of (a) paths is counted by 70 − 30 = 40.

Reading: Ch 2.5, pp. 159-161.

1. As in previous HW, people P1, . . . , P6 are assigned jobs J1, . . . , J6, one job to each. Suppose P1 cannot do J1 or J2, and P2 cannot do J2 or J3. How many allowed job rosters?
2. 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?
   Extra Credit: What will happen if you invite them anyway?
3. Another problem on rings: 15 identical rings are to be put on 10 fingers. Count the ways to arrange the rings under the following conditions. In each case, use both positive counting and PIE to get the answer.
   1. There is at least one ring on each finger.
   2. There are exactly one or two rings on each finger.
4. Jellybeans
   1. A jar has unlimited jellybeans of 4 flavors. How many ways to choose an unordered handful of 18 beans. Example: 10 of the first flavor, 8 of the fourth flavor.
   2. Same, except the jar has only 5 of each flavor. Hint: Use PIE with the bad sets being the handfuls with too many beans of flavor 1,2,3,4.
   3. Count the ways to add 4 numbers between 0 and 5 whose sum is 18, that is a₁ + a₂ + a₃ + a₄ = 18, where a_i ∈ {0,1,2,3,4,5}. Example: 5 + 3 + 5 + 5 = 18.
   4. Count the ways to roll 4 distinct 6-sided dice with total 22. Example: 6 + 4 + 6 + 6 = 22.

1. A = {all rosters}, B₁ = {P1 does J1}, B₂ = {P1 does J2}, B₃ = {P2 does J2}, B₄ = {P2 does J3}. Then all terms in PIE are zero except: |A| = 6! , |B_i| = 5! , |B₁∩B₃| = |B₁∩B₄| = |B₂∩B₄| = 4! . Ans: 6! − 4×5! + 3×4! .

2. PIE: A = {sets of 5 from 10}, B₁ = {sets containing 1,2}, B₂ = {sets containing 2,3}, B₃ = {sets containing 3,4}. Clearly |A| = (10 | 5), and |B_i| = (8 | 3) since if two guests are fixed, this leaves 5−2 more to choose from 10−2. Similarly |B₁∩B₂| = (7 | 2), etc. Ans: (10 | 5) − (3 | 1)(8 | 3) + (7 | 2) + (6 | 1) + (7 | 2) − (6 | 1) = 126.

If you invite 1 & 2 anyway, 1 will sulk and not say a word all evening. If you invite 2 & 3, they will get into a ridiculous argument about politics. If you invite 3 & 4, don't even ask: that dude 4 is dangerous.

3a. PIE:

• A = {all arrangements of 15 rings on 10 fingers}
• B_i = {finger i has no ring} for i = 1, . . . , 10.
• Count: ((10 | 15)) − (10 | 1) ((9 | 15)) + (10 | 2) ((8 | 15)) − ··· − (10 | 9) ((1 | 15)) = 2002.

Positive counting: Since each finger has at least one ring, start by putting one ring on each finger, leaving 5 remaining rings to put on 10 fingers. Count: ((10 | 5)) = 2002. A much simpler method!

3b. PIE:

• A = {all arrangements of 15 rings on 10 fingers}
• B_i = {finger i has no ring} and B'_i = {finger i has ≥ 3 rings} for i = 1, . . . ,10 (20 bad sets in all).

This leads to an awful mess to compute the answer, because there are two types of bad sets, and you must account for all combinations of each. Yuck!
PIE/Postive hybrid:

• A = {all arrangements of 5 remaining rings on 10 fingers},
• B_i = {finger i has ≥ 2 of the 5 rings} for i = 1, . . . , 10
• Count: ((10 | 5)) − (10 | 1)((10 | 3)) + (10 | 2)((10 | 1)) = 252.

Positive counting: Start by putting one ring on each finger, leaving 5 remaining rings to put on 10 fingers, with at most one of the 5 on each finger. Count: (10 | 5) = 252.
Moral: Positive counting gives the simplest answer, if you can find the tricks to transform the data into a form that allows it.

4a. This is the model for Basic Problem 4: a handful with 18 beans of 4 kinds is a multiset of 1's, 2's, 3's, 4's. Ans: ((4 | 18)) = (21 | 18) = 1330.

4b. PIE: A = {all handfuls with 18 of 4 flavors}, B_i = {handfuls with more than 5 of the i^th flavor} for i = 1,2,3,4. We can count |B_i| by first choosing 6 beans of flavor i, then choosing the remaining 12 beans of any flavor (possibly more i's).

Ans: ((4 | 18)) − (4 | 1)((4 | 12)) + (4 | 2)((4 | 6)) − (4 | 3)((4 | 0))  =  10.

We can do this positively by noting that there must be either 5 of 2 flavors & 4 of 2 flavors, or 6 of 3 flavors and 4 of 1 flavor. By the Position Transform, this makes (4 | 2) + (4 | 1) = (5 | 2) = 10.

4c. This is the same problem as (b) via the Mutiplicity Transform.

4d. This is the same problem as (c) by a shift transform. That is, given d₁ + ··· + d₄ = 22 with d_i ∈ {1,2,3,4,5,6}, transform via a_i = d_i − 1 into a₁ + ··· + a₄ = 18 with a_i ∈ {0,1,2,3,4,5}.

Review previous two HW on PIE.

1. In class, we used the Sieve of Eratosthenes to count the primes less than 100. That is, we said that n ≤ 100 is prime if and only if n is not a multiple of 2,3,5, or 7, which are the primes ≤ √100 = 10. (Of course, we must also count 2,3,5,7 themselves as primes.) To count the numbers with these restrictions, we used PIE with:
   • A = {2,3,4,5,6, . . . ,100}
   • B₁ = {multiples of 2}
   • B₂ = {multiples of 3}
   • B₃ = {multiples of 5}
   • B₄ = {multiples of 7}
   1. Write out the resulting PIE formula from class, and evaluate it. Also, add 4 in order to count 2,3,5,7 themselves as primes. This tells the number of primes.
   2. Now, find the prime numbers themselves by a sieve method on this table. First, cross out 1 (since it does not count as prime). Next, circle the smallest remaining entry 2 (the first prime) and cross out all its multiples 4,6,8, . . . . Now repeat: circle the first remaining number 3 and cross out all its multiples 6,9,12, . . . . Doing this again for 5 and 7, the remaining numbers are all prime, since any composite ≤ 100 has a factor of 2,3,5 or 7. Does your result agree with the result of part (a)?
   3. Extra Credit: Let π(n) denote the number of primes ≤ n, so that part (a) computed π(100) = 25. There is no known formula for π(n), but the Prime number theorem gives an amazing approximation which gets more and more accurate as n gets large (i.e. it is an asymptotic formula).
      Look up and summarize a reference about the Prime number theorem. What is the expected approximation for π(100), and how well does it match the exact value we found? Plot some values comparing the true π(n) to the approximation.
   4. Extra Credit: The sequence of primes is quite mysterious. Could there be a "formula for primes", meaning a fairly simple function f(n) whose values f(1), f(2), f(3), . . . are all prime? For example, the polynomial f(n) = n² + n + 1 gives f(1) = 3 , f(2) = 7 , f(3) = 13 , but f(4) = 21 = 3×7, so this does not work. Could any polynomial f(n) work? What about Euler's polynomial n² − n + 41?
   5. Extra Credit: Use the primes ≤ 100 you found above to implement the Sieve of Eratosthenes for n = 100² = 10,000 on some kind of software.
2. In class, we discussed the Derangement Problem (Secret Santa). See also HHM p. 160.
   • Let d_n be the answer to this problem: the number of permutations (rearrangements or orderings) of n distinct objects such that no object is returned to its previous place.
   • In terms of Prob 1 above, this is the same as job rosters for n people in which Person i cannot do Job i, for all i = 1, . . . ,n.
   • Example: d₃ = 2, since the derangements of {1,2,3} are: (2,3,1) and (3,1,2); on the other hand, (3,2,1) is not a derangement, since 2 is in position 2.
   • In class, we used PIE with A = {all permutations} and B_i = {permutations fixing the i^th position}, to get the formula: d_n = n! − (n | 1) (n-1)! + (n | 2) (n-2)! − (n | 3) (n−3)! + ··· + (−1)ⁿ .
   Problems
   1. Show that you can re-write this as: d_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 their own name? Also compute this for n = 20.
   3. Prove that if n is very large, the probability that no one gets their 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. Hint: Use the Taylor series e^x = 1 + x + ^x2⁄_2! + ^x3⁄_3! + ···

1a. See HHM p. 159. The number of multiples of k less than or equal to n is ⌊n/k⌋, where ⌊x⌋ means to round a real number x downwards to the nearest integer. Thus |A₁| = ⌊100/2⌋ = 50, |A₂| = ⌊100/3⌋ = 33, etc.
The number of elements of A not divisible by 2,3,5,7 is thus:

|A \ (A₁∪ ··· ∪A₄|   =   99 − ⌊100/2⌋ − ⌊100/3⌋ − ⌊100/5⌋ − ⌊100/7⌋ + ⌊100/(2)(3)⌋ + ⌊100/(2)(5)⌋ + ⌊100/(2)(7)⌋ + ⌊100/(3)(5)⌋ + ⌊100/(3)(7)⌋ + ⌊100/(5)(7)⌋ − ⌊100/(2)(3)(5)⌋ − ⌊100/(2)(3)(7)⌋ − ⌊100/(2)(5)(7)⌋ − ⌊100/(3)(5)(7)⌋ + ⌊100/(2)(3)(5)(7)⌋

  =   99 − 50 − 33 − 20 − 14 + 16 + 10 + 7 + 6 + 4 + 2 − 3 − 2 − 1 − 0 + 0   =   21.

Adding 4 to account for 2,3,5,7 themselves, this gives 25 primes less than 100.

1b. The 25 primes less than 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 .

2a. In the original formula for d_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.

2b. For both cases the answer is d_n/n! ≅ 0.36788 up to many digits of accuracy.

2c. From the formula, the probabability d_n/n! = 1 − 1 + 1/2! − 1/3! + ··· + (−1)ⁿ/n!, which is the first n terms of the formula for e⁻¹ = 1/e. Since the Taylor series converges for all x, this approaches 1/e as n → ∞.

• Define the surjection number surj(n,k) to be the number of lists of n elements of k kinds, with at least one element of each kind. For example, surj(4,2) = 14 counts the lists:
  (1,1,1,2)   (1,1,2,1)   (1,2,1,1)   (2,1,1,1)
  (1,1,2,2)   (1,2,1,2)   (1,2,2,1)   (2,1,1,2)   (2,1,2,1)   (2,2,1,1)
  (2,2,2,1)   (2,2,1,2)   (2,1,2,2)   (1,2,2,2).
  Here we wrote all 2⁴ possible lists except for (1,1,1,1) and (2,2,2,2), in which 2 or 1 is missing.
• In general, we can compute surj(n,k) with PIE, using A = {all lists of n elements from k kinds}, B_i = {lists without the i^th kind}, so that:

  surj(n,k) = kⁿ − (k | 1)(k−1)ⁿ + (k | 2)(k−2)ⁿ − ··· + (−1)^k−1 (k | k−1)1ⁿ.

• We can transform the above lists into subsets of [n] = {1, . . . , n} using a Position Transform. For a list a = (a₁, . . . , a_n), let S₁ = {i where a_i = 1}, the positions of the 1's in the list a. Similarly, S₂ is the positions of the 2's in a, etc., giving disjoint sets with:

  S₁ ∪ ··· ∪ S_k = [n].

  In fact, surj(n,k) is the number of ways to split [n] into k non-empty disjoint subsets. In the example above, the 14 lists correspond to the ways to write S₁ ∪ S₂ = {1,2,3,4}, namely:
  {1,2,3}∪{4}   {1,2,4}∪{3}   {1,3,4}∪{2}   {2,3,4}∪{1}

  {1,2}∪{3,4}   {1,3}∪{2,4}   {1,4}∪{2,3}   {2,3}∪{1,4}   {2,4}∪{1,3}   {3,4}∪{1,2}

  {4}∪{1,2,3}   {3}∪{1,2,4}   {2}∪{1,3,4}   {1}∪{2,3,4}.

• Now let us ignore the order of S₁, . . . , S_k, so that in the example we count {1,2,3}∪{4} = {4}∪{1,2,3}, etc. The resulting count is called the Stirling partition number , pronounced "n partition k", and which I will write here as {n | k}. It is the number of ways to partition [n] into k non-empty disjoint subsets, without keeping track of which is the first subset, etc. For example, {4 | 2} = 7 counts the partitions:
  {1,2,3}∪{4}   {1,2,4}∪{3}   {1,3,4}∪{2}   {2,3,4}∪{1}

  {1,2}∪{3,4}   {1,3}∪{2,4}   {1,4}∪{2,3}.

• Since there are k! ways to re-order S₁, . . . , S_k, the Stirling number is ¹⁄_k! times the surjection number:
  {n | k}  =  ¹⁄_k! surj(n,k)  =  ¹⁄_k! (kⁿ − (k | 1)(k−1)ⁿ + (k | 2)(k−2)ⁿ + ··· + (k | k−1)1ⁿ).

Problems

1. Show that {n | 1} = {n | n} = 1 and {n | 2} = 2ⁿ⁻¹ − 1.
2. Use the definition to find a very simple formula for {n | n−1}.
3. Challenge Problem: The Deletion Transform allows us to discover and/or prove Pascal Triangle type recurrence formulas for the choose numbers (n | k) and the multi-choose numbers ((n | k)). Adapt this argument to discover and prove a recurrence for Stirling partition numbers, of the form:
   {n | k}  =  a{n−1 | k−1} + b{n−1 | k},
   where a and b are some coefficients which might involve n or k. The point is: if we remove the element n from the partiton S₁ ∪ ··· ∪ S_k = [n] to obtain a new partiton S₁' ∪ ··· ∪ S_k' = [n−1], we obtain two cases. In each case, a or b records the extra information needed to recover the orginal partition. Figure it out in an example.
   Check your recurrence formula by constructing the analog of Pascal's Triangle, and seeing if the entries match the explicit PIE formula for {n | k}.

• Reading: Ch 2.6 Method of Generating Functions, pp. 164−165.
• 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 = {}. The term xy corresponds to 1 ∉ S and 2 ∈ S, so S = {2}. The term yx corresponds to 1 ∈ S and 2 ∉S, so S = {1}. The term yy corresponds to 1 ∈ S and 2 ∈ S, so S = {1,2}.
  Algebraic expansion of terms corresponds to the choices of subsets as follows. We expand the binomial product (x+y)ⁿ into terms by repeatedly using the
  Algebraic Distributive Law:   (p+q)r  =  pr + qr.

• On the other hand, we generate subsets S by a sequence of binary choices:
  (1∉S or 1∈S) and (2∉S or 2∈S) and … and (n∉S or n∈S).
  We expand this logically into cases by repeatedly using the
  Logical Distributive Law:   (P or Q) and R ⇔ (P and R) or (Q and R).
  Example: "(hat or gloves) and coat" is logically equivalent to: "(hat and coat) or (gloves and coat)".
  Thus, the algebraic expansion perfectly parallels the logical choice of sets, with ''x'' corresponding to (i ∉ S);  ''y'' to (i ∈ S);  ''+'' to or ;  ''×'' to and ;  ''='' to ⇔ .
• Every term simplifying to x^n−ky^k corresponds to a subset S with |S| = k, so the coefficient of x^n−ky^k is the number of k-element subsets of n elements: namely,
  (x+y)ⁿ  =  (n | 0) xⁿ + (n | 1) xⁿ⁻¹y + (n | 2) xⁿ⁻²y² + ··· + (n | n) yⁿ,
  which is just 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.
• A variant is to write x⁰ = 1 for not taking a given element i and x¹ = x for taking it, producing the one-variable form of the Binomial Theorem:
  (1+x)ⁿ  =  1 + (n | 1)x + (n | 2)x² + ··· + (n | n−1)xⁿ⁻¹ + xⁿ.

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. Why does this show that the coefficient of x^3−ky^k is (3 | k)?
   2. Do the same for (x+y)⁴, getting 16 terms which show that the coefficient of x^4−ky^k is (4 | k).
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 Distributive Law 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. Translate the entire logical computation in (a) into the language of algebra, replacing 0A, 0B by x⁰;  1A, 1B by x¹;  2A, 2B by x²;   "or" by + ;  "and" by × ; ⇔ by = .  Start with (x⁰ + x¹ + x²) (x⁰ + x¹ + x²) and expand using the Algebraic Distributive Law. Finally, 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.
   4. What formulas would we get by applying this translation method to the case of multisets without any repeats, i.e. for ordinary sets inside a set of n elments?

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	{}	{3}	{2}	{1}	{2,3}	{1,3}	{1,2}	{1,2,3}

Thus, there are clearly (3|1) terms which are algebraically equal to x²y, and (3|2) terms equal to xy².

1b. To get (x+y)⁴, start with the previous result and 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 {}, the terms algebraically equal to x³y come from the sets with 1 element, the terms equal to x²y² come from the sets with 2 elements, etc.

2a. Applying the Logical Distributive Law twice:

(0A or 1A or 2A) and (0B or 1B or 2B)

  ⇔   [0A and (0B or 1B or 2B)] or [1A and (0B or 1B or 2B)] or [2A and (0B or 1B or 2B)]

  ⇔  

[0A and 0B] or [0A and 1B] or [0A and 2B] or

[1A and 0B] or [1A and 1B] or [1A and 2B] or

[2A and 0B] or [2A and 1B] or [2A and 2B] .

The final expanded expression has terms (outcomes) corresponding to the multisets M as follows:

term	0A & 0B	0A & 1B	0A & 2B	1A & 0B	1A & 1B	1A & 2B	2A & 0B	2A & 1B	2A & 2B
M	{}	{B}	{B,B}	{A}	{A,B}	{A,B,B}	{A,A}	{A,A,B}	{A,A,B,B}

2b. Applying the Algebraic Distributive Law twice to expland (x⁰+x¹+x²)², we get a symbol-for-symbol equivalent of the above computation:

(x⁰ + x¹ + x²) · (x⁰ + x¹ + x²)

  =   x⁰ (x⁰ + x¹ + x²) + x¹ (x⁰ + x¹ + x²) + x² (x⁰ + x¹ + x²)

  =  

x0x0 + x0x1 + x0x2 +

x1x0 + x1x1 + x1x2 +

x2x0 + x2x1 + x2x2 ,

where the terms correspond to the multisets M in the table. We write each term as x^k, where k is the size of M, and we collect like terms to get 1 + 2x + 3x² + 2x³ + x⁴.
Thus, the coefficient a_k of x^k is the number of M's with k elements, or the number of lunch-bag multisets with k pieces of fruit.

2c. (1 + (x+x²))²  =  1 + 2(x+x²) + (x+x²)²  =  1 + 2x + 2x² + (x² + 2xx² + x⁴)  =  1 + 2x + 3x² + 2x³ + x⁴.

2d. The choices for each element are multiplicity 0 (absent) or 1 (present), producing the factor (1+x). For all n elements, this gives (1+x)ⁿ, where each factor represents rejecting or accepting each element into the subset.

• Goal:   Get a numerical answer to a counting problem a = |A|, where A is a combinatorially interesting class of objects.
  
• Step 0.   Generalize the problem by seeing a as one of a sequence of similar numbers a₀, a₁, a₂, . . . . Usually, this means replacing some specific number in the definition of a by the index k = 0,1,2, . . . .
  
• Step 1.   Define the generating function:
  f(x)   =   a₀ + a₁x + a₂x² + ···   =   ∑_k≥0 a_k x^k .
  This is a polynomial if the sequence {a_k} is finite, or a Taylor series if the sequence is infinite. Use combinatorial properties of the sequence {a_k} to get a simple formula for f(x).
  • The Product Principle for the entire sequence {a_k}, analyzing the choice of an object of any size into a sequence of independent basic choices, can lead to a product formula for f(x). We translate this logical equivalence into the language of algebra.
    Generating Function Dictionary

    Logic	choose object of any size	⇔	basic choice adding size m	or	and
    Algebra	f(x) = ∑k≥0 akxk	=	xm	+	×

    
    Most often, m is a mulitplicity in a multiset, and k is the total size of the multiset.
  • If we can find f(x) in terms of any known Taylor series, we can replace the series by its function, such as 1 + x + x² + ···  =  ¹⁄_(1−x) .
  • A recurrence for a_k leads to an equation involving f(x) by manipulating sigma notation. Solve the equation for f(x).
• Step 2.   Given f(x), use algebra and calculus to expand it as a power series, thereby evaluating the coefficients a_k.
  • Multiply out by brute force, using Wolfram Alpha or a similar algebra system.
  • Taylor's coefficient formula: a_k = ^{f (k)(0)}⁄_k! , where f ^(k)(0) means the k^th derivative of f(x) evaluated at x = 0.
    Valid for all functions, but useful only for simple functions like f(x) = e^x, sin(x), or (1±x)^p.
  • Write f(x) as a sum of functions with known Taylor series.
    Partial fraction decomposition writes a rational function in terms of geometric series.
  Known series: Used by substituting z = an expression in x, such as z = x².
  • Binomial Theorem: (1+z)ⁿ  =  ∑ⁿ_k=0 (n | k) z^k , where (n | k) = ^nk⁄_k! is a choose number (binomial coefficient).
    General binomial: (a+b)ⁿ  =  ∑ⁿ_k=0 (n | k) a^n−k b^k .
  • Geometric series ¹⁄_(1−z)  =  1 + z + z² + ···  =  ∑_k≥0 z^k .   Finite series: 1 + z + z² + ··· + zⁿ  =  ^(1−zn+1)⁄_(1−z) .
  • Binomial with negative power: ¹⁄_(1−z)ⁿ  =  ∑_k≥0 ((n | k)) z^k , where ((n | k)) = (n+k−1 | k) = ^nk ⁄_k! is a multi-choose number.

Reading: Ch 2.6.1 pp. 166-167.

1. A trial example for the Method of Generating Functions (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. What is the highest valid n?
   • Step 1: Let f(x) = a₀ + a₁ x + a₂ x² + ··· + a₁₂x¹² be the generating function with coefficients a_k. We do not know a_k, so we do not yet know f(x). But use the Product Principle for a₀ + a₁ + ··· + a_n: (Choose any number of beads from drawer)  ⇔  (0G or 1G or 2G or 3G) and ··· where 0G means no Green, 1G means 1 Green, etc.
     Now translate this logical equivalence into algebra: replace each logical term with an algebraic one, as in the Toolkit. The left side is replaced with f(x), the unknown function which encodes all possible handfuls. The right side is an explicit product, which multiplies out so that each term algebraically equal to x^k corresponds to a particular handful of k beads; thus the coefficient of x^k is indeed a_k.
   • Step 2: Given the formula from Step 1, use algebra to expand f(x) and find the coefficient of x⁶, the number a we originally wanted. Here there is no algebraic trick for expanding; just type the formula for f(x) into the Wolfram Alpha, which will expand for you; the coefficients 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 Steps 1 & 2 as above.
   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. Consider a double deck of cards, with 2 copies of 52 distinct cards (see Ch 2.6.1). How many 5-card hands can be dealt from this deck?
   Step 0: a_k is the number of k-card hands from the double deck. Examples: a₁ = 52, since repeats are irrelevant with only 1 card;  a₂ = (52 | 2) + (52 |1), taking 2 distinct cards or 2 identical.
   1. Step 1: Use the Product Principle to find the generating function f(x) = ∑_k≥0 a_k x^k. That is, factor the choice of a hand into a sequence of independent basic choices (how many of each card). This chooses all hands with any number of cards, not just those with a fixed number k. Now translate this logical algorithm into algebra using the Generating Function dictionary above.
   2. 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.
   3. Look at your formula for a₅, and explain what each of the terms means combinatorially.
   4. Check your previous result by brute force: multiply out the formula for f(x) using Wolfram Alpha, and comparing the coefficient of x⁵.
   5. Compute a₆ by the same method, and explain the result combinatorially.
   6. Extra Credit: Is each of the above hands equally likely, assuming we deal in the usual way from the double deck? Actually, no: we cannot use this model to compute probablilities by counting! Explain, and give a valid model instead.
4. 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) = (1+x)¹⁰ = a₀ + a₁x + a₂x² + ··· + a₁₀x¹⁰. Use the formula from part (a) to compute a_k = (10 | k). Hint: Use the Chain Rule to differentiate (1+x)¹⁰.
   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 means that as you add more and more terms on the right (with x fixed), it becomes a better and better approximation to the value f(x) on the left. The equation might be valid only for small x, such as |x| < 1.
      Problem: Do some research to find some functions which can't be approximated by Taylor series.
   4. The coefficients of a Taylor series 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.
      Problem: Compute the Taylor series for f(x) = e^x, which is its own derivative: f '(x) = f(x).
   5. Compute the Taylor series for ¹⁄_(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(^π⁄₆) by substituting x = ^π⁄₆ into your Taylor series, and adding the terms up to x⁵. How good is the approximation?
5. Problem: What is the probability of getting 5 heads in 10 tosses of a coin (which lands heads or tails each time)?
   Do this problem by the Method of Generating Functions.
   Step 0: We want to count the number of ways to get 5 heads in 10 tosses. Generalize into a sequence of problems {a_k} by changing a specific number in the original problem to a general k, without changing the basic setup: a_k counts the number of ways to get . . .
   Step 1: Write an algorithm which describes all possible outcomes of 10 tosses as a sequence of choices separated by and. Translate this logical algorithm into an algebraic expression for the generating function f(x) = ∑_k a_kx^k. Replace each basic choice by x^m, where m is the number of heads added.
   Step 2: Expand f(x) by the Taylor coefficient formula, and explicitly find the coefficient of x^k, giving a formula for a_k. Can you explain the answer by combinatorial reasoning alone?
   Finally, find the probability asked for in the problem.

1. Step 0: Define a_k as the number of handfuls with k beads, where k = 0, . . . ,12 (since there are 12 beads altogether).
Step 1: (Choose 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⁴)

3a. Step 1: For a hand of any size, choose the multiplicity of each of the 52 distinct cards C₁, . . . , C₅₂:

(Choose a hand from double deck)   ⇔   (0C₁ or 1C₁ or 2C₁)  and  · · ·  and  (0C₅₂ or 1C₅₂ or 2C₅₂) .

f(x)  =  (1+x+x²) ··· (1+x+x²)  =  (1+x+x²)⁵²

3b. 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.

3c. Wolfram agrees with the count of 3,748,160 for a 5-card hand.

3d. In the expression a₅ = (52 | 3)(3 | 2) + (52 | 4)(4 | 1) + (52 | 5)(5 | 0), the last term (52 | 5) clearly counts 5-card hands with no repeated cards from the 52. The middle term (52 | 4)(4 | 1) means choose 4 distinct cards from 52, then choose one of them to repeat. The term (52 | 3)(3 | 2) means choose 3 distinct cards from 52, then choose 2 of them to repeat. This covers all possibilities of 0,1, or 2 repeated cards.

3e. Similarly choose distinct cards and repeats for a₆ = (52 | 3)(3 | 3) + (52 | 4)(4 | 2) + (52 | 5)(5 | 1) + (52 | 6)(6 | 0).

4a. f ''(x) = 2 a₂ + 3 (2) a₃ x + … so a₂ = f ''(0)/2 = f ⁽²⁾(0) / 2. In general, a_k = f ^k(0) / k!.

4b. f ^(k)(x) = 10^k(1+x)^10−k since (1+x)' = 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.

4c. 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 no Taylor series. In fact, no polynomial function (or Taylor series) looks like |x| very close to x = 0, since every polynomial has a smooth graph, whereas the graph of |x| has a corner.

4d. 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.

4e. 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.

4f. Tsin(x) = x − x³/3! + x⁵/5! − x⁷/7! + ···

4g. The exact value is sin(π/6) = 0.5 . The polynomial p(x) = x − x³/3! + x⁵/5! gives p(π/6) ≈ p(0.52) ≈ 0.497, which is pretty close. The point of the Taylor polynomial is that it computes a good approximation of sin(θ) for any given angle θ (provided θ is not too large), even when there is no simple exact answer. This is how a calculator computes trig functions.

5. Step 0: To generalize counting 5 heads in 10 tosses, it is easier to change 5 into k, leaving the basic setup of 10 tosses fixed: a_k is the number of ways to get k heads in 10 tosses. It would not be as natural to fix 5 heads while allowing any number k of tosses.

Step 1: (any outcome of 10 tosses) ⇔ (T₁ or H₁) and . . . and (H₁₀ or H₁₀), where T_i means the i^th toss is heads, H_i means the i^th toss is tails.
We translate T_i into x⁰ because a tail adds 0 to the number of heads; and we translate H_i into x¹, giving: f(x) = (x⁰ + x¹)¹⁰ = (1 + x)¹⁰.

Step 2: Taylor's Formula in #1b above gives: a_k = ^10k⁄_k! = (10 | k).
The number of outcomes of 10 tosses is 2¹⁰ by the Product Principle, which is a simplified version of our computation of f(x) with x = 1. The probability of k heads is thus (10 | k) / 2¹⁰.
The result a_k = (10 | k) is explained combinatorially by the Position Transform (Notes 1/20): each outcome with k heads is equivalent to the k-element set of positions of the k heads out of the 10 possible positions.

Reading: See Toolkit above.

• Ch 2.6.2 Multisets pp. 168-169.
• Ch 2.6.3 Changing Money, p 171-175.
• Taylor series: Calc Notes, Khan Academy, Wikipedia.

Notes

• Multichoose numbers ((n | k)) have an alternative formula coming from Generating Functions:
  f(x)  =  ∑_k≥0 ((n|k)) x^k  =  (1 + x + x² + ··· )ⁿ  =  (¹⁄_1−x)ⁿ  =  (1−x)⁻ⁿ,
  which has Taylor coefficients
  ((n | k))  =  ^f(k)(0)⁄_k! =  ^nk ⁄_k! ,
  where we use the rising power n^k = n(n+1)(n+2)···(n+k−1) with k factors.
• Changing money with pennies, nickels, dimes
  • Step 0: We consider d_k, the number of ways to make change for k cents with pennies, nickels, and dimes. For example d₁₀ = 4 counts the following handfuls of change: 10¢ (a dime); 2×5¢ (two nickels); 5¢ + 5×1¢ (a nickel and 5 pennies); 10×1¢ (10 pennies)
  • Step 1: We use the product principle: an arbitrary handful of change is equivalent to independently choosing the number of pennies, nickels, and dimes; and we replace each choice of coins worth m cents by x^m. This gives the generating function: f(x)  =  ∑_k≥0 d_kx^k  =  (1+x+x²+x³+···) (1+x⁵+x¹⁰+x¹⁵+···) (1+x¹⁰+x²⁰+x³⁰+···)
     =  ¹⁄_{(1−x)(1−x⁵)(1−x¹⁰)} .
  • Step 2: The difference-of-powers trick (Prob #3 below) gives: (1+x⁵)(1−x⁵)  =  1−x¹⁰     and     (1+x+x²+···+x⁹)(1−x)  =  1−x¹⁰ which allows us to make the three denominators equal: f(x)  =  ^{(1+x+x2+···+x9)}⁄_{(1+x+x²+···+x⁹)(1−x)}  ·  ^(1+x5)⁄_{(1+x⁵)(1−x⁵)}  ·  ¹⁄_(1−x¹⁰)

     =  ^{(1+x+x2+···+x9)}⁄_(1−x¹⁰) ·  ^(1+x5)⁄_(1−x¹⁰)  ·  ¹⁄_(1−x¹⁰)

     =  (1+x+x²+···+x⁹) (1+x⁵)  ·  ¹⁄_{(1−x¹⁰)³}

     =  (1+x+x²+x³+x⁴) (1+2x⁵+x¹⁰)  ·  ∑_j≥0 ((3 | j)) x^10j.

    Here we used the factorization: 1+x+x²+···+x⁹ = (1+x+x²+x³+x⁴)(1+x⁵), as well as the Binomial Theorem for negative powers, with z = x¹⁰.
    Now, the factor (1+x+x²+x³+x⁴) will have no effect on coefficients a_10j and a_10j+5, so multiplying out (1+2x⁵+x¹⁰)  ·  ∑_j≥0 ((3 | j)) x^10j gives:
    a_10j  =  ((3 | j)) + ((3 | j−1))  =  (j + 1)²,           a_10j+5  =  2((3 | j))  =  (j + 1)(j + 2).

    Finally, multiplying by (1+x+x²+x³+x⁴) shows a_10j = a_10j+1 = ··· = a_10j+4, and a_10j+5 = a_10j+6 = ··· = a_10j+9. These results are combinatorially mysterious: for example, how to see directly that there are 11² ways to make change for $1.00 with pennies, nickels, and dimes? Once again, the Method of Generating Functions is more clever with combinatorics than we are!

1. Consider a triple deck with three identical copies of 52 distinct cards. Find the number of distinct 5-card hands from the triple deck the way we did the double deck problem in class. Hint: Use the factorization: 1+x+x²+x³ = (1+x)(1+x²) to get an especially simple answer for a₅.
   Extra Credit: Explain this answer by combinatorial reasoning.
2. Practice for Step 2 of the Method: Find the Taylor series of the following functions as explicitly as possible, simplifying the coefficients as much as possible.
   Hint: Modify the known series in the Toolkit, substituting appropriate expressions for z.
   (a)   f(x) = ¹⁄_(1−x⁴)     (b)   f(x) = ¹⁄_(1−x)⁴     (c)   f(x) = ¹⁄_(1−x²)²     (d)   f(x) = ^x2⁄_(1−x)⁴     (e)   f(x) = ^(5−x)⁄_(1−x)²    
3. 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−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−z)² = ∑_k≥0 ((2 | k)) z^k with z = x².
   3. Do the same for ¹⁄_{(1−x)(1−x³)}. Hint: Multiply top and bottom by (1+x+x²), and use (1+x+x²)(1−x) = 1−x³.
4. Making change with pennies & nickels. 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 (two nickels), 5+1+1+1+1+1 (nickel and 5 pennies), and 1+···+1 (10 pennies).
   1. Compute an explicit formula for N_k by the Method of Generating Functions. Hint: For Step 1, use the Product Principle for a handful of change with any value. Replace each basic choice (how many pennies, how many nickels) by x^k, where k is the cents value of that choice. 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.
5. Rolling dice. A standard cubical die has faces numbered 1,2, . . . ,6.
   1. Let a_k be the number of ways to roll a total of k = 2,3, . . . ,12 with two dice. For example, you can roll a 3 as 1+2 or 2+1, so a₃ = 2. There is a total of 6×6 = 36 possible rolls, so the probability of k = 3 is 2/36.
      Compute a₂, . . . , a₁₂ by generating functions, and make a table of probabilities for the rolls.
      Step 1: Use the product principle see an arbitrary roll as a pair of independent choices (the value of each die). Translate this into algebra, replacing each basic choice which adds m to the total by x^m.
      Step 2: Use Wolfram alpha to expand f(x) into a series.
   2. Sicherman dice are a pair of cubical dice with special number labels instead of the standard 1,2, . . . ,6: one has labels 1,2,2,3,3,4, the other has 1,3,4,5,6,8. Show that the probability of rolling k = 2, . . . ,12 with these dice is the same as the probability for a standard pair.
      Extra Credit: Explain how to discover the Sicherman dice by getting Wolfram alpha to factor the generating function for standard dice from part (a).
   3. Do the same as part (a) for rolls of 3 dice.
   4. Now part (c) without a computer. For Step 2, use the identity x+x²+···+x⁶ = ^x(1−x6)⁄_(1−x), then expand using the Binomial Theorem for positive and negative powers.
   5. Extra Credit: Use generating functions to find a formula for the number of ways to roll k with n dice. Hint: You may use the definition ((n | k)) = 0 for k < 0.

1. Step 0: Let a_k count the possible k-card hands from a triple deck.

Step 1: For each distinct card C, we have the choice (0C or 1C or 2C or 3C). For the 52 distinct cards, this produces f(x)  =  (1+x+x²+x³)⁵²

Step 2: Use the Binomial Theorem to expand:

f(x)  =  (1+x+x²+x³)⁵²

 =  (1+x)⁵²(1+x²)⁵²,

 =  ( ∑⁵²_k=0 (52 | k) x^k )   ( ∑⁵²_j=0 (52 | j) x^2j )

The x⁵ terms are:

(52 | 5)x⁵ (52 | 0)x⁰  +  (52 | 3)x³ (52 | 1)x²  +  (52 | 1)x¹ (52 | 2)x⁴ ,

so a₅ = (52 | 5) + (52 | 3)(52 | 1) + (52 | 1)(52 | 2).
This must have a combinatorial explanation, corresponding to three cases with a product principle for each, but it is not obvious just how to do this. Once again, generating functions substitute algebra for fairly subtle combinatorial thinking.

2a. 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.

2b. Binomial with negative exponent: f(x) = ∑_k≥0 ((4 | k)) x^k, so

a_k  =  ((4 | k))  =  (k+3 | k)  =  (k+3 | 3)  =  (k+3)(k+2)(k+1)/6 .

2c. Binomial with negative exponent: f(x) = ∑_k≥0 ((2 | k)) x^2k, so a_2k = ((2 | k)) = k+1 and a_2k+1 = 0.

2d. 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.

2e. f(x) = (5−x) ∑_k≥0 ((2 | k)) x^k = ∑_k≥05 ((2 | k)) x^k − ∑_k≥0 ((2 | k)) x^k+1
   = ∑_k≥05 ((2 | k)) x^k − ∑_k≥0 ((2 | k−1)) x^k    =    ∑_k≥0 [5 ((2 | k)) − ((2 | k−1))] x^k ,

   so a_k = 5 ((2 | k)) − ((2 | k−1)) = 5(k+1) − k = 4k + 5.

3a. This follows just from multiplying out and cancelling. Alternatively, you can deduce it from (1−xⁿ) / (1−x) = 1 + x + x² + ··· + xⁿ⁻¹ (the finite geometric series summation from an old HW), with x = b/a, after clearing denominators.

3b. 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.

3c. 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.

4a. Step 1:     (choose a handful of change of any value)  ⇔  (0P or 1P or . . . ) and (0N or 1N or . . . )

is translated algebraically as:

f(x) = ∑_k≥0 N_kx^k = (1+x+x²+x³+···) (1+x⁵+x¹⁰+x¹⁵+···) = 1 / (1−x)(1−x⁵),

replacing each choice of coins with x^m, where m is the value of the coins.

Step 2: Just as for 3(b),(c), we get N_5j = N_5j+1 = N_5j+2 = N_5j+3 = N_5j+4 = j+1.

4b. 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.

5a. (Roll two dice)  ⇔  (1 OR 2 OR . . . OR 6) AND (1 OR 2 OR . . . OR 6). Translating into algebra: f(x)  =  (x + x² + ··· + x⁶)². Typing this into Wolfram Alpha as: "expand (x+x^2+x^3+x^4+x^5+x^6)^2", we get:

f(x)  =  x²+2x³+3x⁴+4x⁵+5x⁶+6x⁷+5x⁸ + 4x⁹+3x¹⁰+2x¹¹+x¹². The coefficient of x^k is the desired a_k, and the probabilities are a_k / 36.

5b. Regardless of their labels, each of the dice can land on any of their 6 faces, making 6² = 36 equally likely cases. Let s_k be the number of ways to roll a total of k with Sichermann dice. For example, s₃ = 2, which can appear as either of the 2's on the first die, and 1 on the second die. Using similar reasoning as before, the generating function is:

f(x)  =  ∑_k=2¹² s_kx^k  =  (x + 2x² + 2x³ + x⁴) (x + x³ + x⁴ + x⁵ + x⁶ + x⁸) . Expanding this by Wolfram, we find the same function as in part (a), which proves that the probabilities are also the same.

5c. Similar to part (a):

f(x)  =  (x + x² + ··· + x⁶)³
 =  x³+3x⁴+6x⁵+10x⁶+15x⁷+21x⁸+25x⁹+27x¹⁰+27x¹¹+25x¹²+21x¹³+15x¹⁴+10x¹⁵+6x¹⁶+3x¹⁷+x¹⁸.

5d.   f(x)   =   x³ (1−x⁶)³ / (1−x)³   =   (x³ − 3x⁹ + 3x¹⁵ − x²¹) × ∑_j≥0 ((3 | j)) x^j.
Multiplying out and collecting x^k terms, we get:

a_k   =   ((3 | k−3)) − 3((3 | k−9)) + 3((3 | k−15)) − ((3 | k−21)), where we define ((3 | k)) = 0 for k < 0.
It is not clear why this is zero for k > 18, but we may simplify using ((3 | k)) = (k+3−1 | k) = (k+2 | 2) to check that:

a19	=	((3 | 16)) − 3((3 | 10)) + 3((3 | 4)) − 3((3 | −3))
	=	(18 | 2) − 3(12 | 2) + 3(6 | 2) − 0   =   153 − 198 + 45   =   0 .

This weird formula again illustrates the power of Generating Functions to give answers we never would have thought of combinatorially.

• Reading: HHM 2.6.5 pp. 181-183. Partial fractions review: my notes, Khan Academy.
• We say a sequence a₀, a₁, a₂, . . . is defined recursively if we start with a given base value a₀, and define each successive a_k in terms of the previous a_k−1, a_k−2, . . . We wish to solve the recurrence equation, that is to give an explicit, non-recursive formula for a_k.
• Trivial Example: a₀ = 3 and a_k = 2a_k−1, giving the numbers 3, 6, 12, 24, 48, . . . . This case is easy to solve: a_k = 3(2^k) for k ≥ 0, an exponential sequence. Most recurrences are much harder to solve. Generating Functions will often work, with some new techniques in each step.
• Example: a_k = 2a_k−1 + 1 for k ≥ 1, starting with a₀ = 1, so the sequence is 1, 3, 7, 15, 31, . . .  Do you see a pattern?
  • Step 1: Use the recurrence for a_k in terms of smaller a's to write the generating function f(x) as a more complicated expression in terms of f(x). (The first term a₀ is special, because the recurrence does not hold for k = 0.)
    f(x)   =   ∑_k≥0 a_kx^k   =   a₀ + ∑_k≥1 (2a_k−1+1)x^k
      =   1 + 2x ∑_k≥1 a_k−1x^k−1 + x ∑_k≥1 x^k−1
      =   1 + 2x f(x) + ^x⁄_(1−x)   =   2x f(x) + ¹⁄_{(1−x) .}
    Thus, f(x) satisfies the equation f(x) = 2x f(x) + ¹⁄_(1−x). If we write y = f(x), this is y = 2xy + ¹⁄_(1−x), which we may easily solve to get a non-recursive formula for y = f(x):
    f(x)  =  ¹⁄_{(1−2x)(1−x)} .

  • Step 2: Use the partial fraction expansion of f(x) into geometric series to explicitly find its Taylor coefficients, and therefore get a formula for a_k.
    y  =  f(x)  =  ¹⁄_{(1−2x)(1−x)}  =  ^A⁄_(1−2x) + ^B⁄_(1−x)
    We find A, B by multiplying both sides by (1−2x)(1−x) to get:
    1  =  A(1−x) + B(1−2x)   for all x.
    Setting x = ½ gives 1 = A(½) + B(0) and A = 2. Setting x = 1 gives 1 = A(0) + B(−1) and B = −1. Thus we get a sum of geometric series:
    f(x)  =  ²⁄_(1−2x) + ⁻¹⁄_(1−x)  =  2 ∑_k≥0 (2x)^k − ∑_k≥0 x^k
    
     =  ∑_k≥0 (2)2^kx^k − ∑_k≥0 x^k  =  ∑_k≥0 (2^k+1−1) x^k.
    The explicit formula is a_k = 2^k+1 − 1, which indeed matches the values computed above, e.g. a₄ = 31 = 2⁴⁺¹ − 1. That is the pattern.

1. Partial fraction decomposition is a technique to find the series of a rational function. A typical example is below.
   1. Let f(x)   =   ^(x−5)⁄_(2x²+x−1). Find the vertical asymptotes, which are the roots of the denominator.
   2. Find the two simple functions ¹⁄_(1−γx) and ¹⁄_(1−δx) which have the same vertical asymptotes as f(x). Write   f(x)   =   ^g(x)⁄_{(1−γx)(1−δx)}   for an appropriate numerator g(x).
      Hint: For a given γ, find the asymptote of ¹⁄_(1−γx). Now, for our given vertical asymptotes x = −1, x = ½, what are the values γ, δ that produce these asymptotes? The polynomial (1−γx)(1−δx) has the same roots as 2x²+x−1, so the two differ only by a constant factor, which can be absorbed into the numerator g(x).
   3. We want to find constants A,B such that f(x)   =   ^(−x+5)⁄_{(1+x)(1−2x)}   =   ^A⁄_(1+x) + ^B⁄_(1−2x). To do this, we combine terms on the right hand side: ^(−x+5)⁄_{(1+x)(1−2x)}   =   ^{(A(1−2x) + B(1+x))}⁄_{(1−x−2x²) ;} then multiply out: −x+5   =   A(1−2x) + B(1+x)   for all x. Now substitute any values of x, for example:  x = −1 and x = ½, and solve the resulting equations for A, B.
   4. For the A,B you found in part (c), combine terms in  ^A⁄_(1+x) + ^B⁄_(1−2x)  and verify that it is indeed f(x).
   5. Write out the geometric series for  ^A⁄_(1+x)  and  ^B⁄_(1−2x) , and find the explicit Taylor series of f(x).
2. Solve the following recurrences.
   1. Base value a₀ = 3, recurrence a_k = 2a_k−1 − 1 for k ≥ 1.
   2. Base value a₀ = 3, recurrence a_k = 3a_k−1 − 2^k for k ≥ 1.
3. Solving general recurrences. Use generating functions to solve each of the following recurrence equations, which involve some given constants b,c,r, and also any given base value a₀. Each recurrence is valid for k ≥ 1.
   (a)   a_k = a_k−1 + c              (b)   a_k = b a_k−1 + c r^k              (c)   a_k = b a_k−1 + c k
   Hints:
   1. The solution a_k = a₀ + ck is obvious, but I want you to see what it means in terms of generating functions.
   2. Use the same reasoning as in #2a, which is the special case b = 2, c = −1, r = 1; or in #2b, which is the special case b = 3, c = −1, r = 2. Test some more examples by taking specific b, c, r, a₀, computing a few terms of the series by hand, and seeing that they agree with the general formulas.
   3. You will need the know the formula for ∑_k≥0 k x^k, which you can get from differentiating both sides of the geometric series formula, or from adapting the known series 1/(1−x)².

1a,b. Factoring or using the quadratic formula on the denominator gives the vertical asymptotes x = −1, ½, which are shared by the geometric-series functions ¹⁄_(1+x) and ¹⁄_(1−2x). Since (1+x)(1−2x) has constant term 1, whereas the denominator has constant term −1, we must have 2x²+x−1 = −(1+x)(1−2x), so that:

f(x)   =   ^(x−5)⁄_{−(1+x)(1−2x)}   =   ^(−x+5)⁄_{(1+x)(1−2x)} .

1c,d. Substituting x = −1 gives   1+5 = A(1 + 2), so A = 2; and substituting x = ½ gives −½ + 5 = B(³⁄₂), so B = 3. We may check that   f(x)   =   ²⁄_(1+x) + ³⁄_(1−2x)  by putting over a common denominator and comparing with the previous form of f(x).

1e.   f(x)   =   ∑_k≥0 2(−x)^k + ∑_k≥0 3(2x)^k   =   ∑_k≥0 [2(−1)^k + 3(2^k)] x^k, so a_k = 2(−1)^k + 3(2^k)

2a. See class notes, where I solved a similar recurrence.

Step 1: f(x)  =  a₀ + ∑_k≥1 a_kx^k  = 3 + ∑_k≥1 (2a_k−1−1)x^k

Notice that the summation is for k ≥ 1 since the recurrence is not valid for the k = 0 term a₀. Continuing:

f(x)   =   3 + 2x ∑_k≥1a_k−1x^k−1 − ∑_k≥1x^k   =   3 + 2x f(x) − 1/(1−x) + 1.

Notice that the last summation is almost a geometric series, but with the k = 0 term missing, which accounts for the +1 at the end.
We have: f(x) = 2x f(x) + 4 − 1/(1−x), which we solve to get: (1−2x) f(x) = (4−4x)/(1−x) − 1/(1−x) and finally: f(x) = (3−4x)/(1−2x)(1−x).

Step 2: By partial fraction decomposition,

f(x)   =   2/(1−2x) + 1/(1−x)   =   2 ∑_k≥0 (2x)^k + ∑_k≥0 x^k . Distributing (2x)^k = 2^kx^k and collecting x^k terms, we find the coefficient is: a_k = 2^k+1 + 1.
Check: This agrees with the first few values a₀ = 3, a₁ = 5, a₂ = 9, a₃ = 17.

2b. Step 1: f(x)   =   a₀ + ∑_k≥1 a_kx^k  =  3 + ∑_k≥1 (3a_k−1−2^k)x^k

The summation is for k ≥ 1 since the recurrence is not valid for the k = 0 term.

f(x)   =   3 + 3x ∑_k≥1a_k−1x^k−1 − ∑_k≥12^kx^k   =   3 + 3x f(x) − 1/(1−2x) + 1.

The final +1 is because the geometric series ∑_k≥12^kx^k is missing its k = 0 term.
We have: f(x) = 3x f(x) − 1/(1−2x) + 4 = 3x f(x) + (3−8x)/(1−2x), which we solve to get: f(x) = (3−8x) / (1−2x)(1−3x).

Step 2: By partial fraction decomposition,

f(x)   =   2/(1−2x) + 1/(1−3x)   =   2 ∑_k≥0 (2x)^k + ∑_k≥0 (3x)^k. Distributing and collecting x^k terms, we find the coefficient is: a_k = 2^k+1 + 3^k.
Check: This agrees with the first few values a₀ = 3, a₁ = 7, a₂ = 17, a₃ = 43.

3a. Recurrence: a_k = a_k−1 + c. We do this by generating functions just for practice.

  f(x)   =    a₀ + ∑_k≥1 a_k x^k   =    a₀ + ∑_k≥1 (a_k−1 + c) x^k

  =    a₀ + x ∑_k≥1 a_k−1x^k−1 + cx ∑_k≥1 x^k−1   =    a₀ + x f(x) + cx/(1−x)

Thus: f(x) = a₀/(1−x) + cx/(1−x)²   =    a₀ + ∑_k≥1 a₀ x^k + ∑_k≥0 c ((2 | k)) x^k+1
= a₀ + a₀x + c((2|0))x + a₀x² + c((2|1))x² + ··· Final answer: a_k = a₀ + c ((2 | k−1)) = a₀ + c (k | k−1) = a₀ + ck , which is what we expected.

3b. Recurrence: a_k = b a_k−1+ c r^k. Here the answer is not at all obvious. Step 1 gives:
f(x) = a₀ + bx f(x) + crx/(1−rx)   so   f(x) = a₀/(1−bx) + crx/(1−rx)(1−bx)
Partial fractions: crx/(1−rx)(1−bx) = A/(1−rx) + B/(1−bx) .
Clear denominators, substitute x = 1/b, 1/r , get A = cr/(r−b), B = −cr/(r−b).
Final answer:   a_k = a₀b^k + A r^k + B b^k   =   a₀b^k + cr(r^k − b^k)/(r−b).
Check: For the case in Prob #2, we have b = 2, c = r = 1, a₀ = 1, so a_k = 1(2^k) + 1(1^k−2^k)/(1−2) = 2^k − (1−2k) = −1 + 2^k+1 as we got in #2.

3c. Recurrence: a_k = b a_k−1 + ck . This one is harder than I would give on a test.
First, differentiating (1−x)⁻¹ = ∑_k≥0 x^k gives: (1−x)⁻² = ∑_k≥0 kx^k−1, so x/(1−x)² = ∑_k≥0 kx^k.
Equation: f(x) = a₀ + bx f(x) + cx/(1−x)²   so   f(x) = a₀/(1−bx) + cx/(1−bx)(1−x)²
Partial fractions: cx/(1−bx)(1−x)² = A/(1−bx) + B/(1−x)² + C/(1−x) .
Clear denominators and substitute x = 1/b, x = 1 to get A = cb/(b−1)² ,   B = −c/(b−1) .
Then we have:   C/(1−x) = cx/(1−bx)(1−x)² − A/(1−bx) − B/(1−x)² = −c/(b−1)²(1−x) .
Final answer:   a_k = (a₀ + cb/(b−1)²) b^k − ck/(b−1) − cb/(b−1)² .
Check: Compare with obvious formulas in the case b = 0 and in the case c = 0 .

• Reading: Ch 2.6.4 pp. 177-179.
• Step 0:We defined the Fibonacci numbers by the initial values F₀ = 0, F₁ = 1, and the recurrence: F_k = F_k−1 + F_k−2   for k ≥ 2 . Thus, the sequence starts:

  F0	F1	F2	F3	F4	F5	F6	F7	F8
  0	1	1	2	3	5	8	13	21

• Step 1: We computed the generating function as follows:

  f(x)	=	F0 + F1x + ∑k≥2 Fkxk
  	=	x + ∑k≥2 (Fk−1 + Fk−2)xk
  	=	x + x ∑k≥2 Fk−1xk−1 + x2 ∑k≥2 Fk−2xk−2
  	=	x + x (F1x + F2x2 + F2x3 + ···) + x2 (F0 + F1x + F2x2 + ···)
  	=	x + x (f(x) − F0) + x2 f(x)
  f(x)	=	x + x f(x) + x2 f(x)

  Solving the last equation for f(x), we get:
  f(x)   =   ^x⁄_{(1−x−x²)} .

• Step 2: Finding the Taylor series (see HW below), we obtained the amazing
  Binet formula:       F_k  =  ¹⁄_√5(φ^k − (−ψ)^k) ,                
  where the constants are the two reciprocal values of the Golden Ratio:
  φ = ½(√5 + 1) ≅ 1.618     and     ψ = ¹⁄_φ = ½(√5 − 1) ≅ 0.618

1. Explain the mistakes in each of the following WRONG computations.
   1. ∑_k≥0 3^kx^k   =   3^k ∑_k≥0 x^k  =  ^3k⁄_(1−x) ??   Hint: Focus on the meaning of "k".
   2. ¹⁄_(1−3x)  −  ¹⁄_(1−2x)  =  ∑_k≥0 3x^k − ∑_k≥0 2x^k  =  ∑_k≥0 (3−2)x^k  =  ∑_k≥0 x^k ??
   3. If a₀ = 1 and a_k = 2a_k−1 + 1 for k ≥ 1, then:
         f(x)  =  ∑_k≥0 a_kx^k  =  a₀ + ∑_k≥1 (2a_k−1+1)x^k  =  1 + ∑_k≥1 2x^k + ∑_k≥1 x^k  =  1  +  ^x⁄_(1−2x)  +  ^x⁄_(1−x) ??
2. Practice: Solve the following recurrence using Generating Functions.
   a₀ = a₁ = 1,   a₂ = 2,      a_k = 3a_k−1− 3a_k−2+ a_k−3   for   k ≥ 3 .

3. The Golden Ratio ψ is a special number which supposedly gives the most beautiful proportions for a rectangle. It is defined by the following property: if we divide a rod of length 1 into parts ψ and 1−ψ, then the ratio of ψ to the whole length 1 is equal to the ratio of the other part 1−ψ to ψ. That is:     ψ/1 = (1−ψ)/ψ .
   1. Solve this equation for ψ. Also compute φ = 1/ψ, and rationalize the denominator. Either ψ or φ can be called the Golden Ratio. Give decimal approximations for ψ, φ.   Note: Greek letter ψ is psi, and φ is phi.
   2. Show that: φψ = 1, φ + ψ = √5 , and φ − ψ = 1.
   3. Write the roots of the polynomial 1−x−x² in terms of ψ and φ.
4. Step 2 for the Fibonacci sequence. Show that the vertical asymptotes of the Fibonacci f(x) = ^x⁄_{(1−x−x²)} are x = −φ and x = ψ. Determine the partial fraction decomposition f(x) = ^A⁄_(1−ax) + ^B⁄_(1−bx), and find the explicit Taylor series of f(x), which gives Binet's formula.
   Hint: In your calculations, use that φ = ¹⁄_ψ , φ+ψ = √5 , φ−ψ = 1.
5. Binet formula for Fibonacci numbers:   F_k  =  ¹⁄_√5(φ^k − (−ψ)^k).
   1. In this formula, the irrational square roots somehow cancel, leaving only whole numbers, the F_k's. Check Binet's formula by hand for k = 0, 1, 2, 3.
   2. Since |ψ| < 1, its powers become very small, so that the second term in the above formula is only a small correction. In fact: F_k = round(φ^k / √5), where round( ) means round to the nearest integer. This confirms the intuition that F_k should grow exponentially, since it is a model of (delayed) reproduction.
      Problem: On your calculator, compute φ^k / √5 for k = 1,2, . . . ,12. How close are they to the Fibonacci numbers? Do you have to round up or down? Explain the direction of the rounding by looking at the original formula.
   3. Use the rounding formula and your calculator to compute F₄₀ exactly. Give a general formula for the number of digits in the number F_k.
   4. Prove Binet's Formula by induction, starting with above computations for k = 0,1; then for k ≥ 2, show that the formula for F_k−2 and F_k−1 implies the formula for F_k. Use the equation satisfied by φ, −ψ.
6. Extra Credit: Arithmetic properties of F_k.
   1. For which k is F_k an even number? Prove your answer by induction, but be careful, since the parity of the next step is not necessarily the same as the previous step.
   2. Prove that if nk is a multiple of n, then F_nk is a multiple of F_n . There is a proof using Binet's formula, but be careful to show the quotient ^F_nk⁄_Fn is an integer (no √5's).
   3. Prove that the Fibonacci sequence has a repeating pattern of remainders upon division by a fixed F_n: in terms of modular arithmetic,
      F_nk+ℓ  ≡  (F_n−1)^k F_ℓ  mod  F_n ,
      for all k ≥ 0 and ℓ = 0,1, . . . , n−1, and in particular F_nk ≡ 0 mod F_n. This can probably be done by induction or Binet's formula. As usual, the easiest analysis is by generating functions, this time with coefficients considered modulo F_n:
      f(x)  =  ^x⁄_{(1−x−x²)}  ≡  ^{(F₀+F₁x+···+F_n−1xn−1)}⁄_{(1−Fn−1xⁿ)}  mod F_n .
      Prove this by clearing denominators. Then expand the two sides and equate coefficients to obtain the formula.
7. Extra Credit: F_k in terms of binomial coefficients. If we use different algebraic tricks on the generating function of the Fibonacci numbers, we get another formula for F_k.
   Factoring out an x from the generating function, we get: f(x)/x  =  ∑_k≥0 F_k+1 x^k  =  ¹⁄_{(1−(x+x²)) .} Expand this in two stages. First use the geometric series formula ¹⁄_(1−z) = ∑_j≥0 z^j with z = x+x² . Then expand (x+x²)^j by the Binomial Theorem. You should get a double sum of the form: f(x)/x  =  ∑_j≥0 ∑^j_i=0 ··· . You may prefer to write this out in a table of terms with rows corresponding to j = 0, 1, 2, . . . and columns corresponding to i = 0, 1, . . . , j.
   Now collect terms with like powers of x : that is, add up the coefficients with no x, with x¹, x², x³, until you see the pattern. Or use summation notation, and collect the terms corresponding to all values of j and i which produce a total exponent equal to k. Obtain a formula for F_k as a sum of certain choose numbers (j | i). Write your formula explicitly for k = 1, . . . ,6 .
8. Extra Credit: A counting model for F_k. A hopscotch board is a sequence of columns, each with 1 or 2 squares (see picture HHM p.181 #10). Let h_k be the number of boards with a total of k squares. For example, h₄ = 5 counts the 4-square boards:
   
   Equivalently, h_k is the number of ways of splitting k into a sum of 1's and 2's, where order matters, so we can write the 4-square boards as:
   1+1+2     1+2+1     2+1+1     2+2     1+1+1+1.
   Also let h₀ = 1.
   Find the generating function of h_k using the Sum and Product Principles. Choosing any sum of 1's and 2's is equivalent to the following: first decide how many 1-or-2 numbers you will add (say, j numbers), then choose 1 or 2 for each of the j numbers. This choice will contribute to h_k where k is the sum of the 1-or-2 numbers chosen. Sum over all j ≥ 0 to get the generating function of h_k's . You should get a kind of geometric series 1 + z + z² + ··· , which you can sum using the usual formula. Now use the result to compare h_k to the Fibonacci numbers.
9. Extra Credit: Periodic recurrences. Consider the sequence (a_k)_k≥0 defined recursively by:
   a_k = a_k−1 − a_k−2 .
   Show that for any choice of initial values a₀, a₁, this sequence repeats itself with period 6; that is, a_k+6 = a_k. Do this by direct computation, taking a₀ and a₁ as unspecified constants, and also using the fact that the denominator of the generating function is a cyclotomic polynomial. Explain how to produce many other similar periodic recurrences, and try to classify all of them.

1a. We should write: ∑_k≥0 3^kx^k   =   3⁰x⁰ + 3¹x¹ + 3²x² + ···   =   1 + 3x + (3x)² + ···   =   ¹⁄_(1−3x).
The letter "k" is a dummy variable that takes on a particular value k = 0,1,2, . . . in each successive term of the summation ∑_k . It has no meaning outside the summation, and the correct final formula cannot have any k's in it.

1b. We should write: ¹⁄_(1−3x)  =  ∑_k≥0 (3x)^k  =  ∑_k≥0 3^kx^k, and similarly for ¹⁄_(1−2x) , giving total coefficient a_k = 3^k − 2^k.

1c. After the third equals sign, the a_k just disappeared from the expression, which is wrong since in general a_k ≠ 1. After the fourth equals sign, the expression 2x^k was confused with (2x)^k.

2. Step 1:  

f(x)	=	a0 + a1x + a2x2 + ∑k≥3 akxk
	=	1 + x + 2x2 + ∑k≥3 (3ak−1− 3ak−2+ ak−3)xk
	=	1 + x + 2x2 + 3x ∑k≥3 ak−1xk−1 − 3x2 ∑k≥3 ak−2xk−2 + x3 ∑k≥3 ak−3xk−3
	=	1 + x + 2x2 + 3x (a2x2 + a3x3 + ···) − 3x2 (a1x + a2x2 + ···) + x3 (a0 + a1x + ···)
	=	1 + x + 2x2 + 3x (f(x) − a0 − a1x) − 3x2 (f(x) − a0) + x3 f(x)
	=	1 + x + 2x2 + 3x f(x) − 3x − 3x2 − 3x2 f(x) + 3x2 + x3 f(x)
f(x)	=	1 − 2x + 2x2 + 3x f(x) − 3x2 f(x) + x3 f(x)

Solving the last equation for f(x), we get: f(x)   =   (1 − 2x + 2x²) / (1 − 3x + 3x² − x³)   =   (1 − 2x + 2x²) / (1 − x)³ . Step 2: Using the Negative Binomial formula ¹⁄_(1−x)ⁿ  =  ∑_k≥0 ((n | k)) x^k

f(x)	=	(1 − 2x + 2x2) ∑k≥0 ((3 | k))xk
	=	((3 | 0)) +   ((3 | 1))x +   ((3 | 2))x2 + ((3 | 3))x3 + ··· − 2((3 | 0))x − 2((3 | 1))x2 − 2((3 | 2))x3 + ··· + 2((3 | 0))x2 + 2((3 | 1))x3 + ···

Collecting terms, we find that a_k = ((3 | k)) − 2((3 | k−1)) + 2((3 | k−2)) = ½(k² − k + 2) for all k ≥ 0.

3a. The equation reduces to ψ² = 1−ψ, or ψ²+ψ−1 = 0, which has roots (−1±√5)/2. The positive root is ψ = (√5−1)/2 .

Also φ = 1/ψ = 2/(√5−1) = 2(√5+1) / (√5−1)(√5+1) = 2(√5+1) / (5−1) = (√5+1) / 2. The approximate values are ψ ≅ 0.6 , φ ≅ 1.6 .

3b. The roots are ψ and −φ.

4. The simple functions with the asymptotes x = ψ and x = −φ are 1/(1 − x/ψ) = 1/(1−φx) and 1/(1 + x/φ) = 1/(1+ψx), since 1/ψ = φ and 1/φ = ψ. In fact 1 − x − x² = (1−φx)(1+ψx), since the two sides are polynoimals with the same roots and the same constant term.
Multiplying out x / (1−x−x²) = A/(1−φx) + B/(1+ψx), we get x = A(1+ψx) + B(1−φx) for all x.
Substituting x = ψ gives ψ = A(1+ψ²) + B(1−φψ) = A(1+ψ²) so A = ψ/(1+ψ²) = ··· = 1/√5. Similarly B = −1/√5.
It is much easier to rewrite the original equation as: x = (A+B) + (Aψ−Bφ)x, and equate the constant terms and the coefficients of x on the two sides: 0 = A+B, so that B = −A; and 1 = Aψ−Bφ = Aψ+Aφ, so that A = 1/(ψ+φ) = 1/√5 and B = −1/√5.

5a. For example:

F3	=	[(1+√5)3 − (1−√5)3] / 23√5
	=	[ (1 + 3√5 + 3√25 + √125) − (1 − 3√5 + 3√25 − √125)] / 8√5
	=	(6√5 + 2(5)√5) / 8√5   =   16 / 8   =   2 (!?)

5b. You round down when k is even and the correction term −(−ψ)^k is negative, and round up when k is odd and −(−ψ)^k is positive.

5c. F₄₀ = round( (1.618033988749895)⁴⁰ / 2.2360679774997896 )
      = round( 1.023341550000000019 × 10⁸ ) = 102334155 .
The run of 0's in the decimal expansion is because the correction term −(−ψ)^k / √5 is exponentially small.
The number of digits is the rounding-down of:

log₁₀(F_k) = log₁₀(φ^k / √5) = k log₁₀(φ) − ½ log₁₀(5) ≅ (0.2089)k − 0.3494 .

• Knowing the generating function f(x) = ∑_k≥0 a_kx^k is the most essential information about a sequence {a_k}, and all other forms of information can be deduced from it. These diagrams illustrate this in the case of Fibonacci numbers. (See my graduate combinatorics course.)
• From the Fibonacci recurrence F_k = F_k−1 + F_k−2, we can derive the generating function:
  f(x)  =  ∑_k≥0 F_kx^k  =  ^x⁄_{(1−x−x²)} .
  The partial fraction decomposition of the generating function then gives Binet's explicit formula F_k  =  ¹⁄_√5 φ^k − ¹⁄_√5 (−ψ)^k.
• Also, the vertical asymptote x = ψ closest to x = 0 leads to a good approximation F_k  ≈  ¹⁄_√5 φ^k, where φ = ¹⁄_ψ = ^(1+√5)⁄₂ is the golden ratio. (In fact, F_k is given by rounding the approximation to the nearest integer.)
• Conversely, we could start from the generating function and recover the original recurrence. Clearing denominators gives:
  x  =  (1−x−x²) (∑_k≥0 F_kx^k)   =   ∑_k≥0 F_kx^k − ∑_k≥0 F_kx^k+1 − ∑_k≥0 F_kx^k+2
    =   F₁x + ∑_k≥2 (F_k − F_k−1 − F_k−2) x^k.
  Equating the coefficients x + 0x² + 0x³ + ···   on the left with the corresponding coefficients on the right, we find:
  0  =  F_k − F_k−1 − F_k−2   for k ≥ 2.

• Finally, we can reverse our generating function dictionary to translate algebra to logic, constructing a counting problem to which the answer is F_k. Expanding ^f(x)⁄_x using a geometric series ¹⁄_(1−z) with z = x+x², we get:
  ^f(x)⁄_x   =   ∑_k≥0 F_k+1x^k   =   ¹⁄_1−(x+x²)   =   ∑_ℓ≥0 (x+x²)^ℓ.
  Now, what counting algorithm would produce the generating function (x+x²)^ℓ ?
  Answer: A sequence of ℓ basic choices, each adding 1 or 2 to the size of the object; that is, choosing a list of ℓ numbers, each (1 or 2), whose sum is the total size k. Letting ℓ = 0 or 1 or 2 or . . . , we find:
  F_k+1  =  #{ (c₁, . . . , c_ℓ)  with  ℓ ≥ 0, and c_i = 1 or 2, and c₁ + ··· + c_ℓ = k }.
  For example, F₆ = 8 counts all sequences of 1's and 2's adding up to 6−1 = 5:
  (1,1,1,1,1)     (1,1,1,2)     (1,1,2,1)     (1,2,1,1)     (2,1,1,1)     (2,2,1)     (2,1,2)     (1,2,2).
  We could think of this as rows of 1 and 2 gram weights which balance on a scale against k−1 grams.

Consider the following generating function, whose coefficients a_k are known as tribonacci numbers:

f(x)   =   ∑_k≥0 a_k x^k   =   ¹⁄_{(1 − x − x² − x³)} .

This is the most essential way to encode these numbers: as Taylor coefficients of this rational function. Deduce other information from it.

1. Use Wolfram Alpha to find the first few Taylor coefficients a₀, . . . , a₂₀.
2. In the equation (1−x−x²−x³) ∑_k≥0 a_k x^k = 1, expand the left side and equate the x^k coefficients on the two sides. (The right side is 1 + 0x + 0x² + 0x³ + ···). Use this to find a recurrence equation for a_k with k ≥ 3, and verify that it works for the values from Prob 1.
3. Here is the graph of the generating function:
   
   Working numerically with Wolfram Alpha or a similar system, find the approximate roots of the denominator, solving 1−x−x²−x³ = 0. Switching to Approximate Form, you can see there is one real root x = α closest to the origin x = 0, with two other complex roots x = β, γ farther away. Use this to factor:
   1 − x − x² − x³   ≈   (1 − ^x⁄_α)(1 + ax + bx²).
   Extra Credit: Use Newton's Method to approximate the unique real root x = α of 1 − x − x² − x³ = 0. Get at least 10 decimal places.
   Ans: α ≈ 0.5436890127,  ¹⁄_α ≈ 1.8392867552 .
4. Find the (approximate) partial fraction expansion of the form:
   f(x)   ≈   ¹⁄_{(1 − x/α)(1 + ax + bx²)}   ≈   ^A⁄_{(1 − x/α)} + ^{(Bx + C)}⁄_{(1 + bx + cx²)} .
   In fact, you can find the coefficient of the dominant term ^A⁄_{(1 − x/α)} as the residue:
   A  =  lim_x→α (1 − ^x⁄_α) f(x).
   Ans: A ≈ 0.8012234553 .
5. The first term in the expansion must be dominant in the Taylor series of f(x) since x = α is the vertical asymptote closest to x = 0. Expand this geometric series to deduce an approximate formula for a_k . Check the accuracy of this approximation by comparing it to the exact values of a₀, . . . , a₂₀.
   Ans: a₂₀ = 121415,  A/α²⁰ = 121415.0008 .
6. Expand f(x) as:
   f(x)   =   ¹⁄_{(1 − (x+x²+x³))}   =   ∑_ℓ≥0 (x + x² + x³)^ℓ,
   and translate this algebraic expression into a logical choice algorithm. That is, find a family of combinatorial objects A = A₀ ∪ A₁ ∪ A₂ ∪ ··· such that a_k = |A_k|, counting the objects of size k. Hint: x + x² + x³ can be interpreted as choosing weights of 1,2, or 3 grams.

1. The sequence up to a₂₀ is: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415. See the Encyclopedia of Integer Sequences

2. Equating coefficients for k ≥ 3 gives  a_k − a_k−1 − a_k−2 − a_k−3  =  0,   so   a_k  =  a_k−1 + a_k−2 + a_k−3   for k ≥ 3. The similarity to the Fibonacci recurrence is why they are called "tribonacci".

3. The roots are α ≈ 0.54369 (known as the tribonacci constant) and β,γ ≈ −0.77184 ± 1.11514 i . The distance of a complex number a+bi from the origin is |a+bi| = √(a²+b²), so |β| = |γ| ≈ 1.3 > |α|: that is, β and γ are farther away than α.
To get arbitrary accuracy for α, use Newton's Method.

4 & 5. One form of the approximate partial fraction expansion is:

f(x)   ≈   ^{(1 − 2x2)}⁄_{(1 − 1.83928x)(1 + 0.83928x + 0.54369x²)}

  ≈   ^0.61842⁄_{(1 − 1.83929x)}   +   ^{(0.336228 x + 0.701836)}⁄_{(x² + 1.54369 x + 1.83928)} .

Expanding the first term as a geometric series gives:

a_k   ≈   0.61842 (1.839287)^k .

This approximation is exact to the nearest integer, provided we use enough decimal places for α and A:

a_k  =  round[A(¹⁄_α)^k]  for all  k ≥ 1.

For example, a₁₀ = 274 ≈ 274.007, but a₁₇ = 19513 ≈ 19513.6 does not round correctly and would need more decimal places.

6. Suppose we have a balance scale with an unlimited supply of 1 gram, 2 gram, and 3 gram weights. Then a_k is the number of ways to balance k grams with an ordered row of weights. For example a₄ = 7 counts the arrangements (3,1), (1,3), (2,2), (2,1,1), (1,2,1), (1,1,2), (1,1,1,1).

Consider the generating function

f(x)   =   ∑_k≥0 a_k x^k   =   ¹⁄_{(1−2x−x²)} .

This is the most essential way to encode the numbers a_k. Deduce the other forms from it.

1. Use Wolfram Alpha to find the first few Taylor coefficients a_k.
2. Expand the left side of the equation (1−2x−x²) ∑_k≥0 a_k x^k = 1, and equate the x^k coefficients on the two sides. (The right side is 1 = 1 + 0x + 0x² + ···.). Use this to find a recurrence equation for a_k, and verify that it works for the values from Prob 1.
3. Find the roots x = α, β of the denominator, solving 1−2x−x² = 0. Use this to factor:
   1 − 2x − x²   =   −(x−α)(x−β)   =   −αβ(1 − ^x⁄_α)(1 − ^x⁄_β).   =   (1−ax)(1−bx).
   (Remember to rationalize the denominator.) Find the partial fraction decomposition of f(x), and expand the corresponding geometric series to find an explicit formula a_k = A a^k + B b^k.
4. Find an approximate formula: a_k ≈ A a^k coming from the larger term in the explicit formula from Prob 3. How accurate is this approximation?
5. Expand f(x) as:
   f(x)   =   ¹⁄_{(1 − (2x+x²))}   =   ∑_ℓ≥0 (2x + x²)^ℓ,
   and translate this algebraic expression into a logical choice algorithm. That is, find a class of combinatorial objects such that a_k couunts the objects of size k.
   Hint: 2x + x² = x + x + x² can be interpreted as two basic options of size 1 (a red one and black one), and one basic option of size 2.

2.   a_k − 2a_k−1 − a_k−2   =   0,   so   a_k   =   2a_k−1 + a_k−2   for k ≥ 2.

3,4.   a_k  =  ^{(ak+1 − bk+1)}⁄_2√2  ≈  ^ak+1⁄_2√2, where a = 1+√2 ≈ 2.41,   b = 1−√2 ≈ −0.41 .

5. Suppose we have a balance scale with an unlimited supply of three kinds of weights: 1oz red ▪, 1oz black ▪, and 2oz □. Then a_k is the number of ways to balance k oz with an ordered row of weights.

Consider a sequence (a_k)_k≥0 defined recursively by:

a_k = a_k−1 − a_k−2   for k ≥ 2.

1. Show that for any choice of initial values a₀, a₁, this sequence repeats itself with period 6; that is, a_k = a_k−6 for k ≥ 6. Take a₀ and a₁ as unspecified constants, and compute a₂ = a₁ − a₀, then a₃ in terms of a₀ and a₁, etc.
2. Compute the generating function f(x) = ∑_k≥0 a_kx^k in the same way as for Fibonacci numbers.
3. Determine the roots x = α, β of the denominator, x² − x + 1 = 0. Write these as complex numbers a + bi for a,b real and i = √(−1), and draw them as vectors in the complex plane.
4. Compute α², α³, . . . using complex multiplication, based on ordinary distributivity combined with i² = −1. Show that α, β are complex 6^th roots of 1, i.e. α⁶ = β⁶ = 1, while α², α⁴ are cube roots of 1, and α³ is a square root of 1.
5. Use this to give another proof that a_k has period 6. That is, it is possible to expand the generating function in partial fractions:
   f(x)  =  ^A⁄_(1−x/α) + ^B⁄_(1−x/β) .
   (This follows from general algebra, without needing to compute the complex numbers A and B.) Now expand the right side to get a formula for a_k. Why must it have period 6?
6. Since α, β are roots of the minimal polynomial x² − x + 1 and of x⁶ − 1, we must be able to factor
   x⁶ − 1  =  p(x) (x²−x+1)
   for some polynomial p(x) with integer coefficients. Find this p(x) by long division or another factoring method. In fact, x² − x + 1 is a cyclotomic polynomial.
7. Clear the denominator of f(x) to get:
   f(x)(x⁶ − 1)  =  ∑_k≥0 a_kx^k (x⁶ − 1)  =  q(x)
   for some polynomial q(x). Multiply out and equate coefficients of x^k on each side, and give yet another proof that a_k has period 6.
8. Extra Credit: Explain how to classify all periodic linear recurrences with a given period n.

1. Eventually get a₆ = a₀ and a₇ = a₁, which shows that a₀, a₁, a₂, . . . is the same recursive sequence as a₆, a₇, a₈, . . .

2. As usual, the recurrence of a_k in terms of smaller a's implies an expression for f(x) in terms of itself:

f(x)  =  a₀ + a₁x + ∑_k≥2 (a_k−1 − a_k−2)x^k
 =  a₀ + a₁x + x ∑_k≥2 a_k−1x^k−1 − x² ∑_k≥2 a_k−2x^k−2
 =  a₀ + a₁x + x(f(x) − a₀) − x²f(x).

Solving this equation gives f(x)  =  ^{(a₀+(a₁−a₀)x)}⁄_(1−x+x²).

3. By the quadratic formula, the roots of the denominator x² − x + 1 = 0 are x = α, β = ¹⁄₂ ± ^√3⁄₂i . In the complex plane, these are unit-length vectors at angle ±π/3 from the positive real axis: α, β = cos(π/3) ± i sin(π/3).

4. An alternative to direct multiplication (a+bi)(c+di) = (ac−bd) + (ad+bc)i is the polar-coordinate picture: to multiply two complex numbers, multiply their radii and add their angles. Equivalently, Euler's formula gives:

α  =  e^πi/3  =  cos(π/3) + i sin(π/3),

α^k  =  e^kπi/3  =  cos(kπ/3) + i sin(kπ/3),

with α⁶ = e^2πi = 1. The powers of α are the 6 unit vectors whose angles from the positive real axis are multiples of π/3, namely the complex 6^th roots of 1.

5. Assuming the existence of the partial fraction decomposition, expanding geometric series as usual gives: a_k = ^A⁄_α^k − ^B⁄_β^k for some complex numbers A,B. This must be periodic because α^k+6 = α^k, and similarly for β.

6. Factoring:

x⁶ −1  =  (x³+1)(x³−1)  =  (x²−x+1)(x+1)(x²+x+1)(x−1)  =  (x²−x+1)(x⁴+x³−x−1).

7. Clearning denominators gives:

f(x) (x⁶ − 1)  =  f(x) (x²−x+1)(x⁴+x³−x−1)  =  (a₀ + (a₁−a₀)x) (x⁴+x³−x−1).

On the other hand,

f(x) (x⁶ − 1)  =  ∑_k≥0 a_kx^k (x⁶ − 1)  =  a₀ + ··· + a₅x⁵ + ∑_k≥6 (a_k − a_k−6)x^k

In the first expression, the x^k-coefficient is zero for k ≥ 6, so in the second expression we also have a_k − a_k−6 = 0 for k ≥ 6.

• Reading: Ch 2.6.6 pp. 185-189.
• One common definition of the Catalan numbers is in terms of a game in which you start with $1, and win or lose $1 in each round. Assume the game lasts 2k rounds (an even number), and we impose the restricitons:
  1. You break even, having $1 at the end of the 2k rounds (k wins, k losses).
  2. You never go bankrupt (get to $0).
  Then C_k is the number of possible games with 2k rounds. For example, C₂ = 2, since there are 2 possible games with 4 = 2(2) rounds, namely (+ − + −) and (+ + − −), where + = win $1, and − = lose $1. On the other hand (+ − − +) is not allowed, since you are bankrupt after the third round (start with $1, win $1, then lose $1 twice).
• We can picture such games by Catalan paths (also called Dyck paths), which depict the graph of total winnings after each round. These look like zigzag paths in the plane starting at (0,1), meaning $1 at round 0, ending at (2k, 1), meaning back to $1 after 2k rounds, and going up or down by 1 with each step to the right. Never going bankrupt means the graph must stay on or above the baseline y = 1, and never touch the x-axis. The two paths of C₂ are:
• The C_k's can be computed recursively starting with C₀ = 1, using the formula:
  C_k  =  C₀C_k−1 + C₁C_k−2 + C₂C_k−3 + ··· + C_k−1C₀    for   k ≥ 1
  and C₀ = 1. For example:  C₃  =  C₀C₂ + C₁C₁ + C₂C₀  =  (1)(2) + (1)(1) + (2)(1) = 5.
  This formula can be proved by a transformation which divides any C_k path into a unique pair of a C_m−1 path and a C_k−m path, where 1 ≤ m ≤ k.
  • Divide the path at the first point where it returns to the baseline, so there are 2m steps left of the division point and 2k−2m steps to the right.
  • The left part starts with a + and ends with a −, and the part in between is a C_m−1 path never going below the line y = 2. (This the part of the path "on stilts".)
  • The right part is a C_k−m path.
  • This tranformation has an obvious inverse, taking a pair of paths in C_m−1 × C_m−k, for 1 ≤ m ≤ k, to a path in C_k. This it is one-to-one and onto, giving the recurrence equation.
• Example: The C₄ path (+ + − − + − + −) first returns to the baseline after 2m = 4 steps, so we can split it into left, stilt, and right parts as: (+ + − − + − + −). That is, the left part (without the stilts) is the C₁ path (+ −); and the right part is the C₂ path (+ − + −).
  Every C₄ path can be split into a pair of C₀×C₃ , C₁×C₂ , C₂×C₁ , or C₃×C₀ paths.
• Explicit formula:
  C_k  =  ¹⁄_k+1 (2k | k).
  This can be proved by generating functions.
  • Multiply out the product of the Taylor series f(x)   =   ∑_k≥0 a_kx^k and g(x)   =   ∑_k≥0 b_kx^k to get a new Taylor series:
    f(x) g(x)   =   ∑_k≥0 c_kx^k
    where c_k = a₀b_k + a₁b_k−1 + a₂b_k−2 + ··· + a_kb₀ . The sequence c_k is called the convolution of the sequences a_k and b_k. In particular:
    f(x)²   =   ∑_k≥0 (a₀a_k + a₁a_k−1 + a₂a_k−2 + ··· + a_ka₀) x^k.

  • Now the generating function of Catalan numbers is:
    f(x)   =   C₀  +  ∑_k≥1 C_kx^k   =   C₀  +  ∑_k≥1 (C₀C_k−1 + C₁C_k−2 + ··· + C_k−1C₀) x^k
    
      =   1  +  x ∑_k≥1 (C₀C_k−1 + C₁C_k−2 + ··· + C_k−1C₀) x^k−1
    
      =   1 + x f(x)².

  • This is a quadratic equation in the variable f(x). It can be solved with the Quadratic Formula to get
    f(x)  =  ¹⁄_2x (1−√(1−4x)),
    This completes Step 1 of the Method.
  • For Step 2, expand the numerator using Taylor's coefficient formula, and simplify to get the explicit formula for C_k. See Prob #4 below.
• The Reflection Principle is another way to obtain an explicit formula:
  C_k = (2k | k) − (2k | k−1),
  which can be reduced to the previous formula (see Prob #5 below). That is, we take the large set of all 2k-step up/down paths from (0,1) to (2k,1): choosing such a path is the same as choosing the positions of the k up-steps, so there are (2k | k) paths in total. Among these paths are the C_k Catalan paths which never dip below the baseline y = 1; and also the bad paths which touch or cross the x-axis. We transform these bad paths by vertically reflecting the part after they first touch the x-axis, obtaining a 2k-step path from (0,1) to (2k,−1). Here are two examples of the Reflection Transformation for k = 4:
  
  This transformation is reversible, so that any 2k-step path from (0,1) to (2k,−1) can be reflected back to a path from (0,1) to (2k,1). Choosing a path on the right corresponds to choosing the positions of the k−1 up-steps, so there are (2k | k−1) such paths, and the same number of bad paths on the left. That is, the number of good paths is C_k = (2k | k) − (2k | k−1).

1. Draw all the paths for C₃ = 5 and C₄ = 14. For each path, identify its left and right parts (of length 2m−2 and 2k−2m) according to the rule in the Notes above. Observe that all pairs of paths occur, illustrating the recurrence equation.
2. Use the recurrence equation to algebraically compute C₁, . . . , C₁₀. Can you find any patterns, or guess any formula? Which C_k's are odd versus even?
3. The explicit formula for Catalan numbers is: C_k   =   ¹⁄_(k+1) (2k | k)   =   ^(2k)!⁄_k!(k+1)!
   1. Compute C₀, . . . , C₈ using the formula. Does it agree with the values in the previous problem?
   2. The Catalan number C_k counts Catalan paths (also called Dyck paths): paths in the plane from (0,1) to (2k,1), never going below y = 1, and having 2k steps, each going right by +1, and up-or-down by ±1.
      Problem: Why would you think of (2k | k) in relation to counting paths? There is a fairly natural relation, though it does not explain the full formula for C_k .
   3. Extra Credit: The Formula looks like a fraction, not a whole number: it seems a "coincidence" that (2k | k) is always divisible by k+1. Can you give an algebraic or combinatorial reason for this?
4. Explict formula from generating function
   1. Compute the Taylor series of √(1−x) = (1−x)^1/2. Hint: Use Taylor's formula for the coefficients, just as for the Binomial Theorem with negative exponents.
   2. Recall that the Catalan generating function is f(x)   =   ∑_k≥0 C_kx^k   =   (1 − √(1−4x)) / 2x . Go through Step 2 of the Method for the modified function: h(x)   =   xf(x)   =   C₀x + C₁x² + C₂x³ + ···   =   ½ − ½√(1−4x). You can find the Taylor series h(x) = ∑_k≥0 a_kx^k using the previous problem. Conclude by computing C_k = a_k+1, and obtaining the explicit formula above.
5. The Reflection Principle in the Notes gave a combinatorial proof of:  C_k = (2k | k) − (2k | k−1).
   1. Show algebraically that (2k | k) − (2k | k−1)  =  ¹⁄_(k+1) (2k | k), which recovers our previous explicit formula for C_k .
   2. Illustrate the proof that C₃ = (6 | 3) − (6 | 2) = 20 − 15, by drawing a diagram of the Reflection Transformation. Make a list of the (6 | 3) up/down paths from (0,1) to (6,1), including the Catalan paths (also called Dyck paths) which do not dip below the baseline y = 1, and the bad paths which touch or cross the x-axis. For each bad path, draw its reflected path in a new column: that is, vertically reflect the portion after the first touch of the x-axis, obtaining a new up/down path from (0,1) to (6,−1). Check that the reflected paths include all (6 | 2) up/down paths from (0,1) to (6,−1): this shows the nuumber of bad paths in the first column is also (6 | 2).
6. Grouping products: one of the many, many problems that give rise to Catalan numbers.
   The associative law says that a product does not depend on the grouping of factors: for example 2×3×4 can be multiplied as (2×3)×4 = 6×4 = 24 and 2×(3×4) = 2×12 = 24. Abstractly: (x₀x₁)x₂  =  x₀(x₁x₂). Of course it works with more factors, and there are more ways to multiply: ((x₀x₁)x₂)x₃  =  (x₀(x₁x₂))x₃  =  (x₀x₁)(x₂x₃)  =  x₀((x₁x₂)x₃)  =  x₀(x₁(x₂x₃)) Let M_k be the number of ways to group k+1 factors x₀x₁···x_k , so that M₀ = M₁ = 1, M₂ = 2, M₃ = 5.
   1. Find a recurrence for M_k as follows. Sort the M_k groupings into cases, depending on where the outermost (last) multiplication occurs.
      For example, in (x₀x₁)(x₂x₃), the last-multiplication division point is after x₁, and the number of groupings with this division point is M₁M₁ = 1.
      In ((x₀x₁)x₂)x₃ and (x₀(x₁x₂))x₃, the division point is between x₂ and x₃, and the number of groupings with this division point is M₂M₀ = 2.
      To illustrate, make a two-column table of the transformation between M₄ and M₀C₃ + M₁M₂ + M₂M₁ + M₃M₀ . Be clear on how to split each expression into left and right parts.
   2. Prove by induction that M_k = C_k . This is obvious since . . . .
7. A family tree (ordered tree) is a structure of unlabeled vertices or nodes connected by edges as follows. At the top is one node (the ancestor), with some number of nodes coming down from it (indicating children), listed in age order left-to-right. Then each of these has some nodes coming down from it, etc., eventually ending in nodes without children. The family trees (ordered trees) with 4 nodes are: Note that the difference between the 3rd and 4th trees is whether the ancestor's older or younger child has his own child.
   Let O_k be the number of ordered trees with k nodes, so that O₁ = O₂ = 1, O₃ = 2, O₄ = 5.
   Problem: Find a recurrence for O_k by splitting a tree into the subtree coming from the ancestor's oldest child, and the other subtree with everyone else. Compute some values of O_k and compare to C_k. Prove your comparison.
8. Extra Credit: HHM Ch 2.6.6, p.190 #6. Suppose 2k people are seated around a table. How many ways are there for k pairs to shake hands simultaneously across the table in such a way that no arms cross? Geometrically: mark 2k nodes on a circle, and pair the nodes up by drawing curves between them, so that no two curves cross. Let H_k be the number of handshake-patterns for 2k people.
   For example, H₃ = 5 counts the following patterns:

   

   Find H₄ by drawing out all possible patterns for 8 nodes. Guess a relation of H_k to C_k. Prove a Catalan-like recurrence for H_k, which gives a recursive algorithm for drawing patterns, and also proves the relation between H_k and C_k. Finally, find a simple, explicit transformation between handshake patterns for 2k people and parentheses for grouping the product x₀···x_k, as in #6 above: this directly proves that H_k = M_k, which we know is C_k.
   Hint: Given a handshake pattern, saw the table in half along the curve starting at the top node, getting left and right pieces of the table, which can be considered as smaller tables with nodes (guests) around them. Fixing the number of nodes in each piece, how many smaller handshake patterns can be inserted? Sum these to get the recurrence.

1. See Wolfram Mathworld, which has a picture of the Dyck paths for k = 1,2,3,4, but in a different orientation: instead of up/down paths staying on or above y = 1, those paths go right or up, and stay below the line y = x. Turn your head sideways to recover our orientation.
For C₃, we show the left part (on stilts) and right part of each path:

(+ • − + + − −)       (+ • − + − + −)       (+ + − − + −)       (+ + + − − − •)       (+ + − + − − •) Here   •   indicates the one-point C₀ path.

2.

k	0	1	2	3	4	5	6	7	8	9	10
Ck	1	1	2	5	14	42	132	429	1430	4862	16796

3b. Since the path ends at the same height as it began, half the steps must be down, and half up. Thus every path corresponds to a choice of k positions out of 2k for the up steps; and there are (2k | k) possibilities for such a choice. (See HW 1/9 #4, the city grid problem, where we also had two choices for each step, with fixed start and end points.) However, Catalan paths also require staying above y = 1, and the Formula says that a 1/(k+1) fraction of all the paths satisfy this. Where this fraction comes from is unclear: it is explained in the Wikipedia article.

4a. The k^th derivative of (1−x)^1/2 is (−1)^k(½)(½−1)(½−2)···(½−k+1)(1−x)^{1/2 − k}, so the k^th coefficient of the Taylor series is a_k = (−1)^k(½)^k / k!. This can be rewritten as:

a_k   =   (−1)^k(½)^k / k!   =   (−1)^k(1/2)(−1/2)(−3/2)···(−(2k−3)/2) / k!   =   −1(3)(5)···(2k−3) / 2^kk!
  =   −( 1(3)(5)···(2k−3) / 2^kk! ) ( 2(4)(6)···(2k−2) / 2^k−1(k−1)! )
  =   ^−(2k−2)!⁄_{(k−1)!(k−1)! 2^2k−1k}   =   ^{−(2k−2 | k−1)}⁄ _2^2k−1k .

4b. Modifying the above Taylor series

(1−4x)^1/2   =   −∑_k≥0 ^{(2k−2 | k−1)}⁄_2^2k−1k  x^k,

we find:

h(x)   =   ½ − ½(1−4x)^1/2   =   ∑_k≥1 ^{(2k−2 | k−1)}⁄_2^2kk (4x)^k   =   ∑_k≥1 ¹⁄_k (2k−2 | k−1) x^k.

This immediately gives the explicit formula   C_k  =  a_k+1  =  ¹⁄_k+1 (2k | k).
⊞ Direct derivation  

5a. By the Reflection Principle, we have C_k  =  (2k | k) − (2k | k−1), which simplifies algebraically as:

(2k | k) − (2k | k−1)  =  ^(2k)!⁄_k!k! − ^(2k)!⁄_{(k+1)!(k−1)!}  =  ^(2k)!⁄_k!(k−1)! (¹⁄_k − ¹⁄_k+1)

 =  ^(2k)!⁄_k!(k−1)! (¹⁄_k(k+1))  =  ¹⁄_(k+1) ^(2k)!⁄_k!k!  =  ¹⁄_(k+1) (2k | k).

6a. The groupings with division point after x_m split into a factor with m+1 variables and one with k−m variables, with 0 ≤ m ≤ k−1; considering recursively, there are M_mM_k−m−1 such groupings. Thus M_k = M₀M_k−1 + M₁M_k−2 + ··· + M_k−1M₀.

As an example, we make a two-row table of the transformation between the 14 factorizations counted by M₄, and the splitting of these at the outermost multiplication into pairs of factorizations counted by ∑³_i=0 M_iM_3−i. In fact, the most practical way to list all the Catalan number C_n expressions in any model is to write the (C_i | C_3−i) expressions first, then combine them.

C4	x0(x1(x2(x3x4)))	x0(x1((x2x3)x4))	x0((x1x2)(x3x4))	x0((x1(x2x3))x4)	x0(((x1x2)x3)x4)
C0 | C3	x0 | x1(x2(x3x4))	x0 | x1((x2x3)x4)	x0 | (x1x2)(x3x4)	x0 | (x1(x2x3))x4	x0 | ((x1x2)x3)x4

C4	(x0x1)(x2(x3x4))	(x0x1)((x2x3)x4)	C4	(x0(x1x2))(x3x4)	((x0x1)x2))(x3x4)
C1 | C2	x0x1 | x2(x3x4)	x0x1 | (x2x3)x4	C2 | C1	x0(x1x2) | x3x4	(x0x1)x2) | x3x4

C4	(x0(x1(x2x3)))x4	(x0((x1x2)x3))x4	((x0x1)(x2x3))x4	(((x0(x1x2))x3)x4	(((x0x1)x2)x3)x4
C3 | C0	x0(x1(x2x3)) | x4	x0((x1x2)x3) | x4	(x0x1)(x2x3) | x4	((x0(x1x2))x3 | x4	((x0x1)x2)x3 | x4

6b. M_k and C_k are computed using exactly the same recursion, starting from the same initial value M₀ = C₀ = 1, so they must be equal.
Formally, we can prove it by induction. M_k = C_k is definitely true for k = 0. Now assume it is proved up to a given k. Then M_k+1 = M_kM₀ + M_k−1M₁ + ··· + M₀M_k. By assumption M₀ = C₀, M₁ = C₁, . . . , M_k = C_k, so the right hand side equals C_kC₀ + C_k−1C₁ + ··· + C₀C_k, which equals C_k+1 by the known recurrence. Thus the equality M_k+1 = C_k+1 also holds, and the induction proceeds. Conclusion: M_k = C_k holds for all k ≥ 0.

7. Any tree T with k ≥ 2 splits into two subtrees: T' coming from the ancestor's oldest child (having m ≥ 1 vertices), and T'' with everyone else, including the ancestor (having k − m vertices). Conversely, any T' and T'' can be put together in a unique way to get a T (i.e. make the ancestor of T' into the oldest child of the ancestor of T''). Considering recursively, the number of pairs (T' , T'') is O_mO_k−m. Thus, O_k = O_k−1O₁ + O_k−2O₂ + ··· + O₁O_k−1. This is the same recurrence as for the sequence C'_k = C_k+1 , so O_k = C'_k = C_k+1.
In the picture above, the first two trees are of type O₃O₁, since the subtree T' coming from the oldest (only) child has 3 vertices, and the rest make a tree T'' with 1 vertex (the ancestor alone). The third tree is of type O₂O₂, since the subtree T' from the oldest child has 2 vertices, and the rest make T'' with 2 vertices. The last two trees are of type O₁O₃, since the oldest child has no children, and there are 3 vertices besides.

1. Let f(x)   =   ∑_k≥0 a_kx^k and g(x)   =   ∑_k≥0 b_kx^k. Show that  f(x) g(x)   =   ∑_k≥0 c_kx^k   where
   c_k = a₀b_k + a₁b_k−1 + a₂b_k−2 + ··· + a_kb₀ .
   The sequence c_k is called the convolution of the sequences a_k and b_k.
2. Give a simple formula for the quantity: c_k   =   2^k + 2^k−1(3) + 2^k−23² + ··· + 2(3^k−1) + 3^k Hint: This c_k is a convolution of two well-known sequences, so its generating function h(x) = ∑_k≥0 c_kx^k is the product of two well-known generating functions. Use our usual techniques to evaluate the coefficients of h(x), once you have its formula.

Solutions
I. The terms in the product are a_ixⁱ b_jx^j = a_ib_j x^i+j with i, j ≥ 0. Grouping these by the power of x, the coefficient of x^k is the sum of all a_ib_j with i + j = k, namely c_k = a₀b_k + a₁b_k−1 + ··· + a_kb₀ .
II. The series c_k is the convolution of a_k = 2^k and b_k = 3^k, so by part (a), the generating function h(x) = ∑_k≥0 c_k x^k = f(x) g(x), where f(x)   =   ∑_k≥0 2^kx^k = 1/(1−2x)     and     g(x)   =   ∑_k≥0 3^kx^k = 1/(1−3x) . Taking the partial fraction expansion: h(x)   =   1 / (1−2x)(1−3x)   =   −2 / (1−2x) + 3 / (1−3x) , we expand to get c_k   =   −2(2^k) + 3(3^k)   =   3^k+1 − 2^k+1 .
Actually, we could do this without generating functions, using the difference-of-powers formula: (3−2)(3^k + 3^k−1(2) + ··· + 3(2^k−1) + 2^k)   =   3^k+1 − 2^k+1 .

• Exam Date: Wed Feb 21 during our usual lecture. Start 5 min early for extra time.
• Topics: All material so far, summarized in the two Toolkits on Counting Techniques and Generating Functions.
• Problems will be of difficulty and style similar to quizzes.
• Study strategy
  • For each old quiz, cover your answers and re-do it, then look at your previous answer and my answer from class notes and video, also Q12+13. Make sure you understand all mistakes. I can email missing quizzes on request.
  • Do Review HW posted below. (Don't just read the solutions!) We will also have a review quiz Mon.
  • Make flash cards to memorize:
    • Basic Principles: Sum, Product, Difference (PIE), Quotient, Transformation
    • 4 Basic Problems: n!, n^k, (n | k), ((n | k)).
    • Generating function dictionary from logic to algebra
    • Binomial Theorem, Geometric Series, Negative Binomial Series
  • Review the HW and finish problems you didn't do.

1. In the set [1000] = {1, 2, . . . , 1000}, count the numbers which have the following properties.
   1. How many with distinct digits?  Examples:   GOOD 3, 30, 301    BAD 33, 131, 300
   2. How many with strictly increasing digits?  Examples:   GOOD 3, 13, 137    BAD 30, 33, 355
   3. How many with digits adding to 9?  Examples:   GOOD 9, 63, 306    BAD 901
2. Bob goes to a shop selling 5 kinds of donuts: Plain, Glazed, Chocolate, Strawberry, Boston (P,G,C,S,B). Count how many ways to choose donuts, under the following conditions:
   1. A bag of 3 donuts, all different. Ex: Plain, Chocolate, Strawberry.
   2. A bag of 3, but they need not be different. Ex: 1 Plain, 2 Chocolates.
   3. A bag with any number of donuts (but at least 1), all different. Ex: The most he could get is 1 of every kind.
   4. Every lunchtime Mon-Fri, a bag of 3 donuts, all different in each bag.
      Ex: Mon P,G,S; Tue G,C,B; Wed G,C,B; Thu P,C,S; Fri C,S,B.
3. In the same store, the 5 kinds of donuts are displayed in bins next to each other. Count how many arrangements under the following conditions:
   1. 5 bins: 1 of each kind, no restrictions. Ex: from left-to-right, B,C,G,S,P.
   2. Same as (a), but the Chocolate cannot be next to the Boston. Ex: B,G,C,S,P
   3. Same as (a), but the Chocolate cannot be next to the Boston or the Strawberry. Ex: G,C,P,B,S or B,G,C,P,S.
   4. 6 bins: 2 identical bins of Chocolate, 1 each of the other 4 kinds. Ex: G,B,C,P,C,S.
4. You Can't Have Just One: Suppose you choose 20 jellybeans of 3 kinds (red, green, yellow), with the rule that you cannot choose just one of any kind. That is, if you choose any reds, you must take at least 2 of them, and the same way with greens and yellows. Let a be the number of ways to choose such a handful.
   1. Use positive counting (Sum and Product Principles) to find a.
   2. Use negative counting (PIE) to find a.
   3. Use the Method of Generating Functions to find a.
      • Step 0: Generalize a to a sequence a_k.
      • Step 1: Use the combinatorics of choosing to find a simple formula for the generating series f(x) = ∑_k≥0 a_kx^k.
      • Step 2: Use algebra and known series to expand f(x) as a Taylor series. Equating the coefficients of this final series with the original a_k solves our problem.
5. Consider the following recurrence: p_k = 3p_k−1 − 2p_k−2   for k ≥ 2, with p₀, p₁ being arbitrary given constants. Ex: In the special case p₀ = p₁ = 1, we get p₂ = 3(1)−2(1) = 1, p₃ = 3(1)−2(1) = 1, etc.
   Solve by the Method of Generating Functions, giving an explicit, non-recursive formula for p_k.
6. Board games.
   1. In the One-Step Game, for each turn you either stay in place, or advance one step. How many possible outcomes in 8 turns?
      Example: The 8 turns are: step, stay, stay, step, stay, step, step, stay.
   2. In the One-Step Game, how many ways can you advance 5 steps in 8 turns?
      Example: step, stay, stay, step, stay, step, step, step.
   3. In the Many-Step Game, for each turn you advance any number of steps: 0,1,2,3, . . . . How many ways can you advance 5 steps in 8 turns?
      Example: 1 step, 0 steps, 0 steps, 3 steps, 1 step, 0 steps, 0 steps, 0 steps.
7. For each game below, use Generating Functions to compute the sequence: a_k  =  number of ways to advance k steps in 8 turns. Hint: Consider possible outcomes in turn 1, . . . , turn 8, and translate this into algebra.
   1. Compute a_k for 8 turns of the One-Step Game from above.
   2. Compute a_k for 8 turns of the Many-Step Game from above.
   3. Compute a_k for 8 turns of the Odd-Step Game, where for each turn, you advance an odd number of steps: 1,3,5, . . . . Explain your algebraic formula for a_k by solving the problem with positive-counting methods. The formula itself and the computations of Step 2 hint at a useful transformation.
   4. Compute a_k for 8 turns of the Ten-Step Game where each turn can be any number of steps from 0 to 10. Hint: This is similar to the multiple-dice problem, but Step 2 is more complicated. You can also do Step 2 by brute force, with Wolfram Alpha.
8. Pascal's Triangle and Deletion Transform
   1. State the recurrence formula for choose-numbers (n | k) which we use to construct Pascal's Triangle. Recall the transformation proof of this recurrence: we transform the objects counted on the left side (sets S with k distinct elements from n) into objects counted by the right side (sets S' with k or k−1 elements from {1, . . . ,n}).
   2. The equivalent of Pascal's Triangle for multi-choose numbers is given by the recurrence: ((n | k))  =  ((n−1 | k)) + ((n | k−1)). We can prove this by transformation from the objects counted by the left side (multi-sets M with k objects of n kinds), into objects counted by the right side (multi-sets M' with k elements of n−1 kinds, or with k−1 elements of n kinds). The transformation is defined as follows on a multiset M.
      • If M does not contain n, let M' = M
      • If M has at least one copy of n, let M' = M − {n}, the same except with one fewer copy of n.
      Problem: Draw a table of this transformation M → M' in the case ((3 | 3)) = ((2 | 3)) + ((3 | 2)).
   3. Define the inverse of the transformation in (b). Given M', how to produce M?
9. Give a simple formula to evaluate each of the following numbers, for any n ≥ 1. Hint: Use the Binomial Theorem.
   1. (n | 1) + (n | 2) + ··· + (n | n)
   2. 1 + 2(n | 1) + 4(n | 2) + 8(n | 3) + ··· + 2ⁿ(n | n)
10. Multinomial coefficients
    1. How many ways to split up 15 people into 3 basketball teams of 5 each?
    2. You have 5 red marbles, 5 blue, 5 green. How many ways to line them up? Example: BBRGGGBGGRRRBBR. Hint: Think of lining up 15 distinct people, then giving each a red, blue, or green team jersey which makes members of each team indistinguishable (Quotient Principle). This is one of our standard Transforms.
11. Extra Credit: Count the possible ways to write 10 as a sum of whole numbers (order matters). Examples: 8 + 2 or 1 + 5 + 2 + 2.
    First solve by generating functions, then explain the very simple answer by a combinatorial transformation.

1a. Sum Principle. Split into cases: 1 digit or 2 digits or 3 digits or 4 digits.
For each case, use the Product Principle, multiplying the number of allowed choices for each digit. (The only possible 4-digit number is 1000, which is bad.)
Ans: 9 + 9(10−1) + 9(10−1)(10−2) + 0

1b. Transform each number into a set, e.g. 13 ↔ {1,3} ⊂ [9]. These are counted by Basic Problem 3.
Ans: (9 | 1) + (9 | 2) + (9 | 3)

1c. The reverse Multiplicity Transform considers the digits as multiplicities in a multiset with 9 objects of 3 kinds, e.g. 351 ↔ {A,A,A,B,B,B,B,B,C} or 90 = 090 ↔ {B,B,B,B,B,B,B,B,B}. (We consider 1, 2, and 3 digits at once by inserting leading zeroes.) These are counted by Basic Problem 4.
Ans: ((3 | 9))

2a. The items in a bag are most reasonably interpreted as unordered, thus modeled by a set or multi-set. They are 3 different items of 5 kinds, namely a set of 3 from 5 (Basic Problem 3). Ans: (5 | 3) = (5 | 2) = (5)(4) / 2 = 10.
Note: It is not completely unreasonable to consider items in a bag as ordered, which would lead to Basic Problem 2, ans: 5³. It is wise to state in your answer which interpretation you use.

2b. Here a bag is a multi-set with 3 items of 5 kinds (Basic Problem 4). Ans: ((5 | 3)) = (5+3−1 | 3) = (7 | 3) = 7³ / 3! = 35.

2c. A bag is any non-empty subset of {P,G,C,S,B}. An n-element set has 2ⁿ subsets (since each of the n elements could be in or out of the subset: Product Principle). Since the empty set is not allowed, we get 2⁵ − 1 = 31.

2d. A sequence of 5 independent choices, each with (5 | 3) possibilities (Product Principle). Ans: (5 | 3)⁵ = 100,000.

3a. Basic Problem 1: Ordering 5 distinct objects (Basic Problem 1). Ans: 5! = 120.

3b. PIE: A = {all arrangements from part (a)}, A₁ = {arrangements containing sequence C,B}, A₂ = {arrangements containing sequence B,C}. In A₁, we can consider the adjacent letters C,B as a single unit, next to the 3 other units P, G, S; and these 4 units can be arranged arbitrarily. Same for A₂, so |A₁| = |A₂| = 4!. Also |A₁∩A₂| = 0, and the number of good arrangements is:

|A - (A₁∪A₂)|   =   |A| − |A₁| − |A₂| + |A₁∩A₂| = 5! − 2(4!) + 0 = 72.

3c. PIE: A = {all arrangements}, with 4 kinds of forbidden arrangements: A₁ = {arrangements containing the sequence C,B}, A₂ = {arr with B,C}, A₃ = {arr with C,S}, A₄ = {arr with S,C}. Reasoning as before, |A| = 5! and |A_i| = 4!. The only non-empty intersections are: A₁∩A₄ = {arr with S,C,B} and A₂∩A₃ = {arr with B,C,S}. Again, consider arbitrary arrangements of a 3-letter unit with two 1-letter units, giving 3! arrangements for each intersection. Hence:

|A - (A₁∪ . . . ∪A₄)|   =   |A| − ∑_1≤i≤4 |A_i| + ∑_1≤i<j≤4 |A_i∩A_j|                    
                              − ∑_{1≤i<j<k≤4} |A_i∩A_j∩A_k| + |A₁∩A₂∩A₃∩A₄|

  =   5! − 4(4!) + 2(3!)   =   36.

Another way: positive counting using a transformation. We analyze the data into parts which can be easily counted.

• From a good arrangement like (C,G,S,B,P), we cross out the two letters S,B to extract (C,G,P); and we extract the other two letters (S,B). Now, in the original arrangement, replace C,G,P by bin dividers,and S,B by beans: ( | | O O | ), meaning the first two bins are empty, the third bin contains two beans, the fourth bin is empty. Now, S,B cannot be next to C, so we erase these two empty bins and their adjacent dividers to get: ( O O | ).
• No information has been lost, since these three pieces of data (C,G,P), (S,B), ( O O | ) are enough to reconstruct the original good arrangement. From seeing C at the beginning of (C,G,P), we know the two erased bins must be at the beginning, giving ( | | O O | ); and now we can replace the three dividers and two beans by the corresponding letters to recover (C,G,S,B,P).
• We can reverse-transform any data of the same type, such as: (P,C,G), (B,S), ( O | O ). From (P,C,G), we know that the two erased bins were in the center (next to C), so the bin arrangement was: ( O | | | O ) and we re-construct the original arrangment by replacing the dividers and beans with the corresponding letters: (B,P,C,G,S).
• Therefore the number of good arrangements is equal to the number of data triples above: ways to arrange {P,G,C}, which is 3!, times the ways to arrange {B,S}, which is 2!, times the ways to put O O into two bins ( | ), which is ((2 | 2)). Final answer: 3! 2! ((2 | 2)) = 6 (2) (3) = 36.

3d. Pick the positions of the two C's (Basic Problem 3), then arrange the other 4 around them (Basic Problem 1). Ans: (6 | 2) 4! = 360.
Alternatively: list the positions of B,G,S,P, making a list of 4 distinct positions out of 6 (Basic Problem 2). Ans: 6⁴ = 360.

4a. Positive counting. Split all outcomes into disjoint cases (Sum Principle): Case (i), just 1 flavor, all 20 beans the same: 3 handfuls. Case (ii), have 2 flavors: then 4 beans are fixed (2 of each flavor), with 16 left to choose among 2 flavors; (3 | 2)((2 | 16)) handfuls. Case (iii), have all 3 flavors: then 6 beans are fixed, 14 left to choose among 3 flavors; ((3 | 14)) handfuls.   Ans: 3 + 3((2 | 16)) + ((3 | 14)) = 3 + 3(17 | 1) + (16 | 2) = 174

3b. Negative counting (PIE). A = {all handfuls of 20 beans of 3 kinds}, A_i = {just 1 of flavor i, the other 19 of 2 flavors}, for i = 1,2,3.   Ans: ((3 | 20)) − (3 | 1)((2 | 19)) + (3 | 2)((1 | 18)) − (3 | 3)((0 | 17))  =  (22 | 2) − 3(20 | 1) + 3 = 174.

4c. Step 0: Generalize the problem to give a sequence. Let a_k be the number of ways to choose k jellybeans with the given restriction.
Step 1. Find a simple formula for the generating function f(x) = ∑_k≥0 a_k x^k . Consider that a handful of beans can be chosen by the logical expression:

(0R or 2R or 3R or ···) and (0G or 2G or 3G or ···) and (0Y or 2Y or 3Y or ···) which translates to the algebraic expression: f(x) = (1 + x² + x³ + ···)³ = ( 1/(1−x) − x )³ = ( 1 + x²/(1−x) )³. Step 2. To expand either of the above expressions for f(x), first apply the binomial theorem (a+b)³ = a³ + 3a²b + 3ab² + b³ , then expand each term using 1/(1−x)ⁿ = ∑_k≥0 ((n | k)) x^k . Here ((n | k)) are multichoose numbers, which can be written in terms of binomial coefficients as: ((n | k)) = (n+k−1 | k) = (n+k−1 | n−1).
Using the first expression: f(x)   =   1/(1−x)³ − 3x/(1−x)² + 3x²/(1−x) − x³            
  =   ∑_k≥0 ((3 | k))x^k  −  ∑_k≥0 3((2 | k))x^k+1  +  ∑_k≥0 3x^k+2  −  x³ The coefficient of x²⁰ is our answer:   ((3 | 20)) − 3((2 | 19)) + 3 = 174 . This recovers the answer from negative counting by PIE.
Alternatively, using the second expression: f(x) = 1 + 3x²/(1−x) + 3x⁴/(1−x)² + x⁶/(1−x)³            
  =   1  +  ∑_k≥0 3x^k+2  +  ∑_k≥0 3((2 | k))x^k+4  +  ∑_k≥0 ((3 | k))x^k+6 The coefficient of x²⁰ is:   3 + 3((2 | 16)) + ((3 | 14)) = 174 . This recovers the answer from positive counting by cases.

5. Turning the recurrence into an equation for f(x) = ∑_k≥0 p_kx^k, we get:

f(x)   =   p₀ + p₁x + ∑_k≥2 (3p_k−1−2p_k−2)x^k
  =   p₀ + p₁x + 3x∑_k≥2 p_k−1x ^k−1 − 2x²∑_k≥2 p_k−2x^k−2
  =   p₀ + p₁x + 3x (f(x) − p₀) − 2x²f(x) Solve for f(x):

f(x)

=

(p1−3p0)x + p0 1 − 3x + 2x2

.

Since the denominator has roots:   1 − 3x + 2x² = 0 when x = 1 and x = 1/2, we may write: 1 − 3x + 2x² = (1−x)(1−2x) and: f(x)  =  A/(1−x) + B/(1−2x)  =  ∑_k≥0 A x^k + ∑_k≥0 B 2^k x^k . We may compute A, B by: (p₁−3p₀)x + p₀ = A(1−2x) + B(1−x). Substituting x = 1 and x = 1/2 gives: A = 2p₀ − p₁  , B = p₁ − p₀ . Collecting x^k terms, we find: p_k  =  2p₀ − p₁  +  (p₁ − p₀) 2^k. Check: For the special case p₀ = p₁ = 1, the formula gives p_k = 1, which is correct.

6a. A sequence of 8 independent choices, with 2 outcomes for each. Product Principle:  2⁸ = 256.

6b. A sequence of 8 binary choices, with 5 steps and 3 stays. Position Transformation into Basic Problem 3:  (8 | 5) = (8 | 3) = 56.

6c. A sequence of 8 whole numbers adding up to 5, (n₁, . . . , n₈) with n_i ≥ 0 and n₁ + ··· + n₈ = 5. The Multiplicity Transformation turns this into arrangements of 5 beans in 8 bins, Basic Problem 4:  ((8 | 5)) = (5+8−1 | 5) = (12 | 5) = 792.

7a. Step 1: (Take 8 turns stay/step)   ⇔   (turn 1: stay or step) and ··· and (turn 8: stay or step).
Since "stay" advances 0 steps, it is replaced by x⁰, and similarly "step" becomes x¹:

f(x) = (x⁰ + x¹) ··· (x⁰ + x¹) = (1 + x)⁸
Step 2: Binomial Series:  f(x) = Σ_k=0⁸ (8 | k)x^k,  so a_k = (8 | k), as in 6(b).

7b. Step 1: (Take 8 turns of any length)   ⇔  
          (turn 1: 0 steps or 1 step or 2 steps or···) and ··· and (turn 8: 0 steps or 1 step or ···).
Each choice to advance i steps gets replaced by xⁱ:

f(x)  =  (x⁰ + x¹ + x² + ···)⁸  =  (¹⁄_(1−x))⁸  =  ¹⁄_(1−x)⁸
Step 2: Negative Binomial Series: f(x)  =  Σ_k≥0 ((8 | k))x^k, so a_k = ((8 | k)), as in 6(c).

7c. Step1: Similarly to the above:

f(x)  =  (x + x³ + x⁵ + ···)⁸  =  (x (1 + x² + x⁴ + ···))⁸  =  (x (¹⁄_(1−x²))⁸  =  (x⁸) ¹⁄_(1−x²)⁸ Step 2: f(x)  =  x⁸ Σ_k≥0 ((8 | k))x^2k  =  ((8 | 0))x⁸ + ((8 | 1))x¹⁰ + ((8 | 2))x¹² + ···
We can see that the coefficient of of an even power x^k is: a_k = ((8 | ½(k−8) )). Also, the coefficient of an odd power x^k vanishes: a_k = 0.
Retrospective: To solve this problem by elementary methods, consider any way to advance k steps in 8 odd-step turns.

• There is at least one step per turn, so fix that one step and forget about it (8 times).
• The remaining part of each turn advances an even number of steps, for a total of k−8 steps in 8 turns.
• This is the same as advancing any number of double-steps per turn, for a total of k' = ½(k−8) double-steps in 8 turns.
• This reduces the problem to the previous case 7(b), so the answer is ((8 | k')) = ((8 | ½(k−8) )).

7d. f(x)  =  (1+x+x²+···+x¹⁰)⁸  =  ^(1−x11)8⁄_(1−x)⁸
 =  (∑⁸_i=0 (−1)ⁱ (8 | i) x¹¹ⁱ) (∑_j≥0 ((8 | j)) x^j),
so a_k  =  ∑_11i+j=k (−1)ⁱ (8 | i) ((8 | j))

8a. The recurrence is: (n | k) = (n−1 | k) + (n−1 | k−1). The Deletion Transformation is S → S' where: S' = S if n ∉ S; and S' = S \ {n} if n ∈ S. Its inverse is the Insertion Transformation S' → S, where S = S' if |S'| = k, and S = S' ∪ {n} if |S'| = k−1.

8b. Each input M is on top, with its transformation output M' below it.

M =	{1,1,1}	{1,1,2}	{1,1,3}	{1,2,2}	{1,2,3}	{1,3,3}	{2,2,2}	{2,2,3}	{2,3,3}	{3,3,3}
M' =	{1,1,1}	{1,1,2}		{1,2,2}			{2,2,2}
			{1,1}		{1,2}	{1,3}		{2,2}	{2,3}	{3,3}

The inputs cover all ((3 | 3)) multisets M; the outputs cover all ((2 | 3)) + ((3 | 2)) multisets M'.

8c. The inverse is the Insertion Transformation M' → M, where:  M = M', if |M'| = k; and

M  =  M' ∪ {n}  =  M' with one extra copy of n,   if |M'| = k−1.

9a. 2ⁿ  =  (1 + 1)ⁿ  =  (n | 0)1ⁿ + (n | 1)1ⁿ⁻¹1 + ··· + (n | n)1ⁿ , so:

(n | 1) + (n | 2) + ··· + (n | n)  =  2ⁿ − 1.

9b. 3ⁿ  =  (1 + 2)ⁿ  =  (n | 0) + (n | 1)2 + (n | 2)2² + ··· + (n | n)2ⁿ.

10a. There is no order among team members, so choose a set of 5 from 15 for the first team, then choose another 5 from the remaining 10 for the second team, with the third team of 5 left over. This gives the multinomial coeffcient:

(15 | 5) (10 | 5) (5 |5)  =   (15 | 5,5,5)  =   ^15!⁄_5!5!5! .

(Note that multinomial coefficients are very different from multi-choose numbers.) If we do not count which team is first, second, or third, we divide this by 3!.

10b. A line of marbles corresponds to a team-assignment for each of the 15 people, by using the Position Transform to record which positions have R's, which have B's, which have G's. For example:

(

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
B	B	R	G	G	G	B	G	G	R	R	R	B	B	R

)   ↔   {3,10,11,12,15} ∪ {1,2,7,13,14} ∪ {4,5,6,8,9}.

Thus, the number of marble lineups is equal to the number of team assignments from part (a), not divided by 3!.

• Reading: Ch 2.7.1 p. 190-194.
• Let X be a rectangle (not a square) with vertices (corners) labeled for reference:

  1	−−−−−−	2
  |		|
  4	−−−−−−	3

• A symmetry of X is a mapping (or function) σ : X → X taking each point of X to another point of X, in a way that preserves the structure (in this case the geometric structure of distances and angles). For example, the side-to-side reflection τ₁ mirrors each point across a vertical line bisecting X, mapping the corners as: τ₁(1) = 2,   τ₁(2) = 1,   τ₁(3) = 4,   τ₁(4) = 3.
  This preserves the structure, because it takes the short side between 1 & 4 to another short side between τ₁(1) & τ₁(4), i.e. between 2 & 3; and similarly for every side of X (short to short, long to long).
• We call the set of all symmetries of X the symmetry group G = Sym(X).
• Each symmetry is a bijective (one-to-one and onto) function σ : X → X, and each vertex i is taken to some vertex σ(i) = j, making a permutation of the vertices.
  We represent σ by a two-line permutation table: on the top line with the input vertices 1,2,3,4, and on the bottom line their symmetric images, the output vertices σ(1), σ(2), σ(3), σ(4) .
  The most useful notation for a permutation σ : {1, 2, . . . , n} → {1, 2, . . . , n} is the cycle notation, in which we write the effect of iterating the mapping: (1, σ(1), σ(σ(1)), . . . ), ending as the iterations come back to the first element 1; then if 2 is not in the first cycle, we write (2, σ(2), σ(σ(2)), . . . ), etc. Each number appears in exactly one cycle.
  Examples: One permutation for n = 6 is:   σ = (

  1	2	3	4	5	6
  5	2	6	1	4	3

  ) = (1,5,4) (2) (3,6).  
  The side-to-side reflection of the rectangle is:   τ₁ = (

  1	2	3	4
  2	1	4	3

  ) = (1,2) (3,4).
• Every symmetry group contains the trivial symmetry or identity mapping ε : X → X, which takes each point to itself: ε(1) = 1, ε(2) = 2, etc. For our rectangle:  ε = (

  1	2	3	4
  1	2	3	4

  ) = (1)(2)(3)(4).
• The symmetric group S_n is the set of all possible permutations π : [n] → [n] taking the set [n] = {1, 2, . . . , n} one-to-one onto itself. This is the symmetry group of the set [n] thought of as a handful of identical marbles, which can be switched around arbitrarily. Since the two-line notation for π is just an ordering of [n], there are |S_n| = n! such mappings.
• By representing each symmetry of the rectangle X in terms of how it permutes the corners, we find G = Sym(X) ⊂ S₄; that is, G is a subgroup of S₄ .
• Greek letter names:   α alpha,   β beta,   γ gamma,   ε epsilon,   ρ rho,   σ sigma,   τ tau.

1. Consider the geometric symmetries of the rectangle X.
   1. Draw all the symmetries, including the identity ε, rotations ρ₁, ρ₂, . . . and reflections τ₁, τ₂ . . . . For each symmetry σ, draw the rectangle and an arrow from each vertex i to the destination or image vertex σ(i).
      Hints:
      • The ¹⁄₄ turn is not a symmetry, since it does not take the rectangle onto itself; rather, it would stand the rectangle on end.
      • To make sure you have found all the symmetries, consider a general symmetry σ, and count the possibilities for σ(1), then the remaining possibilities for σ(2), etc. This will give an upper bound for the number of symmetries.
   2. Write the two-line and cycle notation for each symmetry of the rectangle.
2. Cycle notation. Consider the permutation σ ∈ S₈ given in 2-line notation by:
   σ  =  (

   1	2	3	4	5	6	7	8
   6	8	7	4	1	5	2	3

   ).
   1. Draw σ as an arrow-diagram, with vertices 1,2, . . . , 8 in a circle, and an arrow from each i to its image σ(i). For example, an arrow from 1 to 6, from 2 to 8, etc.
   2. Tracing the arrow-cycles in part (a), write σ in cycle notation. Hint: Since σ(1) = 6, σ(6) = 5, σ(5) = 1, one of the cycles is (1,6,5).
   3. Now draw an arrow diagram for the inverse permutation σ⁻¹, which undoes σ. (That is, if σ(i) = j, then σ⁻¹(j) = i.) Write its cycle notation. In general, what is the rule for the inverse of a cycle?
3. For each pair of rectangle symmetries α, β, consider the composition α ∘ β, meaning do α after β, giving another symmetry γ. Picture this γ and identify it as one of the known symmetries. Also try computing α ∘ β symbolically, by seeing where it takes each vertex i: first β takes i to some j = β(i), then α takes this image point to α(j), so γ(i) = α(β(i)). The permutation γ can then be identified as one of the symmetries described previously.
   Record the results in a multiplication table, with rows and columns labeled by ε, ρ, τ₁, τ₂; and in row α and column β, write the letter of the symmetry γ = α ∘ β .
   Example: To compute τ₁ ∘ τ₁, we can picture that two reflections bring every point back to itself, so τ₁ ∘ τ₁ = ε. Or we can compute that τ₁(τ₁(1)) = τ₁(2) = 1 and similarly τ₁(τ₁(i)) = i. But this is the same function as the identity ε(i) = i, so τ₁ ∘ τ₁ = ε. Thus in the multiplication table, in the diagonal position with row τ₁ and column τ₁, we write ε.

   °	ε	ρ	τ1	τ2
   ε
   ρ
   τ1			ε
   τ2

4. We say a group G is commutative if σ ∘ τ = τ ∘ σ for all σ, τ ∈ G.
   1. Is our G = Sym(X) commutative? How can you check from the multiplication table?
   2. Find σ, τ ∈ S₃ which do not commute. Use this to show that S_n is never commutative for n ≥ 3.
5. Counting with symmetry. How many ways are there to arrange all four numbered beads 1,2,3,4 on the corners of the rectangle, counting symmetric arrangements as the same. (No repeated beads!) Give one representative arrangement from each distinct symmetry class.

1a. The symmetries of the rectangle are the identity ε, the ¹⁄₂ rotation ρ, the side-to-side reflection τ₁, and the up-and-down reflection τ₂.
For an arbitrary symmetry σ, vertex 1 must go to one of the vertices σ(1) = 1,2,3, or 4; and this forces σ(2) to be the long-edge neighbor of σ(1); and there is also only one choice for σ(3), σ(4). Thus there are at most 4 symmetries, and we have found them all.

1b. The permutations of vertices corresponding to the geometric symmetries are:

ε = (

1	2	3	4
1	2	3	4

) = (1)(2)(3)(4),   ρ = (

1	2	3	4
3	4	1	2

) = (13)(24),   τ₁ = (

1	2	3	4
2	1	4	3

) = (1,2)(3,4),   τ₂ = (

1	2	3	4
4	3	2	1

) = (1,4)(2,3).

It is easier to write only the bottom row, the one-line notation.

2a,b. The arrow cycles are: 1 → 6 → 5 → 1, and 2 → 8 → 3 → 7 → 2; and 4 → 4. Thus, the cycle notation is: σ = (1,6,5)(2,8,3,7)(4). This can be rewritten many ways with the same meaning, such as σ = (4)(6,5,1)(8,3,7,2).

2c. The inverse permutation reverses each cycle, so that σ⁻¹ = (5,6,1)(7,3,8,2)(4) = (1,5,6)(2,7,3,8)(4).

3. With a little practice, you can easily multiply using two-line or cycle notation. For example:

ρ ∘ τ₁ = (

1	2	3	4
3	4	1	2

) ∘ (

1	2	3	4
2	1	4	3

) = (

1	2	3	4
4	3	2	1

) = τ₂,
since: ρ(τ₁(1)) = ρ(2) = 4; ρ(τ₁(2)) = ρ(1) = 3; ρ(τ₁(3)) = ρ(4) = 2; ρ(τ₁(4)) = ρ(3) = 1. Picture each number going into τ₁ from the right, and its output gets passed left to ρ, with the final output coming out on the far left.

The multiplication table is:

°	ε	ρ	τ1	τ2
ε	ε	ρ	τ1	τ2
ρ	ρ	ε	τ2	τ1
τ1	τ1	τ2	ε	ρ
τ2	τ2	τ1	ρ	ε

4a. Our group G, the symmetries of the rectangle, is a commutative group: we see that the table is symmetric across the upper-left to lower-right diagonal, so that an upper-right entry σ ∘ τ is the same as the corresponding lower-left entry τ ∘ σ.

4b. Writing in cycle notation, we have (1,2)(3) ∘ (1)(2,3) = (1,2,3), whereas (1)(2,3) ∘ (1,2)(3) = (1,3,2), so (1,2)(3) and (1)(2,3) do not commute. We can duplicate this in every larger S_n by just defining σ(i) = i for i ≥ 4. For example: (1,2)(3)(4)(5) ∘ (1)(2,3)(4)(5) = (1,2,3)(4)(5), etc.

5. We use the Quotient Principle, as we once did for computing (n | k) = ^nk⁄_k!. There are 4! arrangements without considering symmetry (Basic Problem 1). Collect all these into columns of arrangements which are symmetric to each other. Since there are |G| = 4 symmetries, each column has 4 arrangements. Each column is a symmetry class, and the number of columns is ^|S₄|⁄_|G|  =  ^4!⁄₄  =  6. One way to choose representatives is:

1 −−−−−− 2 | | 4 −−−−−− 3

1 −−−−−− 2 | | 3 −−−−−− 4

1 −−−−−− 3 | | 4 −−−−−− 2

1 −−−−−− 3 | | 2 −−−−−− 4

1 −−−−−− 4 | | 3 −−−−−− 2

1 −−−−−− 4 | | 2 −−−−−− 3

Each of these arrangements can be moved within a class of 4 equivalent arrangements by the rectangle symmetries ε, ρ, τ₁, τ₂. This problem is easy because each equivalence class has the same number of elements; this would no longer be true if repeated beads were allowed.

• Reading: Ch 2.7.2, pp. 196−200.
• Consider an object X with symmetry group G = Sym(X), and vertices or special points {1, . . . , n} which give an embedding G ⊂ S_n.
• A coloring is a function that assigns a color (by convention a number 1, . . . , k) to each vertex, that is c : {1, . . . , n} → {1, . . . , k}.
• Let C be the set of all colorings without considering symmetry: |C| = kⁿ since each of n vertices can have k possible colors.
• Since a symmetry σ moves X onto itself, it also moves each coloring c to another coloring σ(c). The symmetry class or orbit of c is the set of all colorings symmetric to c:
  c = { σ(c) for all σ ∈ G },
  and we let C = {c₁, c₂, . . .} be the set of all distinct symmetry classes.
• Counting with Symmetry: Find the number of distinct symmetry classes |C|; that is, the number of different colorings ''up to symmetry'', counting symmetric colorings as the same. Burnside's theorem will answer this question.
• Burnside's theorem: The number of colorings with k allowed colors, up to symmetry, is equal to the number of colorings fixed by a given symmetry, averaged over all the symmetries of X:
  |C|   =   ¹⁄_|G| ∑_σ∈G |C_σ|   =   ¹⁄_|G| ∑_σ∈G k^cyc(σ),
  where:
  C_σ  =  Fix(σ)  =  {c ∈ C with σ(c) = c}
  is called the fixed set of σ ∈ G, and cyc(σ) is the number of cycles of σ permuting the n vertices.
• We will prove Burnside's theorem next time. For now, we prove the second equality in the theorem: the fixed set of σ has size:
  |C_σ|  =  k^cyc(σ),
  where cyc(σ) is the number of cycles of the permutation σ ∈ G ⊂ S_n. This is because a coloring c is fixed by a symmetry σ whenever c gives the same color to all the vertices within each cycle of σ. Thus, to choose a coloring c ∈ C_σ, we independently choose a common color (from k possible) for the vertices in each cycle of σ. There are cyc(σ) such choices, so the total number of c is k^cyc(σ).
  Example: If σ = ε the trivial symmetry ε = (1)(2) ··· (n) has cyc(ε) = n cycles. Since all colorings are preserved by not moving, we have |C_ε| = |C| = kⁿ = k^cyc(ε).
• Let D be the set of colorings where each vertex has a different color: c(i) ≠ c(j) for i ≠ j. Clearly the number of such colorings is: |D| = kⁿ. Since the colors are all different, we never have σ(c) = c for σ ≠ ε. Thus if G = {σ₁, . . . , σ_N}, every coloring class has N = |G| different colorings: c = {σ₁(c), . . . , σ_N(c)}. Therefore the number of distinct symmetry classes of colorings of n vertices by all different colors chosen from k colors, is:
  |D|   =   ^|D|⁄_|G|   =   ^kn⁄_N .
  This is an example of the Quotient Principle from the Counting Toolkit. It agrees with Burnside, because the fixed set of a non-trivial symmetry is empty: D_σ = {}, except for D_ε = D:
  |D|   =   ¹⁄_|G| ∑_σ∈G |D_σ|   =   ¹⁄_|G| (|D| + 0 + ··· + 0).

1. We illustrate colorings of X in the example where X is the rectangle from the previous HW, having vertices (corners) labeled clockwise by {1,2,3,4}:

   1	−−−−−−	2
   |		|
   4	−−−−−−	3

   The symmetry group G = Sym(X) contains the identity ε, the ¹⁄₂ rotation ρ, and horizontal and vertical reflections τ₁, τ₂. (The ¹⁄₄ rotation is not a symmetry of X because it does not move the rectangle onto itself.)
   Consider ways to color the vertices with k = 2 colors (Red and Blue), that is, functions c : {1,2,3,4} → {R,B} which we can write by listing the color of each vertex: for example, BBRB means c(1) = B, c(2) = B, c(3) = R, c(4) = B. The set of all colorings (without considering symmetry) is C, with |C| = 2⁴ = 16.
   1. Draw all 16 colorings as rectangles with each vertex labeled with its color.
   2. Two colorings c and c' are equivalent up to symmetry if one can be moved to the other by some σ ∈ G = Sym(X), written c' = σ(c). (For example, we can flip the colors horizontally or vertically.) The symmetry class of a coloring c is the set of all colorings symmetric to it: c = {c' = σ(c) for all σ ∈ G}.
      Problem: Draw the 16 colorings grouped into symmetry classes, and determine |C|, the number of distinct symmetry classes, i.e. the number of colorings "up to symmetry", counting symmetric colorings as the same.
   3. For each distinct coloring class c, containing all colorings symmetric to a given c ∈ C, find the stabilizer subgroup G_c ⊂ G, namely the σ with σ(c) = c. Verify that the number of colorings in the class is c = ^|G|⁄_|Gc|.
   4. For each group element σ ∈ G, determine C_σ, the set of colorings with σ(c) = c. For example, the side-to-side reflection symmetry τ₁ has C_τ1 including  

      R   R

      R   R

        ,  

      R   R

      B   B

       ,  and two others. Verify that in each case, the number of fixed colorings is |C_σ| = k^cyc(σ), where cyc(σ) is the number of cycles of σ as a permutation of {1,2,3,4}, as appearing in Burnside's theorem.
   5. Verify Burnside's theorem for the above colorings: the number of symmetry classes is equal to the average of |C_σ| over all symmetries σ ∈ G.
   6. Now let D be the colorings of the rectangle with k = 4 colors (which we can think of as stickers with the numbers 1,2,3,4) such that each vertex has a different color. (These are equivalent to one-to-one mappings c : [4] → [4].)
      Write all of the colorings in D, grouped into symmetry classes, and determine |D|, the number of colorings in D up to symmetry.
2. The rigid symmetries (turning and flipping) of a regular n-gon form the dihedral group G = D_n. (In class, we looked at D₃, the 6 symmetries of an equilateral triangle, and D₄, the 8 symmetries of a square.) We label the vertices clockwise 1,2, . . , n, and consider each symmetry as a permutation of the vertices, meaning D_n ⊂ S_n. For example, the ¹⁄_n clockwise turn ρ₁ is the permutation ρ₁(1) = 2, ρ₁(2) = 3, . . . , ρ₁(n) = 1, which in cycle notation is (1,2,3, . . . , n). In general, let ρ_i denote the ⁱ⁄_n clockwise rotation, and denote the reflections by τ_i for i = 1, . . . , n, starting with τ₁ having a line of reflection through vertex 1, then turning the line of reflection by ¹⁄_n for each successive i (if n is odd) and by ¹⁄_2n (if n is even).
   1. For D₄, write each of the 8 symmetries in two-line and cycle notation.
   2. For D₄, show that ρ_k = ρ₁ ∘ ··· ∘ ρ₁ = ρ₁^k, the result of ρ₁ repeated k times. (This is true for all D_n.)
   3. For D₄, show that the reflections τ_i are all given by τ₁ ∘ ρ₁ⁱ. Thus, all the elements of D₄ can be obtained by composing τ₁ and ρ₁: we say these two elements generate the group. (True for all D_n.)
3. Use Burnside's theorem for the square with symmetry group G = D₄ to compute |C|, the number of necklaces with n = 4 beads with k available colors: that is, k^cyc(σ) averaged over all σ ∈ G. Check your general formula by hand for the cases k = 1, 2.
4. Classify necklaces with n = 6 beads of k = 2 colors, up to symmetry. Draw an example of each symmetry type, such as:
   

   R

   B       R

   R       B

   B

   which we write compactly by listing the beads in clockwise order from the top: RRBBRB. This is the same as its rotations BRRBBR, RBRRBB, etc., and its flip RBRRBB by the symmetry τ = (1)(25)(34)(6), etc.
   Hints: First determine the natural symmetry group involved. Imagine the beads at the corners of a regular hexagon, with the corners numbered as:

   1

   6        2

   5        3

   4

   Write each symmetry in cycle notation, and apply Burnside's theorem. Once you have determined the number of symmetry classes of colorings, use trial-and-error to give that many different colorings: all R's; or 5 R's and 1 B; or 4 R's and 2 B's next to each other, etc.

1a & b. The colorings, grouped into symmetry classes of the rectangle group (not the symmetries of the square). Each row lists the elements of c = {c, ρ(c), τ₁(c), τ₂(c)}, though some of these might be identical, so we only list them once. (Remember, the quarter-turn is not a rectangle symmetry.)

R	R
R	R
B	R		R	R		R	B		R	R
R	R		R	B		R	R		B	R
B	B		R	R
R	R		B	B
R	B		B	R
R	B		B	R
B	R		R	B
R	B		B	R
R	B		B	B		B	R		B	B
B	B		B	R		B	B		R	B
B	B
B	B

We have |C| = 7 symmetry classes (rows) altogether. Thus, we say there are 7 colorings of the rectangle vertices with colors R,B, distinct up to symmetry.

1c. Writing a coloring c as the list c(1)c(2)c(3)c(4), the stabilizer subgroups of the 7 distinct symmetry classes are:

G_RRRR = G_BBBB = G,   G_BRRR = G_RBBB = {ε},     G_BRRB = {ε, τ₁},     G_BBRR = {ε, τ₂},     G_BRBR = {ε, ρ}.

This determines the number of colorings symmetric to the given one, for example the class of RRRR contains ^|G|⁄_|GRRRR| = ⁴⁄₄ = 1 coloring, i.e. only RRRR.

1d. A symmetry fixes a coloring, σ(c) = c, whenever all vertices within each cycle of σ are given the same color. For example, ρ = (13)(24), so C_ρ contains colorings with c(1) = c(3) and c(2) = c(4), with k choices for each cycle, so |C_ρ| = k². The fixed colorings are:

• C_ε = {all 16 colorings} which has k^cyc(ε) = 2⁴ = 16 fixed colorings.
• C_τ1 = {

  RR

  RR

   , 

  RR

  BB

   , 

  BB

  RR

   , 

  BB

  BB

  }, which has k^cyc(τ₁) = 2² = 4 fixed colorings.
• C_τ2 = {

  RR

  RR

   , 

  RB

  RB

   , 

  BR

  BR

   , 

  BB

  BB

  } which has k^cyc(τ₂) = 2² = 4 fixed colorings.
• C_ρ = {

  RR

  RR

   , 

  RB

  BR

   , 

  BR

  RB

   , 

  BB

  BB

  } which has k^cyc(ρ) = 2² = 4 fixed colorings.

1e. Since the identity ε has 4 cycles, the rotation ρ has 2 cycles, and the two reflections have 2 cycles each, Burnside gives the formula:  |C|  =  ¹⁄₄(k⁴ + 3k²).
The case k = 1 clearly has only one coloring, and indeed the formula becomes |C| = ¹⁄_|G| ∑_σ∈G 1^cyc(σ) = 4/4 = 1. In the case k = 2, we recover |C| = ¹⁄₄(2⁴ + 3(2²)) = 7 from part (b).

1f. There are |D| = 4! = 24 colorings of 4 vertices with 4 distinct colors, corresponding to lists of 1,2,3,4 in some order. Every symmetry class has |G| = 4 colorings, so the number of symmetry classes is: |D|  =  ^|D|⁄_|G|  =  ²⁴⁄₄  =  6.

2a. We write each element of the dihedral group in cycle notation. Note that an element like σ = (1432) means σ(1) = 4, σ(4) = 3, σ(3)=2, σ(2) = 1, and we could equivalently write σ = (2143) = (3214) = (4321).

ε = (1)(2)(3)(4)     ρ₁ = (1234)     ρ₂ = (13)(24)     ρ₃ = (1432) = (4321)    
τ₁ = (1)(3)(24)     τ₂ = (14)(23)     τ₃ = (2)(4)(13)     τ₄ = (12)(34).

3b. We have ρ₁(i) = i+1 mod n. This means we wrap around an n-hour clock, with n = 0 and n+1 = 1, etc. Performing this k times, we get ρ₁^k(i) = i + k mod n, and this is clearly ρ_k(i). Note also that ρ₁ⁿ = ε and by definition ρ₁⁰ = ε. (These last facts are analogous to (−1)² = 1 and x⁰ = 1.)

2c. We have τ_k = τ₁ ρ₁^k for k = 0,1,2,3, as we can check by computing the cycle notation for the left and right sides. For example:

τ₁ρ₁ = (1)(3)(24) ∘ (1234) = (14)(23) = τ₂

3. The identity ε has 4 cycles, the two ¹⁄₄ rotations have 1 cycle each, the ¹⁄₂ rotation has 2 cycles, two of the reflections have 2 cycles, and the other two reflections have 3 cycles. Burnside gives the general formula: |C| = ¹⁄₈(k⁴ + 2k³ + 3k² + 2k).

The case k = 1 color gives |C| = ¹⁄₈ ∑_σ∈G 1^cyc(σ) = 8/8 = 1, which is correct.

In the case k = 2 colors (R & B), we get |C| = ¹⁄₈(2⁴ + 2(2³) + 3(2²) + 2(2)) = 6: there is one symmetry class having 0R's, 1R, 3R's, 4R's; and two symmetry classes having 2R's & 2B's, namely when the R's are next to each other and when they are diagonal. Note that there is one fewer class of colorings than for the rectangle, because there is more symmetry equivalence.

4. We can consider the 6 beads at the corners of a regular hexagon (with vertices labeled 1, . . . , 6 clockwise), so that the symmetry group is D₆: the identity; 5 rotations ρ_i = (ρ₁)ⁱ; three reflections τ₁, τ₂, τ₃ across the lines through opposite pairs of edges; and three reflections τ₄, τ₅, τ₆ across the lines through opposite pairs of vertices:

σ	cycles	kcyc(σ)
ε	(1)(2)(3)(4)(5)(6)	k6
ρ1	(123456)	k1
ρ2	(135)(246)	k2
ρ3	(13)(24)(36)	k3
ρ4	(531)(642)	k2
ρ5	(654321)	k1
τ1	(1)(26)(35)(4)	k4
τ2	(12)(36)(45)	k3
τ3	(2)(13)(46)(5)	k4
τ4	(23)(14)(56)	k3
τ5	(3)(24)(15)(6)	k4
τ6	(34)(25)(16)	k3

Burnside says that the number of distinct symmetry classes of colorings with k possible colors is the average of the numbers in the right-hand column:

¹⁄₁₂(k⁶ + k¹ + ··· + k³)   =   ¹⁄₁₂(k⁶ + 3k⁴ + 4k³ + 2k² + 2k).

Thus for k = 2 colors, we compute the number of classes:

|C|   =   ¹⁄₁₂ (2⁶ + 3(2⁴) + 4(2³) + 2(2²) + 2(2))   =   13.

Representatives of the 13 classes:

RRRRRR,   BRRRRR,   BBRRRR,   BRBRRR,   BRRBRR,
BBBRRR,   BBRRBR,   BRBRBR,  
BBBBBB,   RBBBBB,   RRBBBB,   RBRBBB,   RBBRBB.

The classes on the bottom line are the ones on the top with R & B switched; and the colorings in the middle line are the same (up to symmetry) if R & B are switched. For example, the colorings:

B		R
R       B		B       R
B       R		R       B
R		B

are related by a vertical flip, and so count as the same necklace.

• Reading: Ch 2.7.2 pp. 198-199
• Burnside Theorem: Let X be an object marked with n special points, having symmetry group G = Sym(X) ⊂ S_n. Let C = {c : [n] → [k]} be the set of colorings of the n points with k available colors, and let C be the set of symmetry classes of colorings c = {σ(c) for σ ∈ G}. Then the number of distinct symmetry classes is:
  |C|   =   ¹⁄_|G| ∑_σ∈G |C_σ|   =   ¹⁄_|G| ∑_σ∈G k^cyc(σ),
  the average number of fixed colorings of symmetries σ ∈ G, where
  C_σ = Fix(σ) = {c ∈ C s.t. σ(c) = c}
  and cyc(σ) is the number of cycles of σ on the n vertices. We showed last time that |C_σ| = k^cyc(σ).
• It is hard to count symmetry classes when they do not all have the same size, which happens whenever some symmetry σ takes a coloring c to itself: σ(c) = c. We can measure this by two kinds of sets. One is C_σ in the Theorem, the set of colorings fixed by a given symmetry σ; the other is the stabilizer of a given coloring c, the set of symmetries which fix c:
  G_c  =  Stab(c)  =  {σ ∈ G with σ(c) = c}.
  Lemma: The size of the symmetry class c, i.e. the number of colorings symmetric to c, is equal to the total number of symmetries in G, divided by the number of symmetries which take c to itself:
  |c|  =  |G| / |G_c|

• Proof of Burnside
  • We define the set S of pairs consisting of a symmetry σ and a coloring c unchanged by that symmetry:
    S = { (σ, c)   s.t.   σ(c) = c }.
    Since the elements are pairs, they are naturally drawn in a table with rows corresponing to symmetries, and columns corresponding to colorings.
  • Computing ^|S|⁄_|G| by rows (one for each σ ∈ G) leads to the average of |C_σ|, the right side of Burnside.
  • Computing ^|S|⁄_|G| by columns (one for each c ∈ C) leads to a contribution of
    ^|G_c|⁄_|G|  =  ¹ / |c|
    for each coloring: this is the correct weight for c, considering that its entire symmetry class c should have total weight 1. Thus ^|S|⁄_|G| is equal to the total weight of all colorings, which is |C|, the left side of Burnside.
• Example: X is a triangle with rotation and reflection symmetries:

  X   =

  1 3   2

  G = {ε, ρ1, ρ2, τ1, τ2, τ3},

  where ρ₁ is 1/3 clockwise rotation, ρ₂ is 2/3 clockwise rotation, and τ_i is the reflection which fixes vertex i. Also we take k = 2 possible colors, White and Black.
  In the table below, each  ×  marks a pair (σ, c), a symmetry and a coloring fixed by that symmetry, an element of S = { (σ, c)  s.t.  σ(c) = c }. The dark/light shading of the column headings groups the colorings into symmetry classes.

  σ   \   c

  W W W

  B W W

  W W B

  W B W

  W B  B

  B B W

  B W B

  B B  B

  Row Counts

  ε = (1)(2)(3)

  ×

  ×

  ×

  ×

  ×

  ×

  ×

  ×

  8 = 23

  ρ1 = (123)

  ×

  ×

  2 = 21

  ρ2 = (321)

  ×

  ×

  2 = 21

  τ1 = (1)(23)

  ×

  ×

  ×

  ×

  4 = 22

  τ2 = (2)(13)

  ×

  ×

  ×

  ×

  4 = 22

  τ3 = (3)(12)

  ×

  ×

  ×

  ×

  4 = 22

  |C|  =  ∑ |Gc| ⁄|G|  =

  6⁄6

  +

  2⁄6

  +

  2⁄6

  +

  2⁄6

  +

  2⁄6

  +

  2⁄6

  +

  2⁄6

  +

  6⁄6

  =

  |S| / |G|

  =

  1⁄6(23+21+21+22+22+22)

  • In each row σ, we count the colorings which are unchanged (fixed) by the symmetry σ, which I denoted C_σ. These are precisely the colorings with the same color within each cycle of σ, so there are k^cyc(σ) of these. For example, the symmetry τ₂ = (2)(13) fixes a coloring like BWB having c(1) = c(3); that is, we have k choices for c(1) = c(3) and independently k choices for c(2), giving k² colorings in C_τ2.
    Adding all the row-sums gives |S|, and dividing by |G| = 6, we find that |S| / |G| gives the right-hand side of Burnside's theorem.
    Specifically: τ₂ = (2)(13) fixes the following colorings:

    W W W

    W W B

    B B  W

    B B  B

    These are all the colorings with c(2) free and c(1) = c(3). This means cyc(τ₂) = 2 choices with k = 2 possibilities each, so we have k^cyc(τ₁) = 2² colorings in this row.
  • In each column c, we count the symmetries G_c which leave the coloring c unchanged. Dividing by |G|, we get |G_c| / |G|, which is 1 / |c| by the Lemma: |c| = |G| / |G_c|.
    The dark/light shading separates these fractions into symmetry classes, with each group totaling to 1. Adding all the column fractions gives 1 for each class, and we find that |S| / |G| gives the total number of classes |C|, which is the left-hand side of Burnside's theorem.
  • For example, the coloring:

    c =

    B W W

    is fixed by ε and τ₁ = (1)(23), so it has two ×'s under it, and |G_c| = 2. Thus its symmetry class c has ^|G|⁄_|Gc| = ⁶⁄₂ = 3 colorings, and c should count as ¹⁄₃ of  c:

    c   =

    B W W

    W W B

    W B W

    Adding the fractions for each column in c gives 2/6 + 2/6 + 2/6 = 1/3 + 1/3 + 1/3 = 1, meaning this one symmetry class counts as 1 in the sum, as it should.