Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers



Possible Solutions: Supplementary Problems Set E


.

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

1.

s(n)=3s(n-1) - 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(n-1) + 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(n-1) + s(n-2), 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(n-1) +ns(n-2) - 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(n-1) + 2s(n-2) + s(n-3) + 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(n-1) + 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), ...,
b(n)=b(n-1)*(1.05), with b(0)=8000

8.

Each day Freddie buys exactly one item from the following list:

tape
$1
ruler
$1
pens
$2
pencils
$2
paper
$2
loose-leaf binder
$3

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(n-1) + 3*s(n-2) + s(n-3) if n>=4, with s(1)=2, s(2)=7, s(3)=21

9.

Lolita has an unending supply of identical 2-cent stamps, identical 3-cent stamps, and identical 5-cent stamps. Write a recurrence relation with initial conditions for p(n), the number of different ways in which Lolita could attach exactly n-cents worth of stamps to an envelop, assuming that order of placement on the envelop matters.

s(n) = s(n-2) + s(n-3) + s(n-5), 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(n-1), 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(n-1), 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 50-cent drink?

s(1)=1, s(2)=2, s(3)=3, s(4)=5, s(5)=9, s(n) = s(n-1) + s(n-2) + s(n-5), n>=6

For a 50-cent 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 n-by-n checkerboard. How many squares are there for an 8-by-8 board?

s(n) = s(n-1) + n^2, n>=1, s(1)=1. On an 8-by-8 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 2-element subsets possible from a 5-element 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:

# of apples

2
1
1
1
0
0
0

# of oranges

0
1
0
0
1
1
0

# of pears

0
0
1
0
1
0
1

# of bananas

0
0
0
1
0
1
1

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+4-1,4-1)=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:

3 cheese Danish, 2 apricot Danish, and 4 raspberry Danish.

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.

# of cheese Danish

3
3
3
2
2
1

# of apricot Danish

2
1
0
2
1
2

# of raspberry Danish

2
3
4
3
4
4

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):

1 + 3x + 6x^2 + 9x^3 + 11x^4 + 11x^5 + 9x^6 + 6x^7 + 3x^8 + x^9

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:

(1 + x^2 + x^4 + x^6 + ...)(1 + x^3 + x^6 + x^9 + ...).

Can you see how?

Syllabus
Grades & Grading
Session Notes
Assignments and Problem Sets
Tests and Quizzes