💾 Archived View for gem.sdf.org › s.kaplan › cheatsheets › subjects › mathematics-and-physics › comb… captured on 2023-09-28 at 16:46:13.
-=-=-=-=-=-=-
# Combinatorics Cheatsheet ## Basic Concepts - Combinatorics is the study of counting and arranging objects. - Combinatorial problems often involve selecting objects from a set, arranging objects in a sequence, or constructing objects subject to certain conditions. ## Permutations - A permutation is an arrangement of objects in a specific order. - The number of permutations of n objects is n!, i.e., the product of all positive integers up to n. ## Combinations - A combination is a selection of objects from a set without regard to order. - The number of combinations of k objects from a set of n objects is denoted by n choose k, written as nCk or C(n,k), and is given by the formula n! / (k!(n-k)!). ## Pigeonhole Principle - The pigeonhole principle states that if k + 1 or more objects are placed into k boxes, then there must be at least one box containing two or more objects. ## Inclusion-Exclusion Principle - The inclusion-exclusion principle is a counting technique used to calculate the size of a union of sets. - For two sets A and B, the principle states that |A union B| = |A| + |B| - |A intersect B|. - The principle can be extended to more than two sets. ## Generating Functions - A generating function is a formal power series used to encode information about a sequence of numbers. - The coefficients of the generating function can be used to determine the number of ways to count or arrange objects. - Generating functions can be manipulated using algebraic operations such as addition, multiplication, and composition. ## Recurrence Relations - A recurrence relation is an equation that recursively defines a sequence of numbers. - Recurrence relations can be used to model combinatorial problems, such as counting the number of ways to arrange objects subject to certain conditions. - Techniques such as substitution and generating functions can be used to solve recurrence relations. ## Resources - [Combinatorics on Wikipedia](https://en.wikipedia.org/wiki/Combinatorics) - [A Course in Combinatorics by J. H. van Lint and R. M. Wilson](https://www.cambridge.org/core/books/course-in-combinatorics/0B3A3A6C0A3AF1B3D3A2E2E0B1F9B9A6) - [Concrete Mathematics by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik](https://www.pearson.com/us/higher-education/program/Graham-Concrete-Mathematics-2nd-Edition/PGM33527.html)