| Home / lib / M_Mathematics / MA_Algebra / MAc_Combinatorics / | ||
Wilf. Generatingfunctionology (mostly combinatorics)(231s).pdf |
|
Size 1.6Mb Date Apr 6, 2002 |
The novel feature is the app earance of the differentiation 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 find 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 fixed 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 find 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 find recurrence relations. It often happ ens that the method of generating functions finds 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....
7. Give a direct combinatorial pro of of the recurrence (1.6.13), as follows: given n; consider the collection of all partitions of the set [n]. There are b(n) of them. Sort out this collection into piles numb ered k = 0, 1, . . . , n − 1, where the kth pile consists of all partitions of [n] in which the class that contains the letter ‘n’ contains exactly k other letters. Count the partitions in the kth pile, and you’ll be all finished. 8. In each part of problem 6, find the exponential generating function of the sequence (you may have to solve a differential equation to do so!). 9. A function f is defined for all n ≥ 1 by the relations (a) f (1) = 1 and (b) f (2n) = f (n) and (c) f (2n + 1) = f (n) + f (n + 1). Let F (x) = n
≥1...
for instance, has a p erfectly fine existence as a formal power series, despite the fact that it converges for no value of x other than x = 0, and therefore offers no possibilities for investigation by analytic metho ds. Not only that, but this series plays an important role in some natural counting problems. A formal power series is an expression of the form a0 + a1 x + a2 x2 + · · · where the sequence {an }∞ is called the sequence of coefficients. To say that 0 two series are equal is to say that their coefficient sequences are the same....
{an }∞ , and let k be a p ositive integer. Then 0 n ∞ an1 an2 · · · ank
1 +n2 +···+nk =n...
k an n−s an1 · · · ank (n1 n2 · · · nk )−s n an1 · · · ank
1 ···nk =n...
it follows that a multiplicative number-theoretic function is completely determined by its values on al l powers of primes. Indeed, f (n) = f (pa1 )f (pa2 ) · · · f (par ). r 1 2 (2.6.5)...
This is the celebrated M¨bius Inversion Formula. The reciprocal relationo ships (2.6.11) and (2.6.12) of the sequences mirror the reciprocal relationships of their Dsgf ’s ζ (s) and 1/ζ (s). Example 1. Primitive bit strings. How many strings of n 0’s and 1’s are primitive, in the sense that such a string is not expressible as a concatenation of several identical smaller strings? For instance, 100100100 is not primitive, but 1101 is. There are a total of 2n strings of length n. Suppose f (n) of these are primitive. Every string of length n is uniquely expressible as a concatenation of some number, n/d, of identical primitive strings of length d, where d is a divisor of n. Thus we have d 2n = f (d) (n = 1, 2, . . .)
\n...
(d) x + x3 (e) log (1 − x) 3. Let f be a formal power series such that f proof that f = A sin x + B cos x. (a) {n + 7}∞ 0 (b) {1}∞ 4 (c) {1, 0, 1, 0, 1, 0, 1, 0, . . .} (d) {1/(n + 1)}∞ 2 (e) {1/(n + 5)!}∞ 0 (f ) F1 , 2F2 , 3F3 , 4F4 , . . . (the F ’s are the Fibonacci numbers) (g) {(n2 + n + 1)/n!}∞ 1 5. Use generating functions to prove that kn=
k +...
Let F and F b e two exponential families whose picture sets P , P re disjoint. We form a third family F , and write F = F ⊕ F , as follows:...
By summing (3.4.5) over just those k that lie in a given set T , we obtain Corollary 3.4.2 (The exp onential formula with numb ers of cards n n restricted). Let T b e a set of positive integers, let eT (x) = ∈T x /n!, and let hn (T ) be the number of hands whose weight is n and whose number of cards b elongs to the allowable set T . Then {hn (T )}∞ 0
eg f ← →...
Now by the exponential formula the enumerator of hands is H(x, y ) = ey(e and in particular n k = xn n! (
x...
The number of permutations that meet the conditions of the problem is the coefficient of xn /n! here, namely nn ! . n n 22 That’s one way to answer the question, but the answer can be restated in quite a striking form, like thisTheorem 3.7.1. Let a positive integer n be fixed. The probabilities of the following two events are equal: (a) a permutation is chosen at random from among those of n letters, and it has an even number of cycles, all of whose lengths are odd (b) a coin is tossed n times and exactly n/2 heads o ccur. 3.8 Involutions, etc. Fix positive integers m, n. How many permutations σ , of n letters, satisfy σ m = 1, where ‘1’ is the identity permutation? To do this problem, we need the following:...
and this series does not converge for any x = 0. So this is a formal power series generating function only, and we should not expect analytic functions at the end of the road. Having said all of that, the machinery still works very nicely. We will now find a recurrence formula for the number of connected graphs by the ‘xD log ’ method of section 1.6. It isn’t any harder to find a general recurrence relation than for this special case, however, so let’s do it in general....
| © 2007 eKnigu | ||
| Отзывы на форуме шкаф купе заказ. Шкафы-купе и мебель на заказ для прихожей. . гостиницы ростова . воздухонагреватели gp |