III.32 Generating Functions
by Imre Leader, June Barrow-Green, Timothy Gowers
The Princeton Companion to Mathematics
- Cover
- Title
- Copyright
- Contents
- Preface
- Contributors
- Part I Introduction
- Part II The Origins of Modern Mathematics
- Part III Mathematical Concepts
- III.1 The Axiom of Choice
- III.2 The Axiom of Determinacy
- III.3 Bayesian Analysis
- III.4 Braid Groups
- III.5 Buildings
- III.6 Calabi–Yau Manifolds
- III.7 Cardinals
- III.8 Categories
- III.9 Compactness and Compactification
- III.10 Computational Complexity Classes
- III.11 Countable and Uncountable Sets
- III.12 C*-Algebras
- III.13 Curvature
- III.14 Designs
- III.15 Determinants
- III.16 Differential Forms and Integration
- III.17 Dimension
- III.18 Distributions
- III.19 Duality
- III.20 Dynamical Systems and Chaos
- III.21 Elliptic Curves
- III.22 The Euclidean Algorithm and Continued Fractions
- III.23 The Euler and Navier-Stokes Equations
- III.24 Expanders
- III.25 The Exponential and Logarithmic Functions
- III.26 The Fast Fourier Transform
- III.27 The Fourier Transform
- III.28 Fuchsian Groups
- III.29 Function Spaces
- III.30 Galois Groups
- III.31 The Gamma Function
- III.32 Generating Functions
- III.33 Genus
- III.34 Graphs
- III.35 Hamiltonians
- III.36 The Heat Equation
- III.37 Hilbert Spaces
- III.38 Homology and Cohomology
- III.39 Homotopy Groups
- III.40 The Ideal Class Group
- III.41 Irrational and Transcendental Numbers
- III.42 The Ising Model
- III.43 Jordan Normal Form
- III.44 Knot Polynomials
- III.45 K-Theory
- III.46 The Leech Lattice
- III.47 L-Functions
- III.48 Lie Theory
- III.49 Linear and Nonlinear Waves and Solitons
- III.50 Linear Operators and Their Properties
- III.51 Local and Global in Number Theory
- III.52 The Mandelbrot Set
- III.53 Manifolds
- III.54 Matroids
- III.55 Measures
- III.56 Metric Spaces
- III.57 Models of Set Theory
- III.58 Modular Arithmetic
- III.59 Modular Forms
- III.60 Moduli Spaces
- III.61 The Monster Group
- III.62 Normed Spaces and Banach Spaces
- III.63 Number Fields
- III.64 Optimization and Lagrange Multipliers
- III.65 Orbifolds
- III.66 Ordinals
- III.67 The Peano Axioms
- III.68 Permutation Groups
- III.69 Phase Transitions
- III.70 π
- III.71 Probability Distributions
- III.72 Projective Space
- III.73 Quadratic Forms
- III.74 Quantum Computation
- III.75 Quantum Groups
- III.76 Quaternions, Octonions, and Normed Division Algebras
- III.77 Representations
- III.78 Ricci Flow
- III.79 Riemann Surfaces
- III.80 The Riemann Zeta Function
- III.81 Rings, Ideals, and Modules
- III.82 Schemes
- III.83 The Schrödinger Equation
- III.84 The Simplex Algorithm
- III.85 Special Functions
- III.86 The Spectrum
- III.87 Spherical Harmonics
- III.88 Symplectic Manifolds
- III.89 Tensor Products
- III.90 Topological Spaces
- III.91 Transforms
- III.92 Trigonometric Functions
- III.93 Universal Covers
- III.94 Variational Methods
- III.95 Varieties
- III.96 Vector Bundles
- III.97 Von Neumann Algebras
- III.98 Wavelets
- III.99 The Zermelo–Fraenkel Axioms
- Part IV Branches of Mathematics
- IV.1 Algebraic Numbers
- IV.2 Analytic Number Theory
- IV.3 Computational Number Theory
- IV.4 Algebraic Geometry
- IV.5 Arithmetic Geometry
- IV.6 Algebraic Topology
- IV.7 Differential Topology
- IV.8 Moduli Spaces
- IV.9 Representation Theory
- IV.10 Geometric and Combinatorial Group Theory
- IV.11 Harmonic Analysis
- IV.12 Partial Differential Equations
- IV.13 General Relativity and the Einstein Equations
- IV.14 Dynamics
- IV.15 Operator Algebras
- IV.16 Mirror Symmetry
- IV.17 Vertex Operator Algebras
- IV.18 Enumerative and Algebraic Combinatorics
- IV.19 Extremal and Probabilistic Combinatorics
- IV.20 Computational Complexity
- IV.21 Numerical Analysis
- IV.22 Set Theory
- IV.23 Logic and Model Theory
- IV.24 Stochastic Processes
- IV.25 Probabilistic Models of Critical Phenomena
- IV.26 High-Dimensional Geometry and Its Probabilistic Analogues
- Part V Theorems and Problems
- V.1 The ABC Conjecture
- V.2 The Atiyah–Singer Index Theorem
- V.3 The Banach–Tarski Paradox
- V.4 The Birch–Swinnerton-Dyer Conjecture
- V.5 Carleson’s Theorem
- V.6 The Central Limit Theorem
- V.7 The Classification of Finite Simple Groups
- V.8 Dirichiet’s Theorem
- V.9 Ergodic Theorems
- V.10 Fermat’s Last Theorem
- V.11 Fixed Point Theorems
- V.12 The Four-Color Theorem
- V.13 The Fundamental Theorem of Algebra
- V.14 The Fundamental Theorem of Arithmetic
- V.15 Gödel’s Theorem
- V.16 Gromov’s Polynomial-Growth Theorem
- V.17 Hilbert’s Nullstellensatz
- V.18 The Independence of the Continuum Hypothesis
- V.19 Inequalities
- V.20 The Insolubility of the Halting Problem
- V.21 The Insolubility of the Quintic
- V.22 Liouvflle’s Theorem and Roth’s Theorem
- V.23 Mostow’s Strong Rigidity Theorem
- V.24 The P versus NP Problem
- V.25 The Poincaré Conjecture
- V.26 The Prime Number Theorem and the Riemann Hypothesis
- V.27 Problems and Results in Additive Number Theory
- V.28 From Quadratic Reciprocity to Class Field Theory
- V.29 Rational Points on Curves and the Mordell Conjecture
- V.30 The Resolution of Singularities
- V.31 The Riemann–Roch Theorem
- V.32 The Robertson–Seymour Theorem
- V.33 The Three-Body Problem
- V.34 The Uniformization Theorem
- V.35 The Weil Conjectures
- Part VI Mathematicians
- VI.1 Pythagoras (ca. 569 B.C.E.–ca.494 B.C.E.)
- VI.2 Euclid (ca. 325 B.C.E.–ca. 265 B.C.E.)
- VI.3 Archimedes (ca. 287 B.C.E.–212 B.C.E.)
- VI.4 Apollonius (ca. 262 B.C.E.–ca. 190 B.C.E.)
- VI.5 Abu Ja’far Muhammad ibn Mūsā al-Khwārizmī (800–847)
- VI.6 Leonardo of Pisa (known as Fibonacci) (ca. 1170–ca. 1250)
- VI.7 Girolamo Cardano (1501–1576)
- VI.8 Rafael Bombelli (1526-after 1572)
- VI.9 François Viète (1540–1603)
- VI.10 Simon Stevin (1548–1620)
- VI.11 René Descartes (1596–1650)
- VI.12 Pierre Fermat (160?-1665)
- VI.13 Blaise Pascal (1623–1662)
- VI.14 Isaac Newton (1642–1727)
- VI.15 Gottfried Wilhelm Leibniz (1646–1716)
- VI.16 Brook Taylor (1685–1731)
- VI.17 Christian Goldbach (1690–1764)
- VI.18 The Bernoullis (f1.18th century)
- VI.19 Leonhard Euler (1707–1783)
- VI.20 Jean Le Rond d’Alembert (1717–1783)
- VI.21 Edward Waring (ca.1735–1798)
- VI.22 Joseph Louis Lagrange (1736–1813)
- VI.23 Pierre-Simon Laplace (1749–1827)
- VI.24 Adrien-Marie Legendre (1752–1833)
- VI.25 Jean-Baptiste Joseph Fourier (1768–1830)
- VI.26 Carl Friedrich Gauss (1777–1855)
- VI.27 Siméon-Denis Poisson (1781–1840)
- VI.28 Bernard Bolzano (1781–1848)
- VI.29 Augustin-Louis Cauchy (1789–1857)
- VI.30 August Ferdinand Möbius (1790–1868)
- VI.31 Nicolai Ivanovich Lobachevskii (1792–1856)
- VI.32 George Green (1793–1841)
- VI.33 Niels Henrik Abel (1802–1829)
- VI.34 János Bolyai (1802–1860)
- VI.35 Carl Gustav Jacob Jacobi (1804–1851)
- VI.36 Peter Gustav Lejeune Dirichlet (1805–1859)
- VI.37 William Rowan Hamilton (1805–1865)
- VI.38 Augustus De Morgan (1806–1871)
- VI.39 Joseph Liouville (1809–1882)
- VI.40 Ernst Eduard Kummer (1810–1893)
- VI.41 Évariste Galois (1811–1832)
- VI.42 James Joseph Sylvester (1814–1897)
- VI.43 George Boole (1815–1864)
- VI.44 Karl Weierstrass (1815–1897)
- VI.45 Pafnuty Chebyshev (1821–1894)
- VI.46 Arthur Cayley (1821–1895)
- VI.47 Charles Hermite (1822–1901)
- VI.48 Leopold Kronecker (1823–1891)
- VI.49 Georg Friedrich Bernhard Riemann (1826–1866)
- VI.50 Julius Wilhelm Richard Dedekind (1831–1916)
- VI.51 Émile Léonard Mathieu (1835–1890)
- VI.52 Camille Jordan (1838–1922)
- VI.53 Sophus Lie (1842–1899)
- VI.54 Georg Cantor (1845–1918)
- VI.55 William Kingdon Clifford (1845–1879)
- VI.56 Gottlob Frege (1848–1925)
- VI.57 Christian Felix Klein (1849–1925)
- VI.58 Ferdinand Georg Frobenius (1849–1917)
- VI.59 Sofya (Sonya) Kovalevskaya (1850–1891)
- VI.60 William Burnside (1852–1927)
- VI.61 Jules Henri Poincaré (1854–1912)
- VI.62 Giuseppe Peano (1858–1932)
- VI.63 David Hilbert (1862–1943)
- VI.64 Hermann Minkowski (1864–1909)
- VI.65 Jacques Hadamard (1865–1963)
- VI.66 Ivar Fredholm (1866–1927)
- VI.67 Charles-Jean de la Vallée Poussin (1866–1962)
- VI.68 Felix Hausdorff (1868–1942)
- VI.69 Élie Joseph Cartan (1869–1951)
- VI.70 Emile Borel (1871–1956)
- VI.71 Bertrand Arthur William Russell (1872–1970)
- VI.72 Henri Lebesgue (1875–1941)
- VI.73 Godfrey Harold Hardy (1877–1947)
- VI.74 Frigyes (Frédéric) Riesz (1880–1956)
- VI.75 Luitzen Egbertus Jan Brouwer (1881–1966)
- VI.76 Emmy Noether (1882–1935)
- VI.77 Waclaw Sierpiński (1882–1969)
- VI.78 George Birkhoff (1884–1944)
- VI.79 John Edensor Littlewood (1885–1977)
- VI.80 Hermann Weyl (1885–1955)
- VI.81 Thoralf Skolem (1887–1963)
- VI.82 Srinwasa Ramanujan (1887–1920)
- VI.83 Richard Courant (1888–1972)
- VI.84 Stefan Banach (1892–1945)
- VI.85 Norbert Wiener (1894–1964)
- VI.86 Emil Artin (1898–1962)
- VI.87 Alfred Tarski (1901–1983)
- VI.88 Andrei Nikolaevich Kolmogorov (1903–1987)
- VI.89 Alonzo Church (1903–1995)
- VI.90 William Valiance Douglas Hodge (1903–1975)
- VI.91 John von Neumann (1903–1957)
- VI.92 Kurt Gödel (1906–1978)
- VI.93 André Weil (1906–1998)
- VI.94 Alan Turing (1912–1954)
- VI.95 Abraham Robinson (1918–1974)
- VI.96 Nicolas Bourbaki (1935–)
- Part VII The Influence of Mathematics
- VII.1 Mathematics and Chemistry
- VII.2 Mathematical Biology
- VII.3 Wavelets and Applications
- VII.4 The Mathematics of Traffic in Networks
- VII.5 The Mathematics of Algorithm Design
- VII.6 Reliable Transmission of Information
- VII.7 Mathematics and Cryptography
- VII.8 Mathematics and Economic Reasoning
- VII.9 The Mathematics of Money
- VII.10 Mathematical Statistics
- VII.11 Mathematics and Medical Statistics
- VII.12 Analysis, Mathematical and Philosophical
- VII.13 Mathematics and Music
- VII.14 Mathematics and Art
- Part VIII Final Perspectives
- Index
III.32 Generating Functions
Suppose that you have defined a combinatorial structure, and for each nonnegative integer n you wish to understand how many examples of this structure there are of size n. If an denotes this number, then the object that you are trying to analyze is the sequence a0, a1, a2, a3, . . . . If the structure is quite complicated, then this may be a very hard problem, but one can sometimes make it easier by considering a different object, the generating function of the sequence, which contains the same information.
To define this function, one simply regards the sequence an as the sequence of coefficients in a power series. That is, the generating function f of the sequence is given by the formula
f(x) = a0 + a1x + a2x2 + a3x3 + · · ·.
The reason this can be useful is that one can sometimes derive a succinct expression for f and analyze it without reference to the individual numbers an. For example, one important generating function has the formula 
In such cases, one can deduce properties of the sequence a0, a1,a2,. . . from properties of f, rather than the other way round.
For more on generating functions, see ENUMERATIVE AND ALGEBRAIC COMBINATORICS [IV.18] and TRANSFORMS [III.91].
-
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.