Enumerative combinatorics

इस पर आधारित

32 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)

आप सीखेंगे

• Use exponential generating functions to count labelled structures such as set partitions and derangements.
• Prove Euler's theorem that partitions into odd parts are equinumerous with partitions into distinct parts.
• Count colourings up to symmetry with Burnside's lemma and Pólya's theorem.

परिभाषा

• A partition of n is a way of writing n as an unordered sum of positive integers.
• The exponential generating function of (aₙ) is Σ aₙxⁿ/n!.
• Burnside's lemma: a finite group G acting on a finite set X has (1/|G|) Σ_{g∈G} |Fix(g)| orbits.

प्रमेय

• The number of partitions of n into odd parts equals the number of partitions of n into distinct parts.
• The number of derangements of n objects is n! Σ_{k=0}^{n} (−1)ᵏ/k!.
• Burnside's lemma (also called the Cauchy–Frobenius lemma).

आम भ्रांतियाँ

• Counting colourings up to symmetry by dividing by the size of the group; this fails when some colourings are themselves symmetric.

वैकल्पिक खोजें

• Representation theory of finite groups Partitions of n index the irreducible complex representations of the symmetric group Sₙ.
• ← Combinatorics

आगे पढ़ने के लिए

• Richard P. Stanley, Enumerative Combinatorics, Volume 1
• Herbert S. Wilf, generatingfunctionology (1990)