Wilf. Generatingfunctionology (главным образом комбинаторика), Wilf. Generatingfunctionology (mostly combinatorics)(231s).pdf:

Home / lib / M_Mathematics / MA_Algebra / MAc_Combinatorics /

Wilf. Generatingfunctionology (главным образом комбинаторика)

Wilf. Generatingfunctionology (mostly combinatorics)(231s).pdf

Size 1.6Mb
Date Apr 6, 2002

Cites:

in which the unknown numbers z1 , zn−1 are determined by the requirement that the right side of (1.4.10) be a polynomial, or equivalently by the two equations (1.4.4), which become √ √ z1 + ( 3 − 2)n zn−1 = −D ( 3 − 2) √ √ z1 + (− 3 − 2)n zn−1 = −D (− 3 − 2). (1.4.11)...

To ﬁnd formulas for these numbers we use (what else?) generating functions. For each n = 0, 1, 2, . . . deﬁne the generating function Bn (x) = k
≥0...

Before we plunge into the calculations, let’s pause for a moment to develop some intuition about which of these choices is likely to succeed. To ﬁnd An (y ) will involve multiplying (1.6.3) by y k and summing over k. Do you see any problems with that? Well, there are some, and they arise from the factor of k in the second term on the right. Indeed, after multik lyingy y p nb k y and summing over k we will have to deal with something like k k k. This is certainly possible to think about, since it is related to the derivative of An (y ), but we do have a complication here. If instead we cho ose to ﬁnd Bk (x), we multiply (1.6.3) by xn and sum on n. Then the factor of k that seemed to be troublesome is not involved in the sum, and we can take that k outside of the sum as a multiplicative factor. Comparing these, let’s vote for the latter approach, and try to ﬁnd the functions Bk (x) (k ≥ 0). Hence, multiply (1.6.3) by xn and sum over n, to get Bk (x) = xBk−1 (x) + kxBk (x) (k ≥ 1; B0 (x) = 1)....

The novel feature is the app earance of the diﬀerentiation operator d/dy that was necessitated by the factor k in the recurrence relation. Hence each function An is obtained from its predecessor by applying the operator y (1 + Dy ). Beginning with A0 = 1, we obtain successively y, y + y 2 , y + 3y 2 + y 3 , . . ., but as far as an explicit formula is concerned, we ﬁnd only that An (y) = {y + yDy }n 1 (n ≥ 0) (1.6.9) by this approach. There are, however, one or two things that can be seen more clearly from these generating functions than from the Bn (x)’s. One of these will nf be discussed in section 4.5, and concerns the shape of the sequence k or ﬁxed n, as k runs from 1 to n. It turns out that the sequence increases for a while and then it decreases. That is, it has just one maximum. Many combinatorial sequences are unimodal, like this one, but in some cases it can be very hard to prove such things. In this case, thanks to the formula (1.6.9), we will see that it’s not hard at all. ni For an application of (1.6.7), recall that the Stirling number k s the number of ways of partitioning a set of n elements into k classes. Supp ose we don’t particularly care how many classes there are, but we want to know the number of ways to partition a set of n elements. Let these numbers be {b(n)}∞ . They are called the Bell numbers. It is conventional to take 0 b(0) = 1. The sequence of Bell numb ers begins 1, 1, 2, 5, 15, 52, . . . Can we ﬁnd an explicit formula for the . ell numbers? Nothing to it. nB In (1.6.7) we have an explicit formula for k If we sum that formula from k = 1 to n we will have an explicit formula for b(n). However, there’s one...

We have now seen several examples of how generating functions can be used to ﬁnd recurrence relations. It often happ ens that the method of generating functions ﬁnds a recurrence, and only later are we able to give a direct, combinatorial interpretation of the recurrence. In some cases, recurrences are known that look like they ought to have simple combinatorial explanations, but none have yet been found....

ﬁrst by the method of partial fractions, and second, give a much simpler derivation by being sneaky. 17. An inversion of a permutation σ of [n] is a pair of letters i, j such that i < j and σ (i) > σ(j ). In the 2-line form of writing the permutation, an inversion shows up as a pair that is ‘in the wrong order’ in the second line. The permutation o 1 23456789 σ= 492581673 f [9] has 19 inversions, namely the pairs (4,2), (4,1), ..., (7,3). Let b(n, k) be the number of permutations of n letters that have exactly k kinversions. Find a ‘simple’ formula for the generating function Bn (x) = b(n, k)xk . Make a table of values of b(n, k) for n ≤ 5. 18. (a) Given n, k. For how many of the permutations of n letters is it true that their ﬁrst k values decrease? (b) What is the average length of the decreasing sequence with which the values of a random n-permutation b egin? (c) If f (n, k) is the number of permutations that have exactly k ascending runs, ﬁnd the Pascal-triangle-type recurrence satisﬁed by f (n, k). They are called the Euler numbers. As an example, the permutation h 1 23456789 416925837 as 4 such runs, namely 4, 1 6 9, 2 5 8, and 3 7. 19. Consider the 256 possible sums of the form 1 + 2 + 2 3 + 5 4 + 10 5 + 10 6 + 20 7 + 50 8 where each is 0 or 1. (1)...

(c) Find an explicit formula for f (n, m, k) from the generating function (this should involve only a single summation, of an expression that involves a few factorials). 21. (a) We want to ﬁnd a formula for the nth derivative of the function x ee . Diﬀerentiate it a few times, study the pattern, and conjecture the form of the answer for general n, including some constants to be determined. Then ﬁnd a recurrence formula for the constants in question, and identify them as some ‘famous’ numbers that we have studied....

and notice that if we apply (xD)2 to both sides of this relation and then set x = 1, the left side will be the sum of squares that we seek, and the right side will be the answer! Hence nN
=1...

Here we have a new wrinkle. We are accustomed to going from recurrence relations on a sequence to functional equations that have to be solved for generating functions. In previous examples, those functional equations have either been simple linear equations or diﬀerential equations. In (2.3.8) we have a generating function that satisﬁes a quadratic equation. When we solve it, we get √ 1 ± 1 − 4x . F (x) = 2x Which sign do we want? If we choose the ‘+’ then the numerator will approach 2 as x → 0, so the ratio will become inﬁnite at 0. But our generating function takes the value 1 at 0, so that can’t be right. If we choose the ‘−’ sign, then a dose of L’Hospital’s rule shows that we will indeed have F (0) = 1. Hence our generating function is √ 1 − 1 − 4x F (x) = . (2.3.9) 2x This is surely one of the most celebrated generating functions in combinatorics. The numbers f (n) are the Catalan numbers, and in (2.5.10) there is an explicit formula for them. For the moment, we declare that this exercise, which was intended to show how the form of a recurrence can guide the choice of generating function, is over....