Generating Functions: Concepts & Practice

🧠 What is a Generating Function?

Think of a generating function as a "calculator" or a "storage box" for an infinite sequence of numbers. We use a polynomial where the coefficients store the answers to a counting problem.

The "state" (like a sum, cost, or weight) is stored in the exponent \(x^n\). The "answer" (like the number of ways) is stored in the coefficient \(a_n\).

For example, if we have a function \(f(x) = 1 + 2x + 5x^3\):

• \(1x^0\): There is 1 way to get a state of 0.
• \(2x^1\): There are 2 ways to get a state of 1.
• \(0x^2\): There are 0 ways to get a state of 2 (since the term is missing).
• \(5x^3\): There are 5 ways to get a state of 3.

---

1. The Two Core Rules: OR and AND

Almost all problems are built from these two simple ideas:

➕ The "OR" Rule (Addition)

• Principle: If you can choose either option A OR option B, you add their polynomials.
• Example: You are buying one item. You can either buy an apple (cost 2) or a banana (cost 3).
  • Apple's polynomial: \(x^2\) (1 way to get a cost of 2)
  • Banana's polynomial: \(x^3\) (1 way to get a cost of 3)
  • Your total choice polynomial is: \(f(x) = x^2 + x^3\)
  • This polynomial \(f(x)\) perfectly describes your choices: you can get a cost of 2 in 1 way, or a cost of 3 in 1 way.

✖️ The "AND" Rule (Multiplication)

• Principle: If you must choose option A AND option B, you multiply their polynomials.

• Example: You are buying two items. You must buy one fruit AND one drink.

  • Fruit Choice (F): Apple (cost 2) OR Banana (cost 3)
    • \(F(x) = x^2 + x^3\)
  • Drink Choice (D): Juice (cost 1) OR Water (cost 2)
    • \(D(x) = x^1 + x^2\)
  • Total Polynomial: \(Total(x) = F(x) \times D(x)\)
    • \(Total(x) = (x^2 + x^3)(x^1 + x^2)\)
    • \(Total(x) = x^2(x^1 + x^2) + x^3(x^1 + x^2)\)
    • \(Total(x) = (x^3 + x^4) + (x^4 + x^5)\)
    • \(Total(x) = \mathbf{1}x^3 + \mathbf{2}x^4 + \mathbf{1}x^5\)

• Interpreting the Result:

  • The \(1x^3\) term: 1 way to get a total cost of 3 (Apple + Juice).
  • The \(2x^4\) term: 2 ways to get a total cost of 4 (Apple + Water, or Banana + Juice).
  • The \(1x^5\) term: 1 way to get a total cost of 5 (Banana + Water).

---

2. Ordinary Generating Functions (OGF)

These are the "standard" type of generating functions.

• Best for: Counting problems where order does not matter (combinations).
• Keywords: "Choosing items," "bags of fruit," "making change," "partitions." The order you pick them in is irrelevant.
• Form: \(f(x) = a_0 + a_1 x + a_2 x^2 + \dots = \sum_{n=0}^{\infty} a_n x^n\)
• Meaning: \(a_n\) is the number of ways to build a collection with a "total value" of \(n\).

---

3. Exponential Generating Functions (EGF)

These are a special type used for a different class of problems.

• Best for: Counting problems where order matters (permutations).
• Keywords: "Arrangements," "sequences," "permutations," "words," "labeled objects."
• Form: \(f(x) = a_0 \frac{x^0}{0!} + a_1 \frac{x^1}{1!} + a_2 \frac{x^2}{2!} + \dots = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}\)
  • Notice the \(n!\) in the denominator. This is the key difference!
• Meaning: \(a_n\) is the number of ways to build an ordered arrangement with \(n\) distinguishable items.

---

4. Common Building Blocks (Toolkit)

Here are the most common series you will use to build your functions.

OGF Building Blocks

• Choice: 0 or 1 (e.g., "use item A once or not at all")
  • \(1 + x\)
• Choice: 0 to \(k\) (e.g., "use item A up to \(k\) times")
  • \(1 + x + x^2 + \dots + x^k = \frac{1 - x^{k+1}}{1-x}\)

• Choice: Infinite Supply (e.g., "use item A any number of times")

  • \(1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}\)
  • Why? (The Geometric Series Formula): This is the most important formula. It states that the infinite sum \(1 + x + x^2 + \dots\) (where \(|x| < 1\)) is equal to \(\frac{1}{1-x}\).
  • Proof:
    1. Let \(S = 1 + x + x^2 + x^3 + \dots\)
    2. Multiply \(S\) by \(x\): \(xS = x + x^2 + x^3 + \dots\)
    3. Subtract the two equations: \(S - xS = (1 + x + x^2 + \dots) - (x + x^2 + \dots)\)
    4. This leaves: \(S - xS = 1\)
    5. Factor out \(S\): \(S(1 - x) = 1\)
    6. Solve for \(S\): \(S = \frac{1}{1-x}\)
  • Counting Meaning: The series \(f(x) = 1 + x + x^2 + \dots\) has a coefficient of 1 for every term. This means there is 1 way to choose 0 of the item, 1 way to choose 1 of the item, 1 way to choose 2, and so on. This is the perfect representation for an "infinite supply" of an item.

• Choice: At least one

  • \(x + x^2 + x^3 + \dots = x(1 + x + x^2 + \dots) = \frac{x}{1-x}\)

EGF Building Blocks

• Choice: 0 or 1 (e.g., "use item A once or not at all")
  • \(1 + \frac{x}{1!} = 1+x\)
• Choice: Any number (0, 1, 2, ...):
  • \(1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = e^x\)
• Choice: At least one (1, 2, 3, ...):
  • \(\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = (e^x - 1)\)
• Choice: An Even number (0, 2, 4, ...):
  • \(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \dots = \frac{e^x + e^{-x}}{2}\)
• Choice: An Odd number (1, 3, 5, ...):
  • \(\frac{x}{1!} + \frac{x^3}{3!} + \frac{x^5}{5!} + \dots = \frac{e^x - e^{-x}}{2}\)

---

5. Key Coefficient Formulas (OGF)

This is a cheat-sheet for quickly finding the coefficient \([x^n]\) (the "answer for \(n\)") in common OGF forms.

1. The Basic (Infinite Supply)

This is the series \(f(x) = 1 + 1x + 1x^2 + 1x^3 + \dots\) \(f(x) = \frac{1}{1-x}\) \([x^n] \frac{1}{1-x} = 1\)

2. Scaled Input

This is the series \(f(x) = 1 + (ax) + (ax)^2 + \dots = 1 + ax + a^2x^2 + a^3x^3 + \dots\) \(f(x) = \frac{1}{1-ax}\) \([x^n] \frac{1}{1-ax} = a^n\)

3. Powers of the Basic (Combinations with Repetition)

This is the most powerful OGF formula. It represents choosing \(n\) items from \(k\) distinct types, with infinite supply. \(f(x) = \frac{1}{(1-x)^k} = \left(\frac{1}{1-x}\right) \times \dots \times \left(\frac{1}{1-x}\right) \quad (k \text{ times})\) The formula for the coefficient is: \([x^n] \frac{1}{(1-x)^k} = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}\) * Intuition (Stars and Bars): This is the exact formula for choosing \(n\) items from \(k\) types with repetition. It's the number of ways to put \(n\) identical "stars" (items) into \(k\) distinct "bins" (types). You arrange \(n\) stars and \(k-1\) "bars" (dividers). The total number of arrangements is \(\binom{n+(k-1)}{k-1}\).

• Example (Quiz 1): Buying 12 donuts from 3 types.
  • \(f(x) = (\frac{1}{1-x})^3\). Here \(n=12\) and \(k=3\).
  • Answer: \([x^{12}]f(x) = \binom{12+3-1}{3-1} = \binom{14}{2} = \frac{14 \times 13}{2} = 91\).

---

6. Summary: OGF vs. EGF

Feature	Ordinary Generating Function (OGF)	Exponential Generating Function (EGF)
Form	\(\sum a_n x^n\)	\(\sum a_n \frac{x^n}{n!}\)
Use For	Combinations (order doesn't matter)	Permutations (order matters)
Keywords	Bags, piles, collections, making change	Words, sequences, arrangements, labeled objects
Multiplication	Combines two unlabeled collections	Combines two labeled arrangements

---

Generating Functions: Practice & Quizzes

(Note: \([x^n]f(x)\) means "the coefficient of the \(x^n\) term in the polynomial \(f(x)\)")

---

OGF Practice Problems (Order Doesn't Matter)

Example 1: Buying Fruit (with limits)

• Problem: You can buy 0-2 apples, 0-1 bananas, and 0-1 orange. How many ways are there to buy \(n\) pieces of fruit?
• Setup: This is (Choice of Apples) AND (Choice of Bananas) AND (Choice of Oranges). So, we multiply.
  • Apples (A): 0 apples (\(x^0\)) OR 1 apple (\(x^1\)) OR 2 apples (\(x^2\)).
    • \(A(x) = 1 + x + x^2\)
  • Bananas (B): 0 bananas (\(x^0\)) OR 1 banana (\(x^1\)).
    • \(B(x) = 1 + x\)
  • Oranges (O): 0 oranges (\(x^0\)) OR 1 orange (\(x^1\)).
    • \(O(x) = 1 + x\)
• Total Function: \(f(x) = A(x) \times B(x) \times O(x)\)
  • \(f(x) = (1 + x + x^2)(1 + x)(1 + x) = (1 + x + x^2)(1 + 2x + x^2)\)
  • \(f(x) = 1(1+2x+x^2) + x(1+2x+x^2) + x^2(1+2x+x^2)\)
  • \(f(x) = 1 + 2x + x^2 + x + 2x^2 + x^3 + x^2 + 2x^3 + x^4\)
  • \(f(x) = \mathbf{1} + \mathbf{3}x + \mathbf{4}x^2 + \mathbf{3}x^3 + \mathbf{1}x^4\)
• Answer: The coefficient of \(x^n\) is your answer. For \(n=2\):
  • The term is \(4x^2\). This means there are 4 ways to buy 2 pieces of fruit.
  • (Verification: (2A, 0B, 0O), (1A, 1B, 0O), (1A, 0B, 1O), (0A, 1B, 1O)).

Example 2: Infinite Supply (Coin Change)

• Problem: You have an infinite supply of 1-cent and 2-cent coins. How many ways can you make \(n\) cents?
• Principle: This is (Choice of 1-cent coins) AND (Choice of 2-cent coins).
• 1-cent coins (A): You can take 0, 1, 2, 3...
  • \(A(x) = 1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}\)
• 2-cent coins (B): You can take 0 (cost 0), 1 (cost 2), 2 (cost 4)...
  • \(B(x) = 1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}\)
• Setup: \(f(x) = A(x) \times B(x) = (\frac{1}{1-x}) (\frac{1}{1-x^2})\)
• Answer: The number of ways to make \(n\) cents is \([x^n]f(x)\).

Example 3: Rolling Dice

• Problem: You roll two standard 6-sided dice. How many ways are there to get a sum of \(n\)?
• Principle: This is (Outcome of Die 1) AND (Outcome of Die 2).
• Die 1 (A): The possible outcomes (states) are 1, 2, 3, 4, 5, or 6.
  • \(A(x) = x^1 + x^2 + x^3 + x^4 + x^5 + x^6\)
• Die 2 (B): Same as Die 1.
  • \(B(x) = x^1 + x^2 + x^3 + x^4 + x^5 + x^6\)
• Setup: \(f(x) = A(x) \times B(x) = (x + x^2 + x^3 + x^4 + x^5 + x^6)^2\)
• Answer: To find the ways to get a sum of 4, we need \([x^4]f(x)\).
  • From the expansion \((x + x^2 + \dots)(x + x^2 + \dots)\), the terms that make \(x^4\) are:
  • \(x^1 \cdot x^3\)
  • \(x^2 \cdot x^2\)
  • \(x^3 \cdot x^1\)
  • The coefficient is 3. (The rolls are 1+3, 2+2, 3+1).

---

EGF Practice Problems (Order Matters)

Example 1: Forming a Word (Simple)

• Problem: How many 3-letter "words" can you make using the letters \(\{A, B, C\}\), where you can use each letter at most once?
• Principle: (Choice of 'A') AND (Choice of 'B') AND (Choice of 'C').
• 'A' (A): Use 'A' 0 times (\(1 \frac{x^0}{0!}\)) OR use 'A' 1 time (\(1 \frac{x^1}{1!}\)).
  • \(A(x) = 1 + x\)
• 'B' (B): \(B(x) = 1 + x\)
• 'C' (C): \(C(x) = 1 + x\)
• Total Function: \(f(x) = (1+x)(1+x)(1+x) = 1 + 3x + 3x^2 + 1x^3\)
• Rewrite in EGF form:
  • \(f(x) = 1 \frac{x^0}{0!} + 3 \frac{x^1}{1!} + (3 \times \mathbf{2!}) \frac{x^2}{\mathbf{2}!} + (1 \times \mathbf{3!}) \frac{x^3}{\mathbf{3}!}\)
  • \(f(x) = \mathbf{1} \frac{x^0}{0!} + \mathbf{3} \frac{x^1}{1!} + \mathbf{6} \frac{x^2}{2!} + \mathbf{6} \frac{x^3}{3!}\)
• Answer: The coefficient \(a_n\) of \(\frac{x^n}{n!}\) is the answer.
  • For \(n=3\) (\(a_3\)): There are 6 arrangements ("ABC", "ACB", "BAC", "BCA", "CAB", "CBA").
  • For \(n=2\) (\(a_2\)): There are 6 arrangements ("AB", "BA", "AC", "CA", "BC", "CB").

Example 2: Word with Repeated Letters

• Problem: How many 3-letter arrangements can be made from the letters in "EEL"?
• Principle: (Choice of 'E') AND (Choice of 'L').
• 'E' (A): You can use 0, 1, or 2 'E's.
  • \(A(x) = \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} = 1 + x + \frac{x^2}{2}\)
• 'L' (B): You can use 0 or 1 'L'.
  • \(B(x) = \frac{x^0}{0!} + \frac{x^1}{1!} = 1 + x\)
• Setup: \(f(x) = A(x) \times B(x) = (1 + x + \frac{x^2}{2})(1 + x)\)
  • \(f(x) = 1(1+x) + x(1+x) + \frac{x^2}{2}(1+x)\)
  • \(f(x) = 1 + x + x + x^2 + \frac{x^2}{2} + \frac{x^3}{2} = 1 + 2x + \frac{3}{2}x^2 + \frac{1}{2}x^3\)
• Rewrite in EGF form:
  • \(f(x) = \mathbf{1}\frac{x^0}{0!} + \mathbf{2}\frac{x^1}{1!} + (\frac{3}{2} \cdot 2!)\frac{x^2}{2!} + (\frac{1}{2} \cdot 3!)\frac{x^3}{3!}\)
  • \(f(x) = \mathbf{1}\frac{x^0}{0!} + \mathbf{2}\frac{x^1}{1!} + \mathbf{3}\frac{x^2}{2!} + \mathbf{3}\frac{x^3}{3!}\)
• Answer: The coefficient \(a_n\) of \(\frac{x^n}{n!}\) is the answer.
  • For \(n=3\) (\(a_3\)): There are 3 arrangements ("EEL", "ELE", "LEE").
  • For \(n=2\) (\(a_2\)): There are 3 arrangements ("EE", "EL", "LE").

---

🧠 Quiz: Test Your Understanding

For each problem, just figure out the generating function setup. You don't need to find the final coefficient.

---

Question 1: The Donut Shop (OGF)

A bakery sells 3 types of donuts: Glazed, Chocolate, and Strawberry. You want to buy a box of a dozen (12) donuts. What is the generating function \(f(x)\) where the answer to the problem is \([x^{12}]f(x)\)? (Assume an infinite supply of each donut).

• Analysis: This is an OGF problem (order in the box doesn't matter). It's (Glazed choice) AND (Chocolate choice) AND (Strawberry choice).
• Glazed: \(1 + x + x^2 + \dots = \frac{1}{1-x}\)
• Chocolate: \(1 + x + x^2 + \dots = \frac{1}{1-x}\)
• Strawberry: \(1 + x + x^2 + \dots = \frac{1}{1-x}\)
• Setup: \(f(x) = (\frac{1}{1-x}) (\frac{1}{1-x}) (\frac{1}{1-x}) = (\frac{1}{1-x})^3\)
• Answer: \([x^{12}] (\frac{1}{1-x})^3\)

---

Question 2: The Password (EGF)

You are creating a 5-letter password. You can use the letters {A, B, C}. You must use 'A' at least once, 'B' at most once (i.e., 0 or 1 times), and 'C' any number of times. What is the setup \(f(x)\) where the answer is the coefficient of \(\frac{x^5}{5!}\)?

• Analysis: This is an EGF problem (order in a password matters).
• 'A' (at least once): \(\frac{x}{1!} + \frac{x^2}{2!} + \dots = (e^x - 1)\)
• 'B' (at most once): \(\frac{x^0}{0!} + \frac{x^1}{1!} = (1 + x)\)
• 'C' (any): \(\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \dots = e^x\)
• Setup: \(f(x) = (e^x - 1)(1 + x)(e^x)\)
• Answer: Find the coefficient \(a_5\) where \(f(x) = \sum a_n \frac{x^n}{n!}\).

---

Question 3: Bag vs. Pole (OGF vs. EGF)

You have 4 red flags and 3 blue flags (flags of the same color are identical).

• (a) How many ways to choose 5 flags to put in a bag?
• (b) How many ways to arrange 5 flags on a pole?

What are the two different setups for (a) and (b)?

• (a) The Bag (OGF): Order doesn't matter.

  • Red (max 4): \((1 + x + x^2 + x^3 + x^4)\)
  • Blue (max 3): \((1 + x + x^2 + x^3)\)
  • Setup: \(f(x) = (1 + x + x^2 + x^3 + x^4)(1 + x + x^2 + x^3)\)
  • Answer: \([x^5]f(x)\)

• (b) The Pole (EGF): Order matters.

  • Red (max 4): \((1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!})\)
  • Blue (max 3): \((1 + x + \frac{x^2}{2!} + \frac{x^3}{3!})\)
  • Setup: \(g(x) = (1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!})(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!})\)
  • Answer: The coefficient of \(\frac{x^5}{5!}\) in \(g(x)\).

---

Question 4: Sum of 3 Dice (OGF)

You roll three 4-sided dice (numbered 1 to 4). What is the generating function \(f(x)\) for the sum of the rolls, where \([x^n]f(x)\) is the number of ways to get a sum \(n\)?

• Analysis: This is an OGF problem (sum). It's (Die 1) AND (Die 2) AND (Die 3).
• One Die: \((x^1 + x^2 + x^3 + x^4)\)
• Setup: \(f(x) = (x + x^2 + x^3 + x^4)^3\)
• Answer: \([x^n] (x + x^2 + x^3 + x^4)^3\)