Table of Contents
(DM Ch. 1, Sets and Logic,
Lecture Note) http://matrix.skku.ac.kr/2018DM/Ch1/
DMCh1Lab 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/2018DM/Ch2/
DMCh2Lab
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 WellOrdering Property https://youtu.be/areatkjOjcg
(DM Ch. 3, Functions,
Sequences, and Relations, Lecture Note) http://matrix.skku.ac.kr/2018DM/Ch3/
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/2018DM/Ch4/
DMCh4Lab 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/2018DM/Ch5/
(DM Ch. 5, 동영상강의)
DM 이산수학 Ch 5,
Ch 6,
Counting Methods and the Pigeonhole Principle (lightly covered)  Lecture Note
http://matrix.skku.ac.kr/2018DM/Ch6/
(DM Ch. 6, 동영상강의)
DM 이산수학 Ch 6,
Ch 7,
Recurrence Relations,  Lecture Note http://matrix.skku.ac.kr/2018DM/Ch7/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,
Ch 8, Graph
Theory (if time permits),  Lecture Note http://matrix.skku.ac.kr/2018DM/Ch8/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,
Ch 9, Trees (if
time permits),  Lecture Note http://matrix.skku.ac.kr/2018DM/Ch9/
(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/2018DM/Ch10/
(DM Ch. , 동영상강의)
DM 이산수학 Ch ,
...
...
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 twostep 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 ? (c) How many strings of (a) do not 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,
(c) Part (a) shows that there are strings of length .
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 eightbit 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 eightbit 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 .
Pick or do not pick .
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 ? 
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 offdiagonal entries of the matrix, so it can be or .
An matrix has entries.
The diagonal contains entries.
The number of Offdiagonal 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, 128bit ]
* IPv4 addresses have been distributed by IANA to the RIRs in blocks of approximately 16.8 million addresses each.
Example 1.9 

How many eightbit strings begin either or ? 
Solution
An eightbit strings begin can be constructed in five successive steps :
There are
eightbit strings that begin .
An eightbit strings begin can be constructed in five successive steps :
There are
eightbit strings that begin .
There are eightbit strings that begin .
There are eightbit strings that begin .
There are
eightbit 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 sixperson 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? (c) In how many ways can this be done if Egbert must hold one of the offices? (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.
(c) Egbert is chairperson
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 InclusionExclusion 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 doublecounts the elements in , .
Theorem 1.12 
InclusionExclusion 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 InclusionExclusion 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 2permutations 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, vicechairperson, secretary, and treasurer (4) from a group of persons? 
Solution
An ordering picks (uniquely) a chairperson (first pick), a vicechairperson (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 twostep 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 eightbit strings contain exactly four ’s? 
Solution
An eightbit 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) fivecard porker hands, selected from an ordinary card deck are there? (b) How many poker hands contain cards all the same suit? (c) How many poker hands contain three cards of one denomination and two cards of a second denomination? 
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 lowerleft corner of an square grid to the upperright 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 lowerleft corner of an square grid to the upperright 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 lowerleft corner to the upperright 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 lowerleft corner to the upperright 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 oneone.
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 nonintersecting diagonals.
CATALAN NUMBER http://matrix.skku.ac.kr/sglee/catalan/catalan.htm
Catalan numbers are defined by the formula
for and .
Catalan numbers are
.
PseudoCatalan number
PseudoCatalan 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
 피보나치 수의 엑셀에서의 구현
피보나치 수를 엑셀에서 구현하기 위해 우선 위와 같이 각 항의 숫자를 만든다. 우선 셀 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 blackandwhite 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
30
Chapter SelfTest
Section 1
1, 4
Section 2
6, 8
Section 3
11, 12
Section 7
25, 26
Section 8
30, 31