Loading...
Please wait, while we are loading the content...
Similar Documents
Generating Functions and Recurrence Relations
| Content Provider | Scilit |
|---|---|
| Author | Wallis, Walter D. George, John C. |
| Copyright Year | 2010 |
| Description | Some kinds of combinatorial calculations are modeled by the behavior of infinite power series or even finite power series (i.e., polynomials). For instance, we considered in Chapter 2 how to determine the number of ways of selecting k items from a set of n; for simplicity, we will consider n− 4, k = 2. Suppose we wish to multiply (1 + x1)(1 + x2)(1 + x3)(1 + x4). In the product, we ask how many terms of the form xixj there will be; clearly, ) = 6 of them, since that is how many ways we can choose two of the factors to contribute an xi. Now, if we set x1 = x2 = x3 = x4 = x, the product is the polynomial (1 + x)4. The coefficient of x2 in this product is ) = 6. (The reader will recall that this subscripting technique is how we proved Theorem 2.3, the Binomial Theorem.) In the same way, some numbers of combinatorial interest (such as a sequence of integers) have properties that become clear or easier to prove when they are used as coefficients of a polynomial or an infinite series. These considerations motivate us to define the generating function of a sequence a0, a1, . . . to be the formal power series ∑ i≥0 aix i. The expression “formal power series” is understood to mean that we do not evaluate the power series at any point, or concern ourselves with the question of convergence necessarily. Indeed, some uses of generating functions do not require infinite series at all; in this case we shall assume that an = 0 for all n greater than some specific integer N . Book Name: Introduction to Combinatorics |
| Related Links | https://content.taylorfrancis.com/books/download?dac=C2009-0-02669-3&isbn=9780429113109&doi=10.1201/b12336-9&format=pdf |
| Ending Page | 118 |
| Page Count | 18 |
| Starting Page | 101 |
| DOI | 10.1201/b12336-9 |
| Language | English |
| Publisher | Informa UK Limited |
| Publisher Date | 2010-09-07 |
| Access Restriction | Open |
| Subject Keyword | Book Name: Introduction To Combinatorics Behavior Functions Polynomial Power Series Infinite Theorem |
| Content Type | Text |
| Resource Type | Chapter |
