Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers



Finding Fibonacci's Sequence in Pascal's Triangle


As some of us have explored and many of us may have recognized, the Fibonacci Sequence is one of many special sequences detectable in Pascal's Triangle. Our goal in this discussion is to try and represent the Fibonacci Sequence in terms of the combinatorial relationships revealed within Pascal's Triangle. This may be an approach to the representation of the Fibonacci Sequence that is different from others you have seen, such as simply defining an element of the sequence as the sum of the previous two elements where the first two elements are 1 and 1.

Here is a problem situation to get us started:

Suppose we have a collection of mathematics and science books, distiguishable only by subject, that are to be shelved under the strict requirement that no two science books may be adjacent to each other. How many such arrangements are possible?

Let's explore the examples below, looking for viable patterns, raising conjectures, and trying to justify the relationships we identify.

Example 1: Suppose we have 5 mathematics (M) books and 3 science (S) books. We begin by first fixing the positions of the M books so there is adequate room to put a S book inbetween two M books. There is just 1 way to arrange the M books this way. (Recall that we can distinguish only between the subjects, therefore the M books are indistinguishable from one another.)

_ M _ M _ M _ M _ M _

The picture above shows that there are 6 places for the three S books. Because the S books are indistuishable from one another, we have C(6,3)=20 ways to place the S books among the M books so that no two S books are adjacent.

Example 2: Suppose we have 4 mathematics (M) books and 8 science (S) books. Here's a picture of the M books fixed in position:

_ M _ M _ M _ M _

It seems that there are places for only as many as 5 S books. For the group of 4 M books and 8 S books, there are no ways to solve the problem under the restrictions posed.

Example 3: One more specific case: Suppose we have 9 mathematics (M) books and 6 science (S) books. Here's a picture of the 9 M books fixed in position:

_ M _ M _ M _ M _ M _ M _ M _ M _ M _

This picture shows that there are 10 places for the six S books. The S books can be placed in C(10,6)=C(9+1,6) ways if we must place the S books among the M books so that no two S books are adjacent.

Example 4: Suppose we have r mathematics (M) books and k science (S) books.

Example 5: Finally, suppose we have 8 books in all, some mathematics (M) books and some science (S) books. Given the restrictions on shelving that we've imposed here:

  1. What are the various numbers of M and S books, 8 in all, that could be shelved?
  2. How many different arrangements are there for each possibility you found in the previous question?

Example 6: Suppose we have 4 books in all, some Science and some Mathematics, with the restrictions on shelving that we've imposed here.

Step 1: Determine the number of M/S books possible.

We could have 4M/0S, 3M/1S, and 2M/2S. We cannot have any more S books (or any less M books) and still maintain the non-adjacency requirement for the S books.

Step 2: Determine the number of arrangements for each of the cases determined in Step 1.

4M/0S: First shelve the M books. There are 5 spaces among the 4 M books. Choose 0 of those spaces for the 0 S books. Total: C(5,0)=1 way to arrange the 4M/0S books.

3M/1S: First shelve the M books. There are 4 spaces among the 3 M books. Choose 1 of those spaces for the 1 S book. Total: C(4,1)=4 ways to arrange the 3M/1S books.

2M/2S: First shelve the M books. There are 3 spaces among the 2 M books. Choose 2 of those spaces for the 2 S books. Total: C(3,2)=3 ways to arrange the 2M/2S books.

Step 3: Sum the arrangements determined in Step 2.

C(5,0) + C(4,1) + C(3,2) = 8 ways in all to shelve 4 books. Because these books are in FRED'S office, let's say that FRED'S (4 books) = 8 arrangements, or, more succinctly, F(4)=8.

Example 7: Suppose we have 7 books in all, some Science and some Mathematics. Determine F(7).

Step 1: Determine the number of M/S books possible.

We could have 7M/0S, 6M/1S, 5M/2S, 4M/3S, and 3M/4S. We cannot have any more S books (or any less M books) and still maintain the non-adjacency requirement for the S books.

Step 2: Determine the number of arrangements for each of the cases determined in Step 1.

7M/0S: First shelve the M books. There are 8 spaces among the 7 M books. Choose 0 of those spaces for the 0 S books. Total: C(8,0)=1 way to arrange the 7M/0S books.

6M/1S: First shelve the M books. There are 7 spaces among the 6 M books. Choose 1 of those spaces for the 1 S book. Total: C(7,1)=7 ways to arrange the 6M/1S books.

Continue in this manner through all possible cases determined in Step 1.

Step 3: Sum the arrangements determined in Step 2.

C(8,0) + C(7,1) + C(6,2) + C(5,3) + C(4,4) = 34 ways in all to shelve 7 books. We have F(7)=34.

Now, you determine the remaining values of F(n) for n=1,2,...,14 and then check your solutions. We know F(4) and F(7).

We see that these values satisfy the relationship F(n)=F(n-1)+F(n-2). This is an example of a recursion relation, for it describes a new element of the relationship in terms of previous elements.

We can justify this recursive formula by examining the book-shelving task when there are n books to be shelved. There are exactly two cases to consider in terms of the first book on the shelf: it is either a M book or a S book.

If the first book is M, then the next book could either be M or S and there are F(n-1) ways to shelve these n-1 books. If the first book is an S book, however, we know the next book has to be a M book. This leaves n-2 books to be shelved. There are F(n-2) ways to shelve them.

The two cases, M book first or S book first, are disjoint, so we add the results for each case. This shows that F(n)=F(n-1)+F(n-2).


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