Skip to content

Combinatorics -> Inclusion-Exclusion

Count by overlaps, complements, and Mobius-style corrections when direct counting double-counts structure.

  • Topic slug: combinatorics/inclusion-exclusion
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 3
  • Repo companion pages: 0
  • Curated external problems: 6

Microtopics

  • PIE
  • mobius
  • subset-enumeration
  • complement-counting
  • squarefree
  • coprime-pairs

Learning Sources

Source Type
cp-algorithms inclusion-exclusion Reference
USACO Guide PIE Reference
OI Wiki PIE Reference

Practice Sources

Source Type
CSES Prime Multiples Practice
USACO Cowpatibility Practice
CSES Counting Coprime Pairs Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Christmas Party CSES Medium Derangements - - Fixed Points; Permutations; Mod Arithmetic A textbook derangement / inclusion-exclusion task.
Prime Multiples CSES Medium Number Theory, Subset Counting Math; Enumeration Inclusion-Exclusion; LCM Reasoning Multiples; Primes; Prime Set; LCM Direct inclusion-exclusion over prime subsets.
Counting Coprime Pairs CSES Medium-Hard Mobius, Mobius Inversion Number Theory; Sieving Inclusion-Exclusion; Divisor Counting Coprime Pairs; GCD 1; Pair Counting; Number Theory Mobius-inversion version of inclusion-exclusion on gcds.

Practice

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Coprime Codeforces Medium GCD Number Theory; Greedy Pair Reasoning Coprime; Number Theory A lighter coprimality exercise that still rewards divisor-set reasoning.

Stretch

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Coprime Subsequences Codeforces Hard Mobius Combinatorics; Number Theory Inclusion-Exclusion; Prime Factorization Subsequences; Number Theory A strong advanced example where inclusion-exclusion is the heart of the solution.

Cross-Topic

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Counting Necklaces CSES Hard Burnside, Symmetry Counting - - Orbit Counting; Pólya; Rotations Not pure IE, but a strong neighboring symmetry-counting problem.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
LAMP Dàn đèn màu secondary hard density formula; pairwise coprime products; big integer fractions Note Code
PRIMEMULTIPLES Prime Multiples primary medium subset inclusion exclusion; overflow safe lcm product; count divisible numbers Note Code
VOSFENCE Xay hang rao secondary hard bounded compositions; run decomposition; gap distribution Note Code

Regeneration

python3 scripts/generate_problem_catalog.py