Combinatorics path · C10

Before this lesson: Combinations and binomial coefficients, Combinations with repetition, Algebraic identities and factorisation

Your goal: Explain what each factor and exponent counts.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Binomial Theorem and Generating Functions: the key idea

The binomial theorem expands (x+y)n=∑k(nk)xn−kyk(x+y)^{n}=\sum_{k}\binom{n}{k}x^{n-k}y^{k}: choose the k factors supplying y. The multinomial coefficient n!/(a₁!⋯aᵣ!) counts choices yielding x1a1⋯xrarx_{1}^{a_{1}}\cdots x_{r}^{a_{r}} where ∑ai=n\sum a_{i}=n. A generating function records choices by exponent: the coefficient of xnx^{n} in a product counts ways the component choices total n, provided each object is encoded with the correct weight. These are formal polynomial or series calculations; convergence is unnecessary when extracting a coefficient depending on finitely many terms.

A worked example

Find the coefficient of x³ in (1+x)⁵.

Choose x from exactly three of the five factors: the coefficient is C(5,3)=10.

Your turn: change one thing

Use a generating function to count nonnegative x+y=4 with x≤2.

Try this on paper before opening the explanation.

Compare your reasoning

The first variable contributes 1+t+t², the second 1+t+t²+⋯. The coefficient of t⁴ is 3, from first-variable values 0,1,2. Only terms up to t⁴ are needed.

Pause and check

A trap to avoid: Using coefficients as counts without establishing what a term represents.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove the coefficient of xaybzcx^{a}y^{b}z^{c} in (x+y+z)n(x+y+z)^{n} is n!/(a!b!c!) when a+b+c=n.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Each expanded term chooses one symbol from each of n labelled factors. To obtain the required monomial, choose a factors for x, then b of the remaining for y; the rest supply z. The count is C(n,a)C(n−a,b)=n!/(a!b!c!).

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. In a counting generating function, exponents usually record what?

Foundation

  1. The order of alphabetic names
  2. Only negative counts
  3. The quantity being totalled
  4. The colour of the page
Hint

Multiplication adds exponents.

Answer and reasoning

The quantity being totalled. This makes the product encode sums of component quantities.

2. The coefficient of xkx^{k} in (1+x)n(1+x)^{n} is what?

Foundation

  1. knk^{n}
  2. n+k
  3. C(n,k)
  4. n! always
Hint

Choose which factors supply x.

Answer and reasoning

C(n,k). Exactly k of the n factors must contribute x.

3. Coefficient of x³ in (1+x)⁵?

Core

  1. 20
  2. 10
  3. 5
  4. 15
Hint

Use C(5,3).

Answer and reasoning

10. C(5,3)=10.

4. Coefficient of x²y in (x+y)³?

Core

  1. 1
  2. 2
  3. 6
  4. 3
Hint

Choose the one factor supplying y.

Answer and reasoning

3. There are three choices.

5. Coefficient of x²yz in (x+y+z)⁴?

Stretch

  1. 24
  2. 6
  3. 8
  4. 12
Hint

Use the multinomial coefficient.

Answer and reasoning

12. 4!/(2!1!1!)=12.

6. For bounded count 0≤a≤2, which factor records its choices?

Stretch

  1. 1/(1−x) only
  2. x+x²+x³
  3. 2x
  4. 1+x+x²
Hint

Include zero, one and two.

Answer and reasoning

1+x+x². Each allowed value contributes a monomial of that exponent.

7. In multiplying monomials, their exponents do what?

Foundation

  1. Take the maximum
  2. Disappear
  3. Add
  4. Multiply
Hint

Use xaxb=xa+bx^{a}x^{b}=x^{a+b}.

Answer and reasoning

Add. This is why generating-function products encode sums.

8. Coefficient of x² in (1+x)⁴?

Core

  1. 4
  2. 8
  3. 12
  4. 6
Hint

Choose two of four factors.

Answer and reasoning

6. C(4,2)=6.

9. Why can formal series be used without analytic convergence here?

Stretch

  1. Every infinite series converges
  2. The variable must equal one
  3. Coefficients are ignored
  4. A fixed coefficient depends on finitely many contributing terms
Hint

The operation is algebraic coefficient extraction.

Answer and reasoning

A fixed coefficient depends on finitely many contributing terms. For these nonnegative-exponent counting products, only bounded exponents affect a chosen coefficient.

Choose your next step

Continue to Counting with recurrences. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.