DM-Ch-6-Lab -- Sage

Chapter 6 Counting Methods and The Pigeon Hole Principle

Table of Contents

(DM Ch. 1, Sets and Logic, Lecture Note)  http://matrix.skku.ac.kr/2018-DM/Ch-1/
DM-Ch-1-Lab  http://math1.skku.ac.kr/home/pub/2651/   (Use Chrome browser, not IE)
    (DM Ch. 1, 동영상강의)
Discrete Math 이산수학 Ch 0 Introduction https://youtu.be/9ahFnOFTWNQ
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions https://youtu.be/QgdKqmCFW2Y
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference https://youtu.be/92siPfThf0M
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers https://youtu.be/7M7w9eX5D0Q

(DM Ch. 2, Proofs, Lecture Note)  http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab    http://math1.skku.ac.kr/home/pub/2652/
     (DM Ch. 2, 동영상강의)
DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem   https://youtu.be/xEMkHb2AkYk
DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property https://youtu.be/areatkjOjcg

(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note)  http://matrix.skku.ac.kr/2018-DM/Ch-3/
http://math1.skku.ac.kr/home/pub/2653/
     (DM Ch. 3, 동영상강의)
DM 이산수학 Ch 3, Functions, Sequences, and Relations 1  https://youtu.be/MhM_9ZuGAis
DM 이산수학 Ch 3, Functions, Sequences, and Relations 2  https://youtu.be/ZjAtN9HkZwM
DM 이산수학 Ch 3, Functions, Sequences, and Relations 3  https://youtu.be/Uuwsx2aiEPI

Ch 4, Algorithms, Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-4/
DM-Ch-4-Lab http://math1.skku.ac.kr/home/pub/2654/
(DM Ch. 4, 동영상강의)
DM 이산수학 Ch 4,
...

[Week 6] Ch 5, Introduction to Number Theory (if time permits) - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-5/
(DM Ch. 5, 동영상강의)
DM 이산수학 Ch 5,

Ch 6, Counting Methods and the Pigeonhole Principle (lightly covered) - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-6/
(DM Ch. 6, 동영상강의)
DM 이산수학 Ch 6,

Ch 7, Recurrence Relations, - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-7/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

Ch 8, Graph Theory (if time permits), - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-8/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

Ch 9, Trees (if time permits), - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-9/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

10 Network Models (if time permits)
11 Boolean Algebras and Combinatorial Circuits (if time permits)
12 Automata, Grammars, and Languages (if time permits)
13 Computational Geometry (if time permits)
Appendix

Ch - Lecture Note http://matrix.skku.ac.kr/2018-DM/Ch-10/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,

...
...

[References]

1. Discrete Math - 7th Edition , Richard Johnsonbaugh, Pearson

6 Counting Methods and

the Pigeonhole Principle

6.1 Basic Principles

6.2 Permutations and Combinations

6.3 Generalized Permutations and Combinations

*6.4 Algorithms for Generating Permutations and

Combinations(Skipped)

*6.5 Introduction to Discrete Probability(Skipped)

*6.6 Discrete Probability Theory(Skipped)

6.7 Binomial Coefficients and Combinatorial Identities

6.8 The Pigeonhole Principle

We must count objects to solve many different types of problems. For instance, counting is used to determine the complexity of algorithms. Furthermore, counting techniques are used extensively when probabilities of events are computed.

6.1 Basic Principles

Figure 1.1 Kay’s Quick Lunch menu

APPETIZERS

Nachos (N) 2.15

Salad (S) 1.90

MAIN COURSES

Hamburger 3.25

Cheeseburger 3.65

Fish Filet 3.15

BEVERAGES

Tea 0.70

Milk 0.85

Cola 0.75

Root Beer 0.75

Menu for Quick Lunch:

There are two appetizer, three main courses and four beverages and .

HT, HM, HC, HR, CT, CM, CC, CR, FT, FM, FC, FR ()

And

NHT, NHM, NHC, NHR, NCT, NCM, NCC, NCR, NFT, NFM, NFC, NFR,

12 with Nachos (N), +

12 with Salad (S) = 24.

SHT, SHM, SHC, SHR, SCT, SCM, SCC, SCR, SFT, SFM, SFC, SFR

Multiplication Principle	(Product Rule)

The problem of counting the number of dinners consisting of one appetizer, one main course and one beverage,

First step is “select the appetizer.”

Second step is “select the main course.”

Third step is “select the beverage.”

By the Multiplication Principle,

, and , the total number of dinner is .

Example 1.1
How many dinners are available from Kay’s Quick Lunch consisting of one main course and an optional (선택 안해도 되는) beverage?

Solution

A dinners consisting of one main course and an optional beverage by a two-step process.

The first step is “select the main course.”

The second step is “select an optional (선택 안해도 되는) beverage.”

The main course selected ways.

The optional beverage selected ways. (Tea, Milk, Cola, Root Beer, NONE)

By the Multiplication Principle,

There is dinners.

List the dinners(N no beverage):

HT, HM, HC, HR, HN, CT CM, CC, CR, CN, FT, FM, FC, FR, FN.

Example 1.3

(a) How many strings of length can be formed using the letters

if repetitions are not allowed?

(b) How many strings of (a) begin with the letter ?

Solution

(a)

The first letter selected five ways.

The second letter selected four ways.

The third letter selected three ways.

The forth letter selected two ways.

By the Multiplication Principle,

(b)

The first letter fix.

The second letter selected four ways.

The third letter selected three ways.

The forth letter selected two ways.

By the Multiplication Principle,

Part (b) shows that of these start with letter .

So, the first letter no is

Example 1.4
In a digital picture, we wish to encode the amount of light at each point as an eight-bit string. How many values are possible at one point?

Solution

The first bit selected two ways.

The second bit selected two ways.

The third bit selected two ways.

The forth bit selected two ways.

The eight bit selected two ways.

Two ways to select each bit.

By the Multiplication Principle,

The total number of eight-bit encoding is

Example 1.5
Use the Multiplication Principle to show that a set consisting elements has subsets.

Solution

A subset can be constructed in successive step.

Pick or do not pick .

Each step can be done in two ways.

Thus the number of possible subsets is

Example 1.6
Let be an -element set. How many ordered pairs satisfy ?

Solution

An ordered pairs satisfying .

Each element in is in exactly one of , , or .

Assign each element of to one of the three sets , or ,

we obtain a unique ordered pairs satisfying .

Thus the number of ordered pairs satisfying is equal to the number of ways to assign the elements of to the three sets , and .

We can make such assignments by the following -step process:

Assign the first elements of to one of , , .

Assign the second elements of to one of , , .

Assign the elements of to one of , , .

The number of ordered pairs satisfying is

Example 1.7
How many reflexive relations are there on an -element set?

Solution

We count the number of matrices that represent reflexive relations on an -element set .

, is in the relation the main diagonal of the matrix have ’s.

No restriction on off-diagonal entries of the matrix, so it can be or .

An matrix has entries.

The diagonal contains entries.

The number of Off-diagonal entries in a matrix is .

Since each can be assigned values in two ways,

By the Multiplication Principle there are

matrices that represent reflexive relations on an -element set.

Therefore there are reflexive relations on an -element set.

Example 1.8	Internet Addresses, https://en.wikipedia.org/wiki/IP_address

[ IPv6 addresses, 128-bit ]

* IPv4 addresses have been distributed by IANA to the RIRs in blocks of approximately 16.8 million addresses each.

Example 1.9
How many eight-bit strings begin either or ?

Solution

An eight-bit strings begin can be constructed in five successive steps :

There are

eight-bit strings that begin .

An eight-bit strings begin can be constructed in five successive steps :

There are

eight-bit strings that begin .

There are eight-bit strings that begin .

There are

eight-bit strings that begin either or .

Addition Principle

Example 1.10
In how many ways can we select two books from different subjects among five(5)distinct computer science books, three(3) distinct mathematics books, and two(2) distinct art books?

Using the Multiplication Principle,

We can select two books,

One from computer science and one from mathematics are ways.

One from computer science and one from art are ways,

One from mathematics and one from art are ways.

These sets of selections are pairwise disjoint, using the Addition Principle.

There are

ways of selecting two books from different subjects among the computer science, mathematics and art books.

Example 1.11

skip

A six-person committee composed of Alice, Ben Connie, Dolph, Egbert and Francisco is to select a chairperson, secretary and treasurer.

(a) In how many ways can this be done?

(b) In how many ways can this be done if either Alice or Ben must be chairperson?

(d) In how many ways can this be done if both Dolph and Francisco must hold office?

Solution

Using the Multiplication Principle

(a) We can select three man. chairperson, secretary and treasurer

The chairperson selected in ways,

The secretary selected in ways,

The treasurer selected in ways.

(b) Alice is chairperson

The secretary selected in ways,

The treasurer selected in ways.

Ben is chairperson

The secretary selected in ways,

The treasurer selected in ways.

Since these cases are disjoint, by the Addition Principle, there are

possibilities.

The secretary selected in ways,

The treasurer selected in ways.

Egbert is secretary

The chairperson selected in ways,

The treasurer selected in ways.

Egbert is treasurer

The chairperson selected in ways,

The secretary selected in ways.

Since these cases are pairwise disjoint, by the Addition Principle, there are

possibilities.

(d) Assign Dolph, assign Francisco; fill the remaining office.

There are three ways to assign Dolph.

Once Dolph has been assigned, there are two ways to assign Francisco.

Once Dolph and Francisco have been assigned,

there are four ways to fill the remaining office.

By the Addition Principle, there are

possibilities.

The Inclusion-Exclusion Principle generalizes the Addition Principle by giving a formula to compute the number of elements in a union.

Figure 1.13 counts the number of elements in and , and counts the number of elements in and .

Since double-counts the elements in , .

Theorem 1.12

Inclusion-Exclusion Principle for Two Sets

If and are finite sets, then

Proof

Since and, and are disjoint.

By the Addition Principle

and and are disjoint.

By the Addition Principle

and , and are pairwise disjoint. By the Addition Principle

Example 1.13
A committee composed of Alice, Ben, Connie, Dolph, Egbert and Francisco is to select a chairperson, secretary and treasurer. How many selections are there in which either Alice or Dolph or both are offices?

Solution

Let be the set of selection in which Alice is an officer.

Let be the set of selection in which Dolph is an officer.

We first count the number of selection in which Alice is an officer.

Alice can be assigned an office in three ways. (3, chairperson, secretary and treasurer)

The highest remaining office can be filled in five ways. (5)

The last office can be filled in four ways. (4)

There are three ways to assign Alice.

The number of selection in which Alice is an officer is , that is .

Dolph can be assigned an office in three ways.

The highest remaining office can be filled in five ways.

The last office can be filled in four ways.

There are three ways to assign Alice.

The number of selection in which Dolph is an officer is , that is .

[Both] is the set of selection in which both Alice and Dolph are officers.

Alice can be assigned an office in three ways. (3)

The last office can be filled in four ways. (4)

The number of selection in which both Alice and Dolph are officer is , that is and .

By the Inclusion-Exclusion Principle, there are

= . (Exs 92~97)

6.2 Permutations and Combinations

Definition 2.1
A Permutation of distinct elements , , is an ordering of the elements , , .

Example 2.2

There are six permutations of three elements , , .

The six permutations are

, , , , , .

Theorem 2.3	number of Permutations = n! (factorial)

Example 2.5	Four tokens to permute^^

Example 2.6
How many permutations of the letters contain the letters together in any order?

Solution

Select an ordering of the letters :

Select an ordering of the letters , , , :

By the Multiplication Principle,

the number of permutations of the letters containing the letters together in any order is

Example 2.7
In how many ways can six persons be seated around a circular table?

Solution

Let us denote the persons as , , , and .

Fix one seat, say is fixed. find seat for remaining 5 persons.

=> permutations of five elements, there are ways that six persons can be seated around a circular table.

There are ways that persons can be seated around a circular table.

Definition 2.8	-permutation of (distinct) elements

Example 2.9

ordering picks, Read Theorem 2.10

Examples of 2-permutations of are

Theorem 2.10

The numbers of -permutation of a set of distinct objects is

, .

Proof

To count the number of ways to order elements selected from an -element set.

The first element selected in ways.

The first element has been selected, the second element selected in ways.

We continue selecting elements until having selected.

The st element has been selected, the elements selected in ways.

By the Multiplication Principle,

The number of -permutation of a set of distinct objects is

* Write in terms of factorials.

Example 2.11

According to Theorem 2.10, the number of -permutations of is

These six -permutations are

, , , , , .

Example 2.12
In how many ways can select a chairperson, vice-chairperson, secretary, and treasurer (4) from a group of persons?

Solution

An ordering picks (uniquely) a chairperson (first pick), a vice-chairperson (second pick), a secretary (third pick), and treasurer (fourth pick).

Count the number of orderings of four persons selected from a group of .

By Theorem 2.10, the solution is

Example 2.14	skip
In how many ways can seven distinct Martins and five distinct Jovians wait in line if no two Jovians stand together?

Solution

Line up the Martins and Jovians by a two-step process:

Line up the Martins, line up the Jovians

The Martins can line up in .

The Jovians can stand in .

By the Multiplication Principle,

the number of ways seven distinct Martins and five distinct Jovians can wait in line if no two Jovians stand together is

Definition 2.15

Given a set containing (distinct) elements,

(a) An -combination of is an unordered selection of -elements of (i.e. an -element subset of ).

(b) The number of -combination of a set of distinct elements is or .

Example 2.16
The number of ways the five student can choose three of their group to talk with the chairperson is , the number of -elements of five elements.

Solution

We have found that

Theorem 2.17

The numbers of -combinations of a set of distinct objects is

, .

Example 2.18
In how many ways can we select a committee of three from a group of distinct persons?

Solution

Since a committee is an unordered group of people, the answer is

Example 2.19
In how many ways can we select a committee of two (2) women and three (3) men from a group of five (5) distinct women and six (6) distinct men?

Solution

The two women can be selected in

ways.

The three men can be selected in

ways.

Select the women; select the men.

By the Multiplication Principle,

The total number of committees is

Example 2.20
How many eight-bit strings contain exactly four ’s?

Solution

An eight-bit strings containing four ’s is uniquely determined once we tell which bits are . This can be done in

ways.

Example 2.21

An ordinary deck of cards consists of four suits

clubs, diamonds, hearts, spades

of denominations each

ace, , jack, queen, king.

(a) How many (unordered) five-card porker hands, selected from an ordinary card deck are there?

(b) How many poker hands contain cards all the same suit?

Solution

(a) The combination formula is

(b) A hand containing cards all of the same suit can be constructed in two successive steps:

Step 1 Select one pattern

Step 2 select five cards from the chosen pattern.

The first step is in four ways.

The second step is in ways.

By the Multiplication Principle, the answers is

(c) A hand containing three cards of one denomination and two cards of a second denomination can be constructed in four successive steps:

Select the first denomination

select the second denomination

select three cards of the first denomination

select two cards of the second denomination

The first denomination can be chosen ways.

Having selected the first denomination, we can choose the second denomination in ways.

We can select three cards of the first denomination in ways.

We can select two cards of the second denomination in ways.

By the Multiplication Principle, the answers is

Example 2.22
How many routes are there from the lower-left corner of an square grid to the upper-right corner if we are restricted to traveling only to the right or upward?

Solution

One such route is shown in a grid.

Each route can be described by a string of ’s (right) and ’s(up).

We can described by the string .

String can be obtained by unorder of selecting positions for the ’s, among the positions in the string.

Filling the remaining positions with ’s.

There are possible route.

(a) (b)

Figure 6.2.5

Example 2.23
How many routes are there from the lower-left corner of an square grid to the upper-right corner if we are restricted to traveling only to the right or upward and if we are allowed to touch but not go above a diagonal line from the lower-left corner to the upper-right corner?

Solution

good route: a route that touches but does not go above the diagonal

bad route: a route that goes above the diagonal

We count the number of good routes.

denote the number of good routes.

denote the number of bad routes.

Compute the number of bad routes. in Figure 6.2.5 (b)

grid : from the lower-left corner to the upper-right corner

route.

The number of bad routes is equal to the number of routes.

using bijection function on the set of bad routes and the set of ...

Given a bad route

find the first move that takes it above the diagonal

replace each right move by up move

replace each up move by right move

This transformation can also be effected by rotating the portion of the route following the first move above the diagonal above the dashed line.

Each bad route is an route.

Show that onto function.

Consider route. Since this route ends above the diagonal, there is a first move where it goes above the diagonal.

We may then route the remainder of the route above the dashed line to obtain a bad route. The image of this bad route under our function is the route which we started.

Therefore, our function is onto.

Our function is one-one.

The function transforms distinct bad routes to distinct route.

Therefore the number of bad routes equals the numbers of routes.

The numbers of routes is equal to .

Thus the number of good routes is equal to

EUGÈNE CATALAN (1814–1894)

Catalan was a Belgian mathematician who defined the numbers called after him, while considering the solution of the problem of dissecting a polygon into triangles by means of non-intersecting diagonals.

CATALAN NUMBER http://matrix.skku.ac.kr/sglee/catalan/catalan.htm

Catalan numbers are defined by the formula

for and .

Catalan numbers are

Pseudo-Catalan number

Pseudo-Catalan numbers are defined by the formula

for .

(),

* Fibonacci number (optional)

In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:

By definition, the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

A general term of Fibonacci series is .

Note: 기본적인 피보나치 수열은 , , ,

의 형태로, 식의 수열이 된다.

피보나치 수의 특징 :

1) 1로 시작한다.

2) 처음에 똑같은 두 수가 반복된다.

3) 연속하는 두 수의 합이 다음에 나타난다.

4) 수들이 홀수, 홀수, 짝수로 이루어져 있다.

이 수열의 규칙을 행렬로 찾아보면,

이 식들로부터 , 이라고 정의 하면,

로 알아 볼 수 있다. 의 eigenvalue를 구해 보면,

이를 만족하는 는 근해 공식에 의하여, 이 되고, 따라서 의 eigenvalue는 약 1.618033989 와 약 -0.618033989 임을 알 수 있다.

여기서, 각 항들의 증가 비율은 이 되고,

이 비율이 엑셀파일의 처음 탭과 같은 형태로 하나의 값으로 수렴함을 알 수 있다. 이 값은 위에서 주어진 의 eigenvalue 중 큰 값으로 수렴함을 알 수 있다.

참고 : http://www.maths.abdn.ac.uk/~igc/tch/ma2001/notes/node31.html

http://www.mathacademy.com/pr/prime/articles/fibonac/index.asp

- 피보나치 수의 엑셀에서의 구현

Fibonacci Number.xls

피보나치 수를 엑셀에서 구현하기 위해 우선 위와 같이 각 항의 숫자를 만든다. 우선 셀 A2에 “1”을 입력하고, 셀 A3에 “=A2+1”을 입력한다. 그리고 난 후 셀 A3을 선택하고 해당 셀의 오른쪽하단에 마우스커서를 위치한 다음 마우스 왼쪽 버튼을 클릭한 채 아래로 끌어당긴다. 그러면 다음과 같이 자연수가 만들어짐을 알 수 있다.

다음은 실제 피보나치 수를 만들기 위하여 셀 B2와 셀 B3에 위와 같이 “1”을 입력한다. 그리고 셀 B4에 “=B2+B3”을 입력한다. 그리고 난 후 셀 B4를 선택하고 해당 셀의 오른쪽하단에 마우스커서를 위치한 다음 마우스 왼쪽 버튼을 클릭한 채 아래로 끌어당긴다. 그러면 다음과 같이 피보나치 수를 만들 수 있다.

이제는 각 항의 비율()을 확인하기 위해 위와 같이 셀 C3에 “=B3/B2”를 입력한다. 그리고 난 후 셀 B3을 선택하고 해당 셀의 오른쪽하단에 마우스커서를 위치한 다음 마우스 왼쪽 버튼을 클릭한 채 아래로 끌어당긴다. 그러면 다음과 같이 각 항에 대한 피보나치 수의 비율을 확인할 수 있다.

- 피보나치 수와 황금비

에서 두 연속되는 피보나치 수의 비율을 라고 한다면, 이다.

다시 말하면, 로 나타낼 수 있고, 이다.

따라서, 이 되고, 일반적인 피보나치 수의 비율은 양수이므로

가 된다.

- 피보나치 수의 행렬에서의 의미

의 원소 은 다음과 같은 식을 만족한다.

, .

피보나치 수의 각 항의 비율()을 구하기 위하여, 만약 라고 한다면,

이고, 이다.

또한, 충분히 큰 에 대하여 는 의 가장 큰 고유값이 된다.

즉, 의 두 고유값은 와 이 되고, 이 중 큰 고유값인

이 된다.

Power method 2x2.xls

Properties of Fibonacci

(1)

[Sol]

(2)

[Sol]

, , , ,

(3)

[Sol], ,

(4)

[Sol]

(5)

(6)

[Sol]By (5), Let

(7)

[Sol]

Hence

(8)

[Sol]

(9)

(10)

(11)

[Sol]

(12) ()

[Sol]

Example 2.24
What is wrong with the following argument, which purports to show that there are bit strings of length containing at least five ’s?

Solution

We can construct bit strings of length by filling each of eight slots

with strings or .

There are at least five ’s, we choose five slots and place a in each of them.

The five slots chosen in ways.

The remaining place has or .

Each of the three remaining slots filled in two ways.

The remaining slots filled in ways.

There are bit strings of length containing at least five ’s

The problem is that some strings are counted more than one time. Foe example,

To construct a bit string of length containing exactly five ’s, we choose five slots for the ’s and put ’s in the other three slots.

Since we can choose five slots in ways,

There are bit string of length containing exactly five ’s.

There are bit string of length containing exactly six ’s, and so on.

Therefore, there are

bit string of length containing at least five ’s.

Exercises 7, 13, 16, 19, 24, 28, 36, 39

6.3 Generalized Permutations and Combinations

Example 3.1

How many strings can be formed using the following letters?

Solution

Let us consider the problem of filling blanks,

with the letters given.

Assign positions for the two ’s are ways.

Once the positions for the ’s have been selected,

assign positions for the four ’s are ways.

Once the positions for the ’s have been selected,

assign positions for the four ’s are ways.

Once these selections have been made, there is one position left to be filled by the .

By the Multiplication Principle,

The number of ways of ordering the letters is

Theorem 3.2

Suppose that a sequence of item has

identical objects of type ,

identical objects of type , , and

identical objects of type .

Then the number of orderings of is

Proof

We assign positions to each of the item to create an orderings of .

We may assign positions to the items of type in ways.

Having made these assignments,

We may assign positions to the items of type in ways, and so on.

By the Multiplication Principle, the number of orderings is

Example 3.3

Example 3.4
Consider three books; a computer science book, a physics book and a history book. Suppose that the library has at least six copies (should have six copies) of each of these books. In how many ways can we select six books?

Solution (none or repetition allowed)

The number of ways of selecting two positions for the from eight possible position. There are ways to select six books.

Theorem 3.5

If is a set containing elements, the number of unordered, -element selections from , repetitions allowed, is

Proof

Example 3.6

Suppose that there are piles of red, blue and green balls (=3) and that each pile contains at least eight (8=) balls.

(a) In how many ways can select eight balls?

(b) In how many ways can select eight balls if we must have at least one ball of each color?

Solution

By Theorem 3.5, the number of ways of selecting eight balls is (공을 3개 상자에 8개 담는 방법) (=3, 8=)

We can also use Theorem 3.5 to solve part (b) if we first select one ball of each color. To complete the selection, we must choose five additional balls (5=). This can be done in

ways. (공을 <우선 하나씩 3개 채우고> 3개 상자에 5개 담는 방법) (=3, 8=)

Example 3.7
In how many ways can identical mathematics books (12=) be distributed among the students Anna, Beth, Candy and Dan (=4)?

Solution

Example 3.8

(a) How many solutions in nonnegative integers are there to the equation

(b) How many solutions in integers are there to the equation satisfying , , , ?

Solution

(a) Each solution of is equivalent to selecting items of type , . According to Theorem 3.5, the numbers of selections is

. (1을 4개 상자에 29개 담는 방법) (=4, 29=)

(b) Selecting items, of type ,

First select one item of type

Second select two items of type

Third select three items of type (29 - 6 = 23)

Then choose addition items. By Theorem 3.5, this can be done in

(1을 4개 상자에 23개 담는 방법)

The following table summarizes the various formulas:

	No Repetitions	Repetitions Allowed
Ordered Selections
Unordered Selections

Do. p.338~339 Exercises

1, 4, 10, 14, 15, 18, 22, 25, 42, 45

6.7 Binomial Coefficients and Combinatorial Identities

The Binomial Theorem gives a formula for the coefficients in the expansion of . Since

TABLE 6.7.1 Computing .

Selection from

First Factor

Selection from

Second Factor

Selection from

Third Factor

Product of

Selections

Example 7.2
.

Theorem 7.1

Binomial Theorem

If and , then

Example 7.3
Expand using the Binomial Theorem.

Solution

Example 7.4
Find the coefficient of in the expansion of .

Solution

Taking and

The coefficient of is .

Example 7.5
Find the coefficient of in the expansion of .

Solution

Step 1. chosen from two (2) of the nine (9) terms,

Step 2. chosen from three of the nine terms,

Step 3. chosen from four of the nine terms.

Chosen two terms for the ’s in ways.

Chosen three terms for the ’s in ways.

Chosen four terms for the ’s in ways.

The coefficient of in the expansion of is

The coefficient of is .

Pascal’s triangle

Binomial coefficients in a triangular form

Figure 6.7.1 Pascal’s triangle

An identity that results from some counting process is a combinatorial identity.

The argument that leads to its formulation is combinatorial argument.

Theorem 7.6
Prove that for .

Proof

[Better Proof]

Example 7.7

Use the Binomial Theorem to derive the equation

(7.3) .

Proof

From the Binomial Theorem becomes

Example 7.8
Show that .

Solution

Using Theorem 7.6,

Example 7.9
Find the sum .

Solution

by Ex 7.8

Exercises 3, 6, 22

6.8 The Pigeonhole Principle

The Pigeonhole Principle (the Dirichlet Drawer Principle or the Shoe Box Principle) is sometimes useful in answering the question: Is there an item having a given property? When the Pigeonhole Principle is successfully applied, the principle tells us only that the object exists; the principle will not tells us how to find the object or how many three are.

Figure 6.8.1 pigeons in pigeonholes.

Pigeonhole Principle (1st Form)
If pigeons fly into pigeonholes and , some pigeonhole contains at least two pigeons.

Example 8.1

The persons have first names Alice, Bernard and Charles and last names Lee, McDuff, and Ng. Show that at least two persons have the same first and last names.

There are nine possible names for the persons.

Solution

There are nine possible names for th 10 persons.

The persons is pigeons. The names is pigeonholes.

Assignment of names to people assigning pigeonholes to the pigeons.

By the Pigeonhole Principle,

some name (pigeonhole) is assigned to at least two persons (pigeons).

Pigeonhole Principle (2nd Form)
If is a function from a finite set to a finite set and , then for some , .

is set of pigeons. is set of pigeonholes.

We assign pigeon to pigeonhole .

Example 8.3
Show that if we select distinct computer science courses numbered between and inclusive, at least two are consecutively numbered.

Solution

Let the selected course numbers be

(8.1) , , , .

The numbers consisting of 8.1 together with

(8.2) , , ,

range in value between and .

By the second from of the Pigeonhole Principle, at least two of these values coincide.

The numbers 8.1 are distinct The numbers 8.2 are distinct.

That one of 8.1 and one of 8.2 are equal. Thus we have

and course follows course .

Pigeonhole Principle (3rd Form)
Let be a function from a finite set into a finite set .

Suppose that and .

Let .

Then there are at least values such that

Example 8.5

A useful feature of black-and-white picture is the average brightness of the picture.

Let us say that two pictures are similar if their average brightness differs by no more than some fixed value. Show that among six pictures, there are either three that are mutually similar or three that are mutually dissimilar.

Solution

Denote the pictures , , , .

Each of the five pairs

, , , , ,

has the value “similar” or “dissimilar.”

By the third from of the Pigeonhole Principle, there are at least pairs with the same value; that is, there are three pairs

, ,

all similar or all dissimilar. Suppose that each pair is similar.

If any pair

(8.5) , ,

is similar, then these two pictures together with are mutually similar and we have found there mutually similar pictures.

Otherwise, each of the pairs 8.5 is dissimilar and we have found three mutually dissimilar pictures.

Chapter 6, Report Number

Chapter Review

Section 1

1, 2, 3

Section 2

7, 9

Section 7

28, 29

Section 8

Chapter Self-Test

Section 1

1, 4

Section 2

6, 8

Section 3

11, 12

Section 7

25, 26

Section 8

30, 31

Copyright @ 2018 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1D1A1B03035865).