91Ó°ÊÓ

What is the generating function for the sequence \(\left\\{c_{k}\right\\}\) where \(c_{k}\) represents the number of ways to make change for \(k\) pesos using bills worth 10 pesos, 20 pesos, 50 pesos, and 100 pesos?

Write out the explicit formula given by the principle of inclusion-exclusion for the number of elements in the union of five sets.

a) Find the recurrence relation satisfied by \(R_{n},\) where \(R_{n}\) is the number of regions that a plane is divided into by \(n\) lines, if no two of the lines are parallel and no three of the lines go through the same point. b) Find \(R_{n}\) using iteration.

a) Find the recurrence relation satisfied by \(R_{n},\) where \(R_{n}\) is the number of regions into which the surface of a sphere is divided by \(n\) great circles (which are the intersections of the sphere and planes passing through the center of the sphere), if no three of the great circles go through the same point. b) Find \(R_{n}\) using iteration.

How many elements are in the union of five sets if the sets contain \(10,000\) elements each, each pair of sets has 1000 common elements, each triple of sets has $100 common elements, every four of the sets have 10 common elements, and there is 1 element in all five sets?

What is the general form of the solutions of a linear homogeneous recurrence relation if its characteristic equation has the roots \(-1,-1,-1,2,2,5,5,7 ?\)

a) Find the recurrence relation satisfied by \(S_{n},\) where \(S_{n}\) is the number of regions into which three-dimensional space is divided by \(n\) planes if every three of the planes meet in one point, but no four of the planes go through the same point, b) Find \(S_{n}\) using iteration.

Explain how generating functions can be used to find the number of ways in which postage of \(r\) cents can be pasted on an envelope using 2 -cent, 7 -cent, 13 -cent, and 32 -cent stamps. a) Assume that the order the stamps are pasted on does not matter. b) Assume that the order the stamps are pasted on matters. c) Use your answer to part (a) to determine the number of ways 49 cents of postage can be pasted on an envelope using 2 -cent, 7 -cent, 13 -cent, and 32 -cent stamps when the order the stamps are pasted on does not matter. (Use of a computer algebra program is advised.) d) Use your answer to part (b) to determine the number of ways 49 cents of postage can be pasted on an envelope using 2 -cent, 7 -cent, 13 -cent, and 32 -cent stamps when the order in which the stamps are pasted on matters. (Use of a computer algebra program is advised.)

a) Find a recurrence relation for the number of ways to completely cover a \(2 \times n\) checkerboard with \(1 \times 2\) dominoes. [Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.] b) What are the initial conditions for the recurrence relation in part (a)? c) How many ways are there to completely cover a \(2 \times\) 17 checkerboard with \(1 \times 2\) dominoes?

Find the probability that when four numbers from 1 to 100 , inclusive, are picked at random with no repetitions allowed, either all are odd, all are divisible by \(3,\) or all are divisible by \(5 .\)