api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  slug: combinatorics-fundamentals
  title: Combinatorics Fundamentals
  description: Core counting principles and combinatorial formulas.
  summary: "The counting principles used to enumerate possibilities: the sum and product rules, permutations and combinations (with and without repetition), the pigeonhole principle and the binomial theorem, plus inclusion-exclusion, derangements, stars and bars, Catalan and Stirling numbers. Each entry has the principle, a one-line description and the formula."
  use_when:
    - You need the right counting formula for a probability or algorithm-analysis problem.
    - You are checking whether a count is ordered or unordered, with or without repetition.
  caveats:
    - Formulas assume distinguishable items unless stated; identical items need the multinomial or repetition variants.
    - "Notation varies: C(n, k), nCk and the binomial coefficient all mean the same count."
  related:
    - statistics-basics
    - set-theory-basics
    - complexity-classes
  category: Mathematics
  category_slug: mathematics
  tags: math,combinatorics,counting,permutations,combinations
  view_count: 0
  entry_count: 16
  fields:
    - section: data
      field: principle
      type: string
      example: Product Rule
    - section: data
      field: description
      type: string
      example: If task A has m ways and task B has n ways, bot…
    - section: data
      field: formula
      type: string
      example: m * n
data:
  - principle: Product Rule
    description: If task A has m ways and task B has n ways, both can be done in m * n ways.
    formula: m * n
  - principle: Sum Rule
    description: If tasks are mutually exclusive with m and n ways, total is m + n.
    formula: m + n
  - principle: Permutations
    description: Ordered arrangements of r elements from n items.
    formula: P(n,r) = n! / (n - r)!
  - principle: Combinations
    description: Unordered selections of r elements from n items.
    formula: C(n,r) = n! / (r!(n-r)!)
  - principle: Permutations with Repetition
    description: Arrangements when some elements are identical.
    formula: n! / (n1! * n2! * ... * nk!)
  - principle: Pigeonhole Principle
    description: If n items are placed into m containers and n > m, some container has >= 2 items.
    formula: ceil(n/m)
  - principle: Binomial Theorem
    description: Expansion of (a + b)^n.
    formula: (a+b)^n = Sum C(n,k) * a^(n-k) * b^k
  - principle: Inclusion-Exclusion Principle
    description: Counts the union of sets by adding single sets, subtracting pairwise overlaps, adding triple overlaps, and so on.
    formula: "|A ∪ B| = |A| + |B| − |A ∩ B|"
  - principle: Combinations with Repetition
    description: Choose k items from n types where an item can be chosen more than once and order does not matter.
    formula: C(n + k - 1, k)
  - principle: Stars and Bars
    description: Counts ways to distribute n identical items into k distinct bins.
    formula: C(n + k - 1, k - 1)
  - principle: Multinomial Coefficient
    description: Counts arrangements of n items with k1, k2, ... km identical items of each kind.
    formula: n! / (k1! k2! ... km!)
  - principle: Circular Permutations
    description: Arrangements of n distinct objects around a circle, where rotations count as the same arrangement.
    formula: (n - 1)!
  - principle: Derangements
    description: Permutations in which no element appears in its original position.
    formula: "!n = n! (1 - 1/1! + 1/2! - ... + (-1)^n / n!)"
  - principle: Pascal's Rule
    description: Each binomial coefficient is the sum of the two above it in Pascal's triangle.
    formula: C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
  - principle: Catalan Numbers
    description: Count balanced parentheses, binary trees with n nodes, and monotonic lattice paths that stay on one side of the diagonal.
    formula: C_n = C(2n, n) / (n + 1)
  - principle: Stirling Numbers of the Second Kind
    description: Number of ways to partition n labeled items into k non-empty unlabeled subsets.
    formula: S(n, k) = k S(n - 1, k) + S(n - 1, k - 1)