ICS 6D Homework 8
1.
(a) Give a generating function denoting the number of ways to select a subset from a set of three identical apples.
(b) Give a generating function denoting the number of ways to select a subset from a set of bananas. There are a total of four bananas, but they are bundled into two groups of two.
(c) Now pool the apples and bananas. Give the generating function for the number of ways to select a subset from the pooled set.
(d) How many ways are there to select three apples or bananas?
(e) Now suppose that you have 2 individual and identical oranges. Give a generating function for selecting from the oranges.
(f) Suppose you add the oranges to the set of apples and bananas. Give the generating function for for the combined set.
(g) How many ways are there to select three pieces of fruit from the set of apples, bananas and oranges?
(h) To verify your answer is correct, list the possibilities for selecting three pieces of fruit.
2. Let {fk} be a sequence corresponding to the number of ways to select a subset of k items from a set S. Give the generating function for {fk} for each description of S:
(a) An infinite supply of identical items.
(b) An infinite supply of items. There are two varieties of items. Items of the same variety are identical.
(c) Six identical items.
(d) Items come bundled in groups of three. There is an infinite supply and all items are the same.
(e) There are 6 groups of items. Each group has 3 items. All items are the same.
(f) There are two of each variety of item. The number of varieties is 20.
(g) There are 20 distinct items. (Think of it like 20 varieties with only one of each variety).
(h) There are six varieties and an infinite supply of each variety.
3. Let {cn} be the sequence denoting the number of ways to make n cents of change using pennies, nickels or dimes. For example c10 = 4 because you could have the following ways to make 10 cents: {D}, {N, N}, {N, P, P, P, P, P}, or {P, P, P, P, P, P, P, P, P, P}. Give a generating function for {cn}. (Hint: Consider making change from pennies, nickels and dimes separately and then pool them together).