Skip to content

Generating Functions - Practice

Here are the problem sets you wanted to solve:

🌀 Generating Functions: A Unified Editorial

Generating functions are one of the most powerful tools in combinatorics. They convert a complex counting problem into an algebraic one, allowing us to use operations like polynomial multiplication and expansion to find our answer.

We will explore two main types:

  • Ordinary Generating Functions (OGF): Used for problems involving unlabeled items (e.g., "distribute \(n\) identical candies"). The coefficient of \(z^n\) represents the answer for a problem of size \(n\).

  • Exponential Generating Functions (EGF): Used for problems involving labeled items (e.g., "distribute \(n\) unique candies"). The coefficient of \(x^n/n!\) represents the answer.

Ordinary Generating Functions (OGF)

These problems typically boil down to finding the number of integer solutions to an equation, often with constraints.

1. 🧩 FPS - B - Tuple of Integers (Difficulty: Easy)

Problem: Find the number of non-negative integer quadruples \((a,b,c,d)\) that satisfy \(a+b+c+d=N\) with the constraints:

  • \(a \in \{0, 1\}\)

  • \(b \in \{0, 1, 2\}\)

  • \(c\) is even (\(c \in \{0, 2, 4, ...\}\))

  • \(d\) is a multiple of 3 (\(d \in \{0, 3, 6, ...\}\))

1. Build the Generating Functions (one for each variable):

  • \(G_a(z) = (z^0 + z^1) = \mathbf{1 + z}\)

  • \(G_b(z) = (z^0 + z^1 + z^2) = \mathbf{\frac{1 - z^3}{1 - z}}\)

  • \(G_c(z) = (z^0 + z^2 + z^4 + ...) = \frac{1}{1 - z^2} = \mathbf{\frac{1}{(1-z)(1+z)}}\)

  • \(G_d(z) = (z^0 + z^3 + z^6 + ...) = \mathbf{\frac{1}{1 - z^3}}\)

2. Combine and Simplify (The "Aha!" Moment): The total generating function \(G(z)\) is the product of all four. We are looking for \([z^N] G(z)\).

\[ G(z) = G_a(z) \cdot G_b(z) \cdot G_c(z) \cdot G_d(z) \]
\[ G(z) = (\mathbf{1+z}) \cdot \left(\mathbf{\frac{1 - z^3}{1 - z}}\right) \cdot \left(\mathbf{\frac{1}{(1-z)(1+z)}}\right) \cdot \left(\mathbf{\frac{1}{1 - z^3}}\right) \]

3. Find the Coefficient of \(z^N\): After cancellation, all that remains is:

\[ G(z) = \frac{1}{1 - z} \cdot \frac{1}{1 - z} = \frac{1}{(1 - z)^2} = (1 - z)^{-2} \]

We need to find \([z^N]\) in \((1 - z)^{-2}\). From the "stars and bars" formula, the coefficient of \(z^k\) in \((1-z)^{-n}\) is \(\binom{n+k-1}{n-1}\). Here, \(n=2\) and \(k=N\).

\[ \text{Coefficient} = \binom{2 + N - 1}{2 - 1} = \binom{N + 1}{1} \]

Answer: The number of ways is \(N+1\). (The final answer is \((N+1) \pmod{998244353}\)).

2. 🍭 Candies for 3 Children (Difficulty: Easy)

Problem: Find the number of ways to distribute \(n\) identical candies to 3 children such that no child gets more than \(\text{limit}\) candies.

1. Formulate the Equation: \(x_1 + x_2 + x_3 = n\), with \(0 \le x_i \le \text{limit}\).

2. Build the Generating Function: The choices for a single child are \((z^0 + z^1 + ... + z^{\text{limit}}) = \frac{1 - z^{\text{limit} + 1}}{1 - z}\). The total \(G(z)\) for 3 children is:

\[ G(z) = \left( \frac{1 - z^{\text{limit} + 1}}{1 - z} \right)^3 = (1 - z^{\text{limit} + 1})^3 \times (1 - z)^{-3} \]

3. Find the Coefficient of \(z^n\):

  • Part A: \(A(z) = (1 - z^{\text{limit} + 1})^3 = \mathbf{1} - \mathbf{3}z^{\text{limit} + 1} + \mathbf{3}z^{2(\text{limit} + 1)} - \mathbf{1}z^{3(\text{limit} + 1)}\)

  • Part B: \(B(z) = (1 - z)^{-3} = \sum_{k=0}^{\infty} \binom{k + 2}{2} z^k\)

  • Combine: We match terms from \(A(z)\) and \(B(z)\) to get \(z^n\):

    • From \(\mathbf{1}\): Contribution: \(\mathbf{+1} \times \binom{n + 2}{2}\)

    • From \(\mathbf{-3}z^{\text{limit} + 1}\): Contribution: \(\mathbf{-3} \times \binom{(n - (\text{limit} + 1)) + 2}{2}\)

    • ...and so on.

Answer: The total number of ways is the sum of the four contributions, where \(\binom{N}{K} = 0\) if \(N < K\).

3. 🎲 Dice Roll Target Sum (Difficulty: Medium)

Problem: You have \(n\) dice, each with \(k\) faces (1 to \(k\)). Find the number of ways to get a sum of \(\text{target}\).

1. Formulate the Equation: \(x_1 + x_2 + ... + x_n = \text{target}\), with \(1 \le x_i \le k\).

2. Build the Generating Function: The choices for a single die are \((z^1 + z^2 + ... + z^k) = z \frac{1 - z^k}{1 - z}\). The total \(G(z)\) for \(n\) dice is:

\[ G(z) = \left[ z \left( \frac{1 - z^k}{1 - z} \right) \right]^n = z^n \times (1 - z^k)^n \times (1 - z)^{-n} \]

3. Find the Coefficient of \(z^{\text{target}}\): We need \([z^{\text{target}}] G(z)\), which is the same as \([z^{\text{target} - n}]\) in \((1 - z^k)^n \times (1 - z)^{-n}\). Let \(T = \text{target} - n\).

  • Part A: \(A(z) = (1 - z^k)^n = \sum_{j=0}^{n} \binom{n}{j} (-1)^j z^{kj}\)

  • Part B: \(B(z) = (1 - z)^{-n} = \sum_{m=0}^{\infty} \binom{n + m - 1}{n - 1} z^m\)

  • Combine: We iterate through each term \(j\) from \(A(z)\):

    • Contribution for term \(j\): \(\binom{n}{j}(-1)^j \times \binom{n + (T - kj) - 1}{n - 1}\)

Answer: The total number of ways is the sum of these contributions over \(j\) from \(0\) to \(n\):

\[ \text{Ways} = \sum_{j=0}^{n} (-1)^j \binom{n}{j} \binom{\text{target} - kj - 1}{n - 1} \]

4. 🔢 FPS - C - Integer Sequence with Sum (Difficulty: Medium)

Problem: Find the number of sequences of length \(N\) (\(x_1, ..., x_N\)) with total sum \(S\), where \(0 \le x_i \le M\).

1. Formulate the Equation: This is a direct application. Find solutions to: \(x_1 + x_2 + ... + x_N = S\) Constraint: \(0 \le x_i \le M\) for each \(i\).

2. Build the Generating Function: The choices for a single element \(x_i\) are \((z^0 + z^1 + ... + z^M) = \frac{1 - z^{M+1}}{1 - z}\). The total \(G(z)\) for \(N\) elements is:

\[ G(z) = \left( \frac{1 - z^{M+1}}{1 - z} \right)^N = (1 - z^{M+1})^N \times (1 - z)^{-N} \]

3. Find the Coefficient of \(z^S\): We need \([z^S] G(z)\). This is identical in form to the Dice Roll problem.

  • Part A: \(A(z) = (1 - z^{M+1})^N = \sum_{j=0}^{N} \binom{N}{j} (-1)^j z^{j(M+1)}\)

  • Part B: \(B(z) = (1 - z)^{-N} = \sum_{k=0}^{\infty} \binom{N + k - 1}{N - 1} z^k\)

  • Combine: To find \([z^S]\), we iterate through each term \(j\) from \(A(z)\):

    • Term \(j\) from \(A(z)\): \(\binom{N}{j}(-1)^j z^{j(M+1)}\)

    • Needed from \(B(z)\): We need \(z^k\) where \(k = S - j(M+1)\).

    • Coefficient from \(B(z)\): \(\binom{N + k - 1}{N - 1} = \binom{N + (S - j(M+1)) - 1}{N - 1}\)

    • Contribution for term \(j\): \(\binom{N}{j}(-1)^j \times \binom{N + S - j(M+1) - 1}{N - 1}\)

Answer: The total number of ways is the sum over \(j\):

\[ \text{Ways} = \sum_{j=0}^{\min(N, \lfloor S/(M+1) \rfloor)} (-1)^j \binom{N}{j} \binom{N + S - j(M+1) - 1}{N - 1} \]

This requires precomputing factorials up to \(N+S\) to calculate the binomials. The loop runs at most \(O(\min(N, S))\) times.

5. 🌸 Devu's Flower Selection (Difficulty: Medium)

Problem: Find the number of ways to select exactly \(s\) flowers from \(n\) boxes, where box \(i\) has \(f_i\) indistinguishable flowers.

1. Formulate the Equation: \(x_1 + x_2 + ... + x_n = s\), with \(0 \le x_i \le f_i\).

2. Build the Generating Function: The choices for box \(i\) are \((z^0 + z^1 + ... + z^{f_i}) = \frac{1 - z^{f_i + 1}}{1 - z}\). The total \(G(z)\) is the product of all \(n\) boxes:

\[ G(z) = \prod_{i=1}^{n} \left( \frac{1 - z^{f_i + 1}}{1 - z} \right) = \left( \prod_{i=1}^{n} (1 - z^{f_i + 1}) \right) \times (1 - z)^{-n} \]

3. Find the Coefficient of \(z^s\):

  • Part A: \(A(z) = \prod_{i=1}^{n} (1 - z^{f_i + 1})\) Expanding this product gives \(2^n\) terms, each corresponding to a subset \(S\) of the boxes.

  • Part B: \(B(z) = (1 - z)^{-n} = \sum_{k=0}^{\infty} \binom{n+k-1}{n-1} z^k\)

  • Combine: To find \([z^s]\), we iterate through all \(2^n\) terms in \(A(z)\) (using a bitmask). For each subset \(S\):

    • Let \(power(S) = \sum_{i \in S} (f_i + 1)\).

    • Let \(k_S = s - power(S)\).

    • The contribution is: \((-1)^{|S|} \times \binom{n + k_S - 1}{n - 1}\).

Answer: The total number of ways is the sum of these contributions over all \(2^n\) subsets \(S\).

6. 🥨 FPS - A - Snack (Difficulty: Medium)

Problem: For \(D\) days, you choose one action with cost \(c \in \{1, 3, 4, 6\}\). Find the number of sequences of choices such that the total cost is \(N\).

1. Formulate the Equation: \(x_1 + x_2 + ... + x_D = N\), with \(x_i \in \{1, 3, 4, 6\}\).

2. Build the Generating Function: The choices for a single day are \(P(z) = (z^1 + z^3 + z^4 + z^6)\). The total \(G(z)\) for \(D\) distinct days is \(G(z) = (P(z))^D\). We need \([z^N] G(z)\).

3. The Key Simplification: \(P(z) = z + z^3 + z^4 + z^6 = z(1 + z^2) + z^4(1 + z^2) = \mathbf{z(1 + z^2)(1 + z^3)}\)

4. Apply the Factorization:

\[ G(z) = (z(1 + z^2)(1 + z^3))^D = z^D \cdot (1 + z^2)^D \cdot (1 + z^3)^D \]

5. Find the Coefficient \(z^N\): We need \([z^N] G(z)\), which is the same as \([z^{N-D}]\) in \(H(z) = (1 + z^2)^D \cdot (1 + z^3)^D\). Let \(K = N - D\).

  • \(A(z) = (1 + z^2)^D = \sum_{i=0}^{D} \binom{D}{i} z^{2i}\)

  • \(B(z) = (1 + z^3)^D = \sum_{j=0}^{D} \binom{D}{j} z^{3j}\)

To find \([z^K]\) in \(A(z)B(z)\), we need all pairs \((i, j)\) such that \(2i + 3j = K\).

Answer (Algorithm): Iterate \(i\) from \(0\) to \(D\).

  1. Calculate \(p_A = 2i\).

  2. Calculate the needed power from \(B\): \(p_B = K - p_A\).

  3. If \(p_B < 0\) or \(p_B \pmod 3 \neq 0\), continue.

  4. Calculate \(j = p_B / 3\).

  5. If \(j > D\), continue.

  6. Add the contribution: \(\text{total_ways} = (\text{total_ways} + \binom{D}{i} \times \binom{D}{j}) \pmod{\text{MOD}}\)

This runs in \(O(D)\) time after precomputing factorials.

7. 🧠 FPS - D - Sequence 2 (Difficulty: Hard)

Problem: Find the number of sequences \(A = (a_1, ..., a_N)\) with \(0 \le a_i \le M\) such that its sorted version \(B = (b_1, ..., b_N)\) alternates in parity.

1. Reframe the Problem (The "Gaps" Method) Consider a "path" from \(0\) to \(M\): \(0 \xrightarrow{d_0} b_1 \xrightarrow{d_1} b_2 \xrightarrow{d_2} ... \xrightarrow{d_{N-1}} b_N \xrightarrow{d_N} M\)

We define \(N+1\) gaps:

  • \(d_0 = b_1 - 0 = b_1\)

  • \(d_i = b_{i+1} - b_i\) (for \(1 \le i \le N-1\))

  • \(d_N = M - b_N\)

The sum of all these gaps must be \(M\):

\[ d_0 + d_1 + d_2 + ... + d_N = M \]

2. Analyze the Gap Constraints

  • Gap \(d_0\): \(d_0 = b_1 \ge 0\). Non-negative integer.

    • OGF: \(G_0(z) = (z^0 + z^1 + z^2 + ...) = 1/(1-z)\)

  • Gap \(d_N\): \(d_N = M - b_N \ge 0\). Non-negative integer.

    • OGF: \(G_N(z) = (z^0 + z^1 + z^2 + ...) = 1/(1-z)\)

  • Gaps \(d_i\) (for \(1 \le i \le N-1\)):

    • \(b_{i+1}\) and \(b_i\) have different parity and \(b_{i+1} > b_i\).

    • The difference \(d_i = b_{i+1} - b_i\) must be a positive odd integer (\(1, 3, 5, ...\)).

    • OGF for one gap: \(G_{gap}(z) = (z^1 + z^3 + z^5 + ...) = z/(1-z^2)\)

3. Build the Total Generating Function The total OGF is the product of the OGFs for all \(N+1\) gaps. We are looking for \([z^M] G(z)\).

\[ G(z) = G_0(z) \cdot (G_{gap}(z))^{N-1} \cdot G_N(z) \]
\[ G(z) = \left(\frac{1}{1-z}\right) \cdot \left(\frac{z}{1-z^2}\right)^{N-1} \cdot \left(\frac{1}{1-z}\right) \]
\[ G(z) = \frac{z^{N-1}}{(1-z)^2 \cdot (1-z^2)^{N-1}} \]

The answer for the number of valid sorted sequences \(B\) is \([z^M] G(z)\).

4. Find the Coefficient \(z^M\) (The Algorithm) We need to find \([z^M]\) in \(G(z) = P(z) \cdot C(z)\), where:

  • \(P(z) = z^{N-1} (1-z^2)^{-(N-1)}\)

  • \(C(z) = (1-z)^{-2}\)

We can compute the coefficients \(p_k = [z^k] P(z)\) up to \(k=M\) in \(O(M)\) time:

  • Loop \(i\) from 0.

  • Let \(k = 2i + N - 1\). If \(k > M\), break.

  • \(p_k = \binom{N+i-2}{i}\).

Multiplying by \(C(z) = (1-z)^{-2}\) is equivalent to taking the prefix sum of the coefficients, twice. Let \(p_k\) be the coefficients of \(P(z)\). Let \(s_k\) be the coefficients of \(P(z)(1-z)^{-1}\). Then \(s_k = \sum_{i=0}^k p_i\). Let \(ans_k\) be the coefficients of \(P(z)(1-z)^{-2}\). Then \(ans_k = \sum_{i=0}^k s_i\).

Answer:

  1. Precompute factorials.

  2. Compute the coefficients \(p_k\) of \(P(z)\) up to \(M\).

  3. Compute the prefix sum of \(p_k\) to get \(s_k\).

  4. Compute the prefix sum of \(s_k\) to get \(ans_k\).

  5. The number of valid sorted sets \(B\) is ans[M].

  6. The final answer (for all sequences \(A\)) is (ans[M] * N!) % MOD.

8. 📮 Buying Stamps (Difficulty: Hard)

Problem Link: https://www.acmicpc.net/problem/13542

Problem: Find the number of ways to buy exactly \(K\) yen worth of stamps. We have \(N\) types of 1-yen stamps and \(M\) types of 2-yen stamps. \(N, M \le 300\) and \(K \le 10^{12}\). Answer modulo \(P\).

1. Build and Simplify the OGF:

  • The OGF for all \(N\) 1-yen types is \(G_1(z) = (1-z)^{-N}\).

  • The OGF for all \(M\) 2-yen types is \(G_2(z) = (1-z^2)^{-M}\).

  • The total OGF is \(G(z) = G_1(z) \cdot G_2(z) = (1-z)^{-N} (1-z^2)^{-M}\).

  • We can simplify this: $$ G(z) = \frac{1}{(1-z)^N (1-z^2)^M} = \frac{1}{(1-z)^{N+M} (1+z)^M} $$

2. Use Partial Fraction Expansion: The constraint \(K \le 10^{12}\) means any \(O(K)\) algorithm is too slow. We must use partial fraction decomposition.

\[ G(z) = \sum_{i=1}^{N+M} \frac{c_i}{(1-z)^i} + \sum_{j=1}^{M} \frac{d_j}{(1+z)^j} \]

The coefficients \(c_i\) and \(d_j\) depend only on \(N\) and \(M\) and can be calculated in \(O((N+M)^2)\) time.

3. Find the Coefficient of \(z^K\): We can find \([z^K]\) for each simple term, even for a huge \(K\).

  • \([z^K] \frac{1}{(1-z)^i} = \binom{K+i-1}{K} = \binom{K+i-1}{i-1}\)

  • \([z^K] \frac{1}{(1+z)^j} = (-1)^K \binom{K+j-1}{K} = (-1)^K \binom{K+j-1}{j-1}\)

The final answer \(a_K = [z^K]G(z)\) is the sum of these coefficients:

\[ a_K = \sum_{i=1}^{N+M} c_i \binom{K+i-1}{i-1} + (-1)^K \sum_{j=1}^{M} d_j \binom{K+j-1}{j-1} \]

4. The \(O((N+M)^2)\) Algorithm:

  1. Find \(c_i, d_j\): Use standard methods for partial fractions to find all \(c_i\) and \(d_j\) coefficients.

  2. Compute Combinations: The term \(\binom{K+i-1}{i-1}\) involves a large \(K\) but a small \(i-1\). We can compute it directly (modulo \(P\)):

    \[ \binom{K+i-1}{i-1} = \frac{(K+i-1)(K+i-2)...(K+1)}{(i-1)!} \]

    This is a product of \(i-1\) terms, which takes \(O(i)\) time.

  3. Sum the results: The total time to sum the terms is \(O((N+M)^2 + M^2)\).

Answer: The total complexity is \(O((N+M)^2)\), which is extremely fast and independent of \(K\).

🧬 Exponential Generating Functions (EGF)

These problems involve labeled items, meaning permutations and set partitions matter. The coefficient of \(x^n/n!\) represents the answer.

9. 🎨 FPS - F - Colored Paper (Difficulty: Medium)

Problem: Find the number of ways to color \(N\) distinct sheets of paper Red, Blue, or Yellow such that the number of Blue sheets is even and the number of Yellow sheets is odd.

1. Build the EGF for Each Color: We are assigning \(N\) distinct items (sheets) to 3 "bins" (colors) with constraints.

  • Red (no constraint): \(0, 1, 2, ...\) sheets. \(R(x) = \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x\)

  • Blue (even): \(0, 2, 4, ...\) sheets. \(B(x) = \sum_{n \text{ even}}^{\infty} \frac{x^n}{n!} = \frac{e^x + e^{-x}}{2}\)

  • Yellow (odd): \(1, 3, 5, ...\) sheets. \(Y(x) = \sum_{n \text{ odd}}^{\infty} \frac{x^n}{n!} = \frac{e^x - e^{-x}}{2}\)

2. Combine and Simplify the Total EGF: The total EGF is \(G(x) = R(x) \cdot B(x) \cdot Y(x)\). We are looking for the coefficient of \(x^N/N!\).

\[ G(x) = (e^x) \cdot \left(\frac{e^x + e^{-x}}{2}\right) \cdot \left(\frac{e^x - e^{-x}}{2}\right) \]
\[ G(x) = \frac{e^x}{4} \cdot ( (e^x)^2 - (e^{-x})^2 ) \]
\[ G(x) = \frac{e^x}{4} \cdot (e^{2x} - e^{-2x}) \]
\[ G(x) = \frac{1}{4} (e^{3x} - e^{-x}) \]

3. Find the Coefficient of \(x^N/N!\): We expand \(G(x)\) back into its series form:

  • \(e^{3x} = \sum_{n=0}^{\infty} \frac{3^n x^n}{n!}\)

  • \(e^{-x} = \sum_{n=0}^{\infty} \frac{(-1)^n x^n}{n!}\)

\[ G(x) = \frac{1}{4} \left( \sum_{n=0}^{\infty} \frac{3^n x^n}{n!} - \sum_{n=0}^{\infty} \frac{(-1)^n x^n}{n!} \right) \]
\[ G(x) = \sum_{n=0}^{\infty} \left( \frac{3^n - (-1)^n}{4} \right) \frac{x^n}{n!} \]

Answer: The number of ways is the coefficient of \(x^N/N!\), which is:

\[ \text{Ways} = \frac{3^N - (-1)^N}{4} \]

This can be computed (modulo \(998244353\)) using modular exponentiation for \(3^N\) and finding the modular inverse of 4 (which is \(748683265\)).

10. 🍬 Candies in Bags (Difficulty: Medium)

Problem: Find the number of ways to distribute \(n\) unique candies into \(k\) identical bags such that no bag is empty.

1. Formulate the Structure: This is the definition of Stirling Numbers of the Second Kind, \(S(n, k)\). We are partitioning a set of \(n\) labeled items into \(k\) non-empty, unlabeled subsets.

2. Build the Generating Function:

  • One Bag: The "structure" is a single non-empty bag. The EGF for this is: \(B(x) = 1\frac{x^1}{1!} + 1\frac{x^2}{2!} + 1\frac{x^3}{3!} + ... = (e^x - 1)\)

  • k Bags: Since the bags are identical (unlabeled), we divide the EGF for \(k\) labeled bags by \(k!\): Total EGF: \(G(x) = \frac{(e^x - 1)^k}{k!}\)

3. Find the Coefficient of \(x^n/n!\):

  • Part A: \((e^x - 1)^k = \sum_{j=0}^{k} \binom{k}{j} (e^x)^j (-1)^{k-j} = \sum_{j=0}^{k} \binom{k}{j} (-1)^{k-j} e^{jx}\)

  • Part B: \(e^{jx} = \sum_{n=0}^{\infty} \frac{j^n x^n}{n!}\)

  • Combine: $$ G(x) = \sum_{n=0}^{\infty} \left( \frac{1}{k!} \sum_{j=0}^{k} \binom{k}{j} (-1)^{k-j} j^n \right) \frac{x^n}{n!} $$

Answer: The coefficient of \(x^n/n!\) is \(S(n, k)\), given by the formula:

\[ S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n \]

This can be computed (modulo \(10^9+7\)) using modular exponentiation and precomputed factorials and their modular inverses.