Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 36 ยท Projects and Practice

Practice Set: Advanced Counting

Six advanced counting problems solved with partitions, generating functions, Stirling numbers, recurrences and Burnside, plus plots of partition and Catalan growth.

This final set mixes the tools of chapters 5 to 8: partitions, generating functions, Stirling numbers, linear recurrences, Burnside and Fibonacci-type counts. Each answer is checked by code. At the end, two plots show how fast partition numbers and Catalan numbers grow.

Problems

  1. How many partitions of 12 have distinct parts? How many have exactly 4 parts?
  2. In how many ways can four dice sum to 10?
  3. In how many ways can 7 people be split into 3 non-empty teams (teams unlabeled)?
  4. Solve a_n = 3 a_{n-1} - 2 a_{n-2}, a_0 = 1, a_1 = 3.
  5. How many necklaces with 8 beads can be made with 2 colors (rotations equal)?
  6. How many subsets of {1, ..., 12} contain no two consecutive numbers?
Python Solutions checked by computer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions:

  1. 15 partitions of 12 into distinct parts (equal, by Euler's theorem, to the 15 partitions into odd parts), and 15 partitions into exactly 4 parts. See Integer Partitions.
  2. 80. The coefficient of x^10 in (x + x^2 + ... + x^6)^4; see Generating Functions.
  3. 301 = S(7,3) (Stirling numbers).
  4. The characteristic equation r^2 - 3r + 2 = 0 has roots 1 and 2, so a_n = A + B 2^n; the conditions give a_n = 2^(n+1) - 1, and the list 1, 3, 7, 15, ... confirms it (linear recurrences).
  5. 36 necklaces, by Burnside: (1/8)(2^8 + 2^1 + 2^2 + 2^1 + 2^4 + 2^1 + 2^2 + 2^1) = 288/8.
  6. 377. Choosing k non-consecutive numbers from 12 can be done in binom(13 - k, k) ways; the total is the Fibonacci number F_14, the same recurrence as in Recurrence Relations. The bit trick m & (m >> 1) == 0 tests all 2^12 subsets directly.

Growth rates: partitions and Catalan numbers

Counts grow in characteristic ways. p(n) grows like exp(c sqrt n), slower than any exponential a^n but faster than any polynomial. Catalan numbers grow like 4^n / n^(3/2), so the ratio of consecutive terms tends to 4. The plot below draws p(n) against the Hardy-Ramanujan estimate exp(pi sqrt(2n/3)) / (4 n sqrt 3) on a log axis, and the Catalan ratio.

Python Plot the growth of p(n) and Catalan numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At n = 100 the estimate is within 5% of the true p(100) (ratio 0.9563), and the Catalan ratio is 3.8 at n = 28, creeping toward 4 as (4n + 2)/(n + 2).

flowchart LR
    A["Count needed"] --> B["Closed form?"]
    B -->|"yes"| C["Use it, verify small n"]
    B -->|"no"| D["Recurrence or generating function"]
    D --> E["Fast table / DP"]
    D --> F["Asymptotic growth rate"]

From problem to formula to growth.

Where to go next

  • Graph theory: matchings, colorings, spanning trees (Cayley's n^(n-2)), Ramsey numbers.
  • Algebraic combinatorics: symmetric functions, Young tableaux, the hook length formula for the number of standard tableaux.
  • Probabilistic method: prove existence by showing a random object works with positive probability.
  • Designs and codes: finite geometry and error-correcting codes.
  • Enumerative tools: transfer matrices, Polya enumeration (Burnside with weights), species and symbolic method.

You now have the main toolbox: product and sum rules, binomials, inclusion-exclusion, recurrences, generating functions, partitions, Catalan numbers, pigeonhole, Ramsey theory and Burnside. Return to the track page to review any chapter.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. The number of ways to roll a sum of 10 with four dice is the coefficient of x^10 in which polynomial?

    Each die contributes x^1 through x^6; the product of four such factors lists all outcomes by sum.
  2. 2. a(n) = 3a(n-1) - 2a(n-2) with a(0) = 1, a(1) = 3. What is a(4)?

    a(n) = 2^(n+1) - 1, so the sequence is 1, 3, 7, 15, 31 and a(4) = 31.
  3. 3. The ratio C(n+1)/C(n) of Catalan numbers tends to...

    C(n) is about 4^n / (n^1.5 sqrt(pi)), so the ratio approaches 4.
  4. 4. How many subsets of {1..12} have no two consecutive elements?

    The count is the Fibonacci number F(14) = 377.

Summary

  • The advanced tools combine: partitions, generating functions, Stirling numbers, recurrences, Burnside and Fibonacci-type recurrences all appeared in six problems.
  • Each answer was confirmed by an independent brute-force count.
  • Growth rates (Hardy-Ramanujan for p(n), 4^n for Catalan) tell you how big a count gets before you compute it.

Next: Combinatorics track page