Review:  Binomial & Multinomial Expansions

Here are several problems to help review previous week's discussion of the binomial and multinomial expansions. Click on the highlighted word to take you to a possible solution to that problem.

 다음에서  x^3과 같은 표현은  x³ 을 나타내기로 약속한다  (실제로 이러한 표현은 수학 기호를 사용하는 많은 software에서 공동으로 사용하는 문법이다).

1.    Expand   (r + s)^3.

2.    Write the first three terms, beginning with the term containing the factor m^7, in the expansion of (4m - 3t)^7.

3.    After expanding and collecting all like terms, how many terms will there be in the expansion of (w + v)^18 ?

4.    Is r^4st^2v^3 a possible term in the expansion of                   (r + s + t +v)^12 ? Explain.

5.    Determine the coefficient for the collected term containing the factor a^2b^4cd in the expansion of (a + b + c + d)^8.

6.     Create a counting problem for which 9!/(2!4!3!) is the numerical solution.

  Fibinacci Sequence의 일반식을 구하기 위하여  다섯 가지

관련된 예와 문제를 탐구적 방법으로 알아보도록 한다.

 제 6주 강의록은 영문으로 작성되었습니다.  국문강의록 보다 읽기가 조금 어렵기 때문에 여러분들은 천천히 읽고 학습하기 바랍니다.

        Fibonacci 수열과 점화식 I

이제  Pascal의 삼각형을 이용하여 Fibonacci 수열의

일반항과 여러 성질에 관하여 학습하도록 합시다. 먼저

  Fibinacci Sequence의 일반식을 구하기 위하여  5 가지

관련된 예와 문제를 탐구적 방법으로 알아보도록

합시다.

  Finding Fibonacci's Sequence in Pascal's Triangle:

   As some of you have explored and many of us have recognized, the Fibonacci Sequence is one of many special sequences detectable in Pascal's Triangle. Our goal in this and continued discussions 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.

Throughout this lecture,  we denote  C(n,r)  by the combination  

                             .

    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, look for viable patterns, raise conjectures, and try to justify the relationships we identify.

 

Ex. 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.

 

Ex. 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.

 

Ex. 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.

 

Problem 1: Suppose we have r mathematics (M) books and k science (S) books. How many ways are there to place the S books and still meet our restrictions? Use combinatorial notation. What limitations are there in the relationship between r and k? Use an inequality relationship.

 

Problem 2: 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: What are the various numbers of M and S books, 8 in all, that could be shelved? How many different arrangements are there for each possibility you found in the previous question?

     From discussion of the patterns revealed in exploring these five examples, our next step is to propose one or more conjectures about how we can use combinatorial notation to represent the Fibonacci sequence in Pascal's Triangle. Stay tuned!

Possible Solutions to Review Problems

1. r^3+3r^2s+3rs^2+s^3
2. 4^7m^7-3(4^6)m^6t+9(4^5)m^5t^2
3. 19
4. No. Its exponents do not sum to 12.
5. [8!/(2!4!1!1!)](a^2b^4cd)
6. Example: How many different arrangements are there for the letters in the nonsense word aabbbbccc?

---

 

Fibinacci Sequence의 일반식을 구하기 위하여  5 가지 관련된 예와 문제를 탐구적 방법으로 학습하였다.

 How many way can a convex polygon of n sides be devided into triangles by drawing diagonals that do not intersect ?  Find an explicit formula for the number D_n of different triangulations.

   Fibinacci Sequence와  이와 관련된 문제를 통하여

탐구적 방법으로 점화식에 대하여 학습한다.

       Fibonacci 수열과 점화식 II

이제  Pascal의 삼각형을 이용하여 Fibonacci 수열의

일반항과 여러 성질에 관하여 학습하도록 합시다.

  Fibonacci sequence와  이와 관련된 문제를 통하여 탐구적

방법으로 점화식에 대하여 알아보도록 합시다.

 제 6주 강의록은 영문으로 작성되었습니다.  국문강의록 보다 읽기가 조금 어렵기 때문에 여러분들은 천천히 읽고 학습하기 바랍니다.

Generalization :

If n  represents the total number of M and S books to be shelved under these conditions, then the total number of possible arrangements for n books, n>1, is

F(n)=F(n-1)+F(n-2),    where F(0)=1 and F(1)=2.

Justification :

To justify that this relationship holds in general, consider the shelving possibilities when there are n M and S books.That is, we are looking for F(n). There are two distinct cases to consider:

Case I: The first (leftmost) book is a M book.
If the first book is a M book, there are F(n-1) ways to arrange the remaining n-1 books, for the next book on the shelf can be either M or S.

Case II: The first (leftmost) book is a S book.
If the first book is a S book, there are F(n-2) ways to arrange the remaining n-1 books. This is true because the next book on the shelf, under the problem conditions, has to be a M book. Thus, with a S book first, we are sure of the first two books shelved. Now there remain F(n-2) ways to arrange the remaining n-2 books.

Because the two cases are distinct, we have F(n)=F(n-1)+F(n-2).         

?

Recursion (점화식) :

The relationship described by F(n)=F(n-1)+F(n-2) is called a

recursion relationship(점화관계), a relationship in which a

new element is described by referring to one or more known

elements. We have seen many recursion relationships in our

study of mathematics, although that fact may not have been

directly stated at the time. Here are some examples of

recursion relationships. With each, some specific elements in

the relationship are shown as well as a corresponding explicit

way to describe each relationship.

다음의 표는 몇 가지 점화식과 그 일반항을 나타낸다.

Throughout this lecture,  

we denote   Sigma(i,1,n;a(i))  by

                   .

The Number of Solutions to Sigma(i,1,n;a(i))=K Over (a) Positive Integers, (b) Nonnegative Integers, (c) Restricted Subsets of the Positive Integers

The handout from last time asked you to explore some examples of determining the number of ways to complete specific tasks given certain restrictions. For two of the three situations we have already developed machinery to solve the problem. The third situation, involving Sandy Softknuckle's arrangements of napkins, extends our work. We will use Sandy Softknuckle's setting to illustrate the three situations.

Sandy Softknuckle  suffers from a mild case of obsessive-compulsive disorder. Sandy is particularly fascinated with ways to arrange dinner napkins for formal parties. Assuming Sandy has an unlimited supply of green, white, and red napkins, how many ways can Sandy create a set of 20 napkins if:

a) it is okay to have no napkins of a particular color?
b) there must be at least one napkin of each color?
c) there must be more than 3 of each color napkin?

The two situations previously encountered:

(a) The number of solutions to the equation Sigma(i,1,n;a(i))=K solved over the nonnegative integers is C(K+n-1,n-1). Here, we have C(20+3-1,3-1)=C(22,2).

(b) The number of solutions to the equation Sigma(i,1,n;a(i))=K solved over the positive integers is C(K-1,n-1). Here, we have C(20-1,3-1)=C(19,2).

(c) For the third situation, we introduce a new set of variables to help us reduce the problem to one we have already solved.

Let us write the equation g + w + r = 20 to represent the need to have 20 napkins of three colors. The problem situation requires that g > 3, w > 3, and r > 3. Then g-3 > 0, w-3 > 0, and r-3 > 0. Use a, b, and c to represent the left side of each of these inequalities: We have a = g-3 > 0, b = w-3 > 0, and c = r-3 > 0.

This gives us a + b + c = (g-3) + (w-3) + (r-3) = (g + w + r) - 9. Because we must have g + w + r = 20, we get a + b + c = (g + w + r) - 9 = 11.

Thus, we are left with the condition that a + b + c = 11, where each of a, b, and c must be a positive integer. We know how to determine the number of solutions to this equation (see part (b) above). It is just C(11-1,3-1) = C(10,2).

We could have generated the same solution using a slightly different argument, as follows:

The problem situation requires that g >= 4, w >= 4, and r >= 4. Then g-4 >= 0, w-4 >= 0, and r-4 >= 0. Use x, y, and z to represent the left side of each of these inequalities: We have x = g-4 >= 0, y = w-4 >= 0, and z = r-4 >= 0.

This gives us x + y + z = (g-4) + (w-4) + (r-4) = (g + w + r) - 12. Because we must have g + w + r = 20, we get x + y + z = (g + w + r) - 12 = 8.

Thus, we are left with the condition that x + y + z = 8, where each of x, y, and z must be a nonnegative integer. We know how to determine the number of solutions to this equation (see part (a) above). It is just C(8 + 3 -1,3-1) = C(10,2).

We see that either approach generates the same solution: C(10,2).

 

Problem 1.   Try to generalize the previous results.

이제  위의 생각해볼 문제에서 연구했던 triangulation에 관하여 조금 더 생각하여 봅시다.

6.Eulers's Polygon -Triangulation Problem. It was Euler who first discovered the Catalan numbers through a combinatiorial problem in plane geometry which be posed to Christian Goldbach in 1751.

 In how many ways can a convex polygon of n sides be divided into triangles by drawing diagonals that do not intersect?

 Find an explicit fomula for the number D_n of  different triangulations.

FIGURE 2.

a. Calculate D₃ , D₄, D₅, D₆ .

b. Show that no matter how the n-gon is triangulated, the number of diagonals is always n-3 and the number of triangles is n-2.

c Define D₂ =1 and show that for n≥3

D_n = D₂D_n-1+ D₃D_n-2+ D₄D_n-3 +... +D_n-1D_2.

d.Conclude that {D_n}  is the sequence of Catalan numbers, and hence that

   Fibinacci sequence와  이와 관련된 문제를 통하여

탐구적 방법으로 점화식에 대하여 학습하였다.