Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8
Teachers 
Possible Solutions: Supplementary Problems Set E 


For questions (1) through (5), determine s(5). 

1. 
s(n)=3s(n1)  9, n>=1, s(0)=5 s(0)=5, s(1)=6, s(2)=9, s(3)=18, s(4)=45, s(5)=126 

2. 
s(n)=2s(n1) + 3n, n>=1, s(0)=5 s(0)=5, s(1)=13, s(2)=32, s(3)=73, s(4)=158, s(5)=331 

3. 
s(n)=2s(n1) + s(n2), n>=2, s(0)=2, s(1)=3 s(0)=2, s(1)=3, s(2)=4, s(3)=11, s(4)=26, s(5)=63 

4. 
s(n)=s(n1) +ns(n2)  1, n>=2, s(0)=3, s(1)=4 s(0)=3, s(1)=4, s(2)=9, s(3)=20, s(4)=53, s(5)=152 

5. 
s(n)=s(n1) + 2s(n2) + s(n3) + n, n>=3, s(0)=1, s(1)=2, s(2)=5 s(0)=1, s(1)=2, s(2)=5, s(3)=13, s(4)=29, s(5)=65 

6. 
Membership dues at Pine Valley Tennis Club were $50 in 1970 and have increased $5 per year since then. Write a recurrence relation with initial conditions for m(n), the membership fee n years after 1970. m(n)=m(n1) + 5, with m(0)=50 

7. 
A passbook savings account earns 5% interest compounded annually. An initial deposit of $8000 is made. If no additions or withdrawals are made to the account, write a recurrence relation with initial conditions for b(n), the balance in the account after n years. b(0)=8000,
b(1)=8000+0.05(8000)=8000(1.05)=b(0)*(1.05), ..., 

8. 
Each day Freddie buys exactly one item from the following list:
Write a recurrence relation with initial conditions for s(n), the number of different sequences by which Freddie could spend exactly n dollars. s(n) = 2*s(n1) + 3*s(n2) + s(n3) if n>=4, with s(1)=2, s(2)=7, s(3)=21 

9. 
Lolita has an unending supply of identical 2cent stamps, identical 3cent stamps, and identical 5cent stamps. Write a recurrence relation with initial conditions for p(n), the number of different ways in which Lolita could attach exactly ncents worth of stamps to an envelop, assuming that order of placement on the envelop matters. s(n) = s(n2) + s(n3) + s(n5), n>5, s(1)=0, s(2)=1, s(3)=1, s(4)=1, s(5)=3 

10. 
Let a(n) represent the number of arrangements of the integers 1,2,...,n, with n>=1. State a recurrence relation with initial conditions for a(n). a(1) = 1, a(n) = n*a(n1), n>=1 

11. 
Let s(n) represent the number of subsets for a set with n elements, with n>=1. State a recurrence relation with initial conditions for s(n). s(1) = 2, s(n) = 2*s(n1), n>=1 

12. 
Write a recurrence relation with initial conditions for c(n), the number of sequences of nickels, dimes, and quarters inserted into a vending machine to purchase a soft drink costing 5n cents. How many sequences are there for a 50cent drink? s(1)=1, s(2)=2, s(3)=3, s(4)=5, s(5)=9, s(n) = s(n1) + s(n2) + s(n5), n>=6 For a 50cent drink, there are 128 sequences, that is, s(10) = 128. 

13. 
Write a recurrence relation with initial conditions for s(n), the number of squares of any size that can be found on an nbyn checkerboard. How many squares are there for an 8by8 board? s(n) = s(n1) + n^2, n>=1, s(1)=1. On an 8by8 board there are 204 squares. 

101. 
A child is allowed to take two items from a basket that contains an apple, an orange, a pear, a banana, and a plum. How many different fruit pairs can the child select? This problem reduces to determining the number of 2element subsets possible from a 5element set, or, equivalently, the combinations of 5 choose 2. There are 10 such selections possible. Note that this is the coefficient of the x^2 term in the expansion of (1 + x)^5. Hmmm . . . 

102. 
A senior citizen is asked to take two items from a basket that contains two apples, one orange, one pear, and one banana. How many different fruit pairs can the senior select? There are 7 ways this can occur. You can create an organized list to show this, such as the following:
You can use the inclusion/exclusion property combined with methods for finding the number of nonnegative solutions to the equation A +R + P + B = 2. With unlimited nonnegative integers, there are C(2+41,41)=C(5,3)=10 different ways. We must exclude, however, any solution with R=2, P=2, or B=2. Three such solutions are of that form. This leaves 7 possible selections that the senior citizen can make. Note also that 7 is the coefficient of the x^2 term in the expansion of (1 + x + x^2)(1 + x)(1 + x)(1 + x). Hmmm . . . 

103. 
Each of r people wants a fruit Danish from the bakery. The bakery has only the following Danish available: Determine d(r), the number of fillable orders for r pastries. What is d(7)? Here are the 6 fillable orders when 7 pastries are ordered.
We could create a table like this to determine d(r) for remaining r, r=1,2,...,9. We know d(r)=0 when r>9. Note the coefficients in the expansion of (1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4): Hmmm . . . 

104. 
A mountain ski chalet sells a grilled cheese sandwich for $2 and a bowl of noodle soup for $3. Determine m(r), the number of ways to order $r of soup and sandwiches. Here is a function that generates a solution to this problem: Can you see how? 




