api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2749
  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[2]: 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[2]: 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[3]: statistics-basics,set-theory-basics,complexity-classes
  entry_count: 16
  fields[3]{section,field,type,example}:
    data,principle,string,Product Rule
    data,description,string,"If task A has m ways and task B has n ways, bot…"
    data,formula,string,m * n
  category: Mathematics
  category_slug: mathematics
  tags: "math,combinatorics,counting,permutations,combinations"
  view_count: 40
  created_at: 1793403093
  updated_at: 1793403093
data[16]{principle,description,formula}:
  Product Rule,"If task A has m ways and task B has n ways, both can be done in m * n ways.",m * n
  Sum Rule,"If tasks are mutually exclusive with m and n ways, total is m + n.",m + n
  Permutations,Ordered arrangements of r elements from n items.,"P(n,r) = n! / (n - r)!"
  Combinations,Unordered selections of r elements from n items.,"C(n,r) = n! / (r!(n-r)!)"
  Permutations with Repetition,Arrangements when some elements are identical.,n! / (n1! * n2! * ... * nk!)
  Pigeonhole Principle,"If n items are placed into m containers and n > m, some container has >= 2 items.",ceil(n/m)
  Binomial Theorem,Expansion of (a + b)^n.,"(a+b)^n = Sum C(n,k) * a^(n-k) * b^k"
  Inclusion-Exclusion Principle,"Counts the union of sets by adding single sets, subtracting pairwise overlaps, adding triple overlaps, and so on.",|A ∪ B| = |A| + |B| − |A ∩ B|
  Combinations with Repetition,Choose k items from n types where an item can be chosen more than once and order does not matter.,"C(n + k - 1, k)"
  Stars and Bars,Counts ways to distribute n identical items into k distinct bins.,"C(n + k - 1, k - 1)"
  Multinomial Coefficient,"Counts arrangements of n items with k1, k2, ... km identical items of each kind.",n! / (k1! k2! ... km!)
  Circular Permutations,"Arrangements of n distinct objects around a circle, where rotations count as the same arrangement.",(n - 1)!
  Derangements,Permutations in which no element appears in its original position.,!n = n! (1 - 1/1! + 1/2! - ... + (-1)^n / n!)
  Pascal's Rule,Each binomial coefficient is the sum of the two above it in Pascal's triangle.,"C(n, k) = C(n - 1, k - 1) + C(n - 1, k)"
  Catalan Numbers,"Count balanced parentheses, binary trees with n nodes, and monotonic lattice paths that stay on one side of the diagonal.","C_n = C(2n, n) / (n + 1)"
  Stirling Numbers of the Second Kind,Number of ways to partition n labeled items into k non-empty unlabeled subsets.,"S(n, k) = k S(n - 1, k) + S(n - 1, k - 1)"