By Flajolet P., Sedgewick R.
Read Online or Download Analytic combinatorics PDF
Similar combinatorics books
1998 . .. a very good index is integrated that allows you to aid a mathematician operating in a space except his personal to discover adequate info at the subject in query.
- Flag varieties : an interplay of geometry, combinatorics, and representation theory
- Introduction to combinatorial torsions
- Hidden Collective Factors in Speculative Trading: A Study in Analytical Economics
- Notes on Introductory Combinatorics
Extra info for Analytic combinatorics
Note that the expression makes sense within the strict framewok of formal power series; see A PPENDIX A: Formal power series, p. ) The third expression relative to T (z) is equivalent to the explicit form of Tn via Netwon’s expansion of (1 + x)1/2 (p. 33). The OGFs W (z) and T (z) can then also be interpreted as standard analytic objects, upon assigning to the formal variable z values in the complex domain C. In effect, the series W (z) and T (z) converge in a neighbourhood of 0 and represent complex functions that are well defined near the origin, namely when |z| < 12 for W (z) and |z| < 41 for T (z).
20 I. UNLABELLED STRUCTURES AND ORDINARY GENERATING FUNCTIONS N HC CH 3 CH C HC N =⇒ CH HC H 2C C10 H14 N2 z 26 CH 2 CH 2 F IGURE 2. A molecule, methylpyrrolidinyl-pyridine (nicotine), is a complex assembly whose description can be reduced to a single formula corresponding here to a total of 26 atoms. The OGFs corresponding to our three examples W, P, T are then ∞ 1 2n z n = W (z) = 1 − 2z n=0 ∞ P (z) = n! z n (7) n=0 √ ∞ 1 1 − 1 − 4z 2n n T (z) = z = . n+1 n 2z n=0 The first expression relative to W (z) is immediate as it is the sum of a geometric progression; The second generating function P (z) is not related to simple functions of analysis.
47622n ; see Chapter IV. E XAMPLE 5. Partitions with restricted summands (denumerants). Whenever summands are restricted to a finite set, the special partitions that result are called denumerants. A popular denumerant problem consists in finding the number of ways of giving change of 99 cents using coins that are pennies (1 ¢), nickels (5 ¢), dimes (10 ¢) and quarters (25 ¢). 1 that P T (z) is always a rational function with poles that are at roots of unity; also the PnT satisfy a linear recurrence related to the structure of T .