Course contentsShow
← Mathematics
Lesson 2642 of 3,12152. CombinatoricsFree lesson

Using Generating Functions to Count Distributions

Apply generating functions to count ways of distributing indistinguishable objects into distinct bins.

Using Generating Functions to Count Distributions

You'll learn how generating functions elegantly count the ways to distribute indistinguishable objects into distinct bins with constraints.

The Core Idea

Imagine you have a pile of identical coins and several labeled boxes. You want to count how many ways you can distribute these coins into the boxes, possibly with rules like "box A gets at most 3 coins" or "box B gets an even number."

Generating functions transform this counting problem into algebra. Each box gets its own factor in a product, where the exponents track how many objects go into that box, and the coefficients encode how many ways each distribution can happen.

How It Works

For box i that can receive objects according to some rule, write a generating function representing all possibilities:

  • No restrictions: Box can hold 0, 1, 2, 3,... objects → factor is (1 + x + x² + x³ + ...) = 1/(1-x)
  • At most k objects: (1 + x + x² + ... + xᵏ)
  • Exactly j objects: xʲ
  • Even number: (1 + x² + x⁴ + ...) = 1/(1-x²)

The total generating function is the product of all box factors. The coefficient of xⁿ in the expanded product tells you how many ways to distribute exactly n objects total.

Example

Three distinct bins, unlimited capacity:

G(x) = (1 + x + x² + ...)(1 + x + x² + ...)(1 + x + x² + ...)
     = 1/(1-x)³

Expanding gives coefficients matching C(n+2, 2) — the number of ways to put n indistinguishable objects into 3 distinct bins!

Key Takeaway: Generating functions convert distribution problems into products of power series; the coefficient of xⁿ counts distributions summing to n objects.