Algorithms and Complexity by Herbert S. Wilf

By Herbert S. Wilf

Similar combinatorics books

Approximation Algorithms

This e-book covers the dominant theoretical ways to the approximate answer of not easy combinatorial optimization and enumeration difficulties. It includes stylish combinatorial conception, helpful and engaging algorithms, and deep effects in regards to the intrinsic complexity of combinatorial difficulties. Its readability of exposition and perfect choice of routines will make it available and beautiful to all people with a flavor for arithmetic and algorithms.

Extra info for Algorithms and Complexity

Sample text

M (b) m>1 (2m + 7)/5 19 j (c) j=0 (j/2 ) (d) 1 − x/2! + x2 /4! − x3 /6! 4. Recurrence Relations 27 (e) 1 − 1/32 + 1/34 − 1/36 + · · · ∞ 2 (f) m=2 (m + 3m + 2)/m! 2. Explain why  r≥0 (−1) r π 2r+1 /(2r + 1)! = 0. 3. Find the coeﬃcient of tn in the series expansion of each of the following functions about t = 0. 4 Recurrence Relations A recurrence relation is a formula that permits us to compute the members of a sequence one after another, starting with one or more given values. Here is a small example.

Then 13 would be representable by 3 · 22 + 1 · 20 or by 2 · 22 + 2 · 21 + 1 · 20 , etc. So if we were to allow too many diﬀerent digits, then numbers would be representable in more than one way by a string of digits. If we were to allow too few diﬀerent digits, then we would find that some numbers have no representation at all. For instance, if we were to use the decimal system with only the digits 0, 1, . . , 8, then infinitely many numbers would not be able to be represented, so we had better keep the 9s.

Find, by direct application of Taylor’s theorem, the power series expansion of f (x) = 1/(1 − x)m+1 about the origin. Express the coeﬃcients as certain binomial coeﬃcients. 5. Complete the following twiddles. i J ∼? (a) 2n J in (b) blogn nc ∼ ? 2 i n J (c) bθnc ∼? in2 J (d) n ∼ ? 6. How many ordered pairs of unequal elements of [n] are there? 7. Which one of the numbers {2j inJ n }j=0 is the biggest? 6 Graphs A graph is a collection of vertices, certain unordered pairs of which are called its edges.