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 ,

...
...




 

 


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 ?

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

         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 ?

      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 .

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?

 (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 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?

 (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 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

30


Chapter Self-Test

Section 1

1,  4


Section 2

6,  8


Section 3


11,  12


Section 7

25,  26


Section 8

30,  31



Copyright@   skku  sglee@skku.edu