Dm 1i56m

Discrete Mathematics Chapter 1 Fundamental Principles of Counting

Textbook: Discrete and Combinatorial Mathematics: An Applied Introduction 5rd edition, by Ralph P. Grimaldi Course Outlines: 1. Fundamental Principles of Counting 2. Fundamentals of Logic 3. Set Theory 4. Mathematical Induction 5. Relations and Functions 6. Languages: Finite State Machines 7. The principle of Inclusion and Exclusion 8. Generating Functions 9. Recurrence Relations 10. Graph Theory 11. Number Theory 2

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product problem

decompose

combine

The Rule of Sum 第一件工作 第二件工作 m ways n ways can not be done simultaneously then performing either task can be accomplished in any one of m+n ways 3

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product E.g. 1.1: 40 textbooks on sociology 50 textbooks on anthropology to select 1 book: 40+50 choices What about selecting 2 books?

4

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product E.g. 1.2: things 1

2

3 ... k

ways m1 m2 m3

mk

select one of them: m1 +m2 +m3 +...+ mk ways

5

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product The Rule of Product 第一階段工作 m ways

第二階段工作 n ways

then performing this task can be accomplished in any one of mn ways

6

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product The Rule of Product E.g. 1.6. The license plate: 2 letters-4 digits (a) no letter or digit can be repeated 26  25  10  9  8  7 (b) with repetitions allowed 26  26  10  10  10  10 (c) same as (b), but only vowels and even digits 52 x54 7

Chapter 1: Fundamental Principles of Counting

1.1 The Rules of Sum and Product

BASIC variables: single letter or single letter+single digit 26+26x10=286

rule of sum

rule of product

8

Chapter 1: Fundamental Principles of Counting

1.2 Permutations E.g. 1.9. 10個學生,選5個出來排隊 10  9  8  7  6 Def 1.1 For an integer n≧0, n factorial (denoted n!) is defined by 0!=1, n!=(n)(n-1)(n-2)...(3)(2)(1), for n≧1.

Beware how fast n! increases. 10!=3628800 210=1024 9

Chapter 1: Fundamental Principles of Counting 1.2 Permutations Def 1.2 Given a collection of n distinct objects, any (linear) arrangement of these objects is called a permutation of the collection.

n個選r個的排列方法 n  ( n  1)  ( n  2 )  . . . ( n  r  1) 

n!  P( n , r ) (n  r ) !

if repetitions are allowed: nr

10

Chapter 1: Fundamental Principles of Counting

1.2 Permutations E.g. 1.11 permutation of BALL 4!/2!=12

E.g. 1.12 permutation of PEPPER 6!/(3!2!)=60 E.g. 1.13 permutation of MASSASAUGA 10!/(4!3!)=25200 if all 4 A’s are together 7!/3!=840

11

Chapter 1: Fundamental Principles of Counting

1.2 Permutations E.g. 1.14 Number of Manhattan paths between two points with integer coordinated From (2,1) to (7,4): 3 Ups, 5 Rights Each permutation of UUURRRRR is a path.

8!/(5!3!)=56

12

Chapter 1: Fundamental Principles of Counting Combinatorial Proof E.g. 1.15 Prove that if n and k are positive integers with n=2k, then n!/2k is an integer. Consider the n symbols x1,x1,x2,x2,...,xk,xk. Their permutation is

n! n!  k 2 ! 2 !. . . 2! 2  k

must be an integer 13

Chapter 1: Fundamental Principles of Counting

circular permutation E.g. 1.16 6 people are seated about a round table, how many different circular arrangements are possible, if arrangements are considered the same when one can be obtained from the other by rotations? ABCDEF,BCDEFA,CDEFAB,DEFABC,EFABCD,FABCDE are the same arrangements circularly. 6!/6=5! (in general, n!/n)

14

Chapter 1: Fundamental Principles of Counting

circular permutation E.g. 1.17 3 couples in a round table with alternating sex F M1

1 way M3 total= 3  2  2  1 1

F2 1 way

3 ways

2 ways

F3 M2

2 ways 15

Chapter 1: Fundamental Principles of Counting

Exercise 1.1 and 1.2 on page 11. 11,22, 26, 28,30

16

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem When dealing with any counting problem, we should ask ourselves about the importance of order in the problem. When order is relevant, we think in of permutations and arrangements and the rule of product. When order is not relevant, combinations could play a key role in solving the problem.

17

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem E.g. 1.19 (a)考試時,可回答十題中任七題的方法: C(10,7) (b)前五題答三題,後五題答四題: C( 5,3)  C( 5,4) (c)前五題至少答三題 •前五題答三題: •前五題答四題: •前五題答五題:

C( 5,3)  C( 5,4) C (5,4)  C (5,3)

加起來

C (5,5)  C (5,2)

18

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem E.g. 1.21 36個學生組成四隻球隊,每隊9人的方法 method 1.

36! C( 36,9 )  C( 27 ,9 )  C(18,9 )  C( 9 ,9 )  9 !9 !9 !9 ! method 2. students 1 2 3 4 ... 36 teams ABCD ... B (9 As,9Bs,9Cs,9Ds)

19

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Select 3 cards from a deck of playing cards without replacement: order of selection is relevant: P(52,3)= 52  51 50 order of selection is irrelevant: P(52,3)/3!=C(52,3)

P( n , r ) n! C( n , r )   ,0  r  n r! r !( n  r ) !

20

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem 11! E.g. 1.22 TALLAHASSEE permutation= 3!2 !2 !2 !1!1!  831,600

without adjacent A:

8!  9   2 !2 !2 !  3

disregard A first

9 positions for 3 A to be inserted

Challenge: Mississippi相同字母不相鄰的排列? (Write a program to your answer.) 21

Chapter 1: Fundamental Principles of Counting

The Sigma notation n

n

i1

j 1

 a i   a j  a1  a 2  a n

For example,

n ( n  1)  1  n ,  i  1  2 n  2 i 1 i1 n n ( n  1)( 2 n  1) n 3 2 ,i  ? i  6 i 1 i 1 n

n

You will learn how to compute something like that later. 22

Chapter 1: Fundamental Principles of Counting The Sigma notation n

n

i 1

i 1

c  ai   cai (constant can move out) n

n

i 1

i 1

But, not i  ai   iai n

n

n

i 1

i 1

i 1

 ( a i  bi )   a i   bi

23

Chapter 1: Fundamental Principles of Counting

The Sigma notation n

For example,  ( 2n  1)( n  2) i 1 n

 n(2n  1)(n  2) n

2 ( 2 i  1 )( i  2 )  ( 2 i  3i  2)   

i 1

i 1

n

n

n

i 1

i 1

2  i  3 i  2  1 i 1

2

24

Chapter 1: Fundamental Principles of Counting

The Sigma notation n m

m

n

j 1i 1

i 1

j 1

n

n

  ai b j   ai  b j j

  a i b j   b j ( a1  a 2  a j ) 

j 1i 1

j 1

n

a1b1  ( a1  a 2 ) b2  bn  a i i 1

25

Chapter 1: Fundamental Principles of Counting

The Pi notation n

 a i  a1  a 2  a n

i 1 n

n

 ca i  c  a i

i 1

n

i 1

n

n

n

i 1

i 1

i 1

 ( a i  bi )   a i   bi

26

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem E.g. 1.23

alphabets: a,b,c,d,...,1,2,3,...

symbols: a,b,c,ab,cde,... strings: concatenation of symbols, ababab,bcbdgfh,... languages: set of strings

{0,1,00,01,10,11,000,001,010,011,100,101,...} ={all strings made up from 0 and 1}

27

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem E.g. 1.23 由0,1,2構成的長度為 n的string有3n個 if

x  x1x2  xn , n

define wt ( x)   xi i 1

for example, wt(000)=0, wt(1200)=3

28

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem E.g. 1.23 Among the 310 strings of length 10, how many have even weight? Ans.: the number of 1’s must be even number of 1’s=i (i=0,2,4,6,8, or 10) 10  10i number of strings=  2 i  5  10  total=   2102n n 0  2n 

Select i positions for the i 1’s 29

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Be careful not to overcount. E.g. 1.24 Select 5 cards which have at least 1 club. reasoning (a): all minus no-club

 52  39       2 ,023,203  5  5

reasoning (b): select 1 club first, then other 4 cards

 13  51      3,248,700  1 4 

What went wrong?

30

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Be careful not to overcount. E.g. 1.24 Select 5 cards which have at least 1 club. for reasoning (b): select C3 then C5,CK,H7,SJ select C5 then C3,CK,H7,SJ

All are the same selections.

select CK then C5,C3,H7,SJ 31

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Be careful not to overcount. E.g. 1.24 Select 5 cards which have at least 1 club. for reasoning (b):

correct computation 13  39    2,023,203    i 1 i  5  i  5

number of clubs selected

non-clubs 32

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem

 n  n      Try to prove it by combinatorial reasoning.  r   n  r Theorem 1.1 The Binomial Theorem

 n k n k ( x  y)     x y k  0  k n

n

binomial coefficient

Select k x’s from (x+y)n 33

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem

7 7 E.g. 1.25 The coefficient of x5y2 in (x+y)7 is       21  5

The coefficient of

a5b2

in

(2a-3b)7

is

 2

 7 5 2 2 (  3 )    5

34

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Corollary 1.1. For any integer n>0, (a)  n   n   n  2 n , and      

 0

 1

 n

(x=y=1)

 n  n  n n  n (b)          ( 1)    0.  0  1  2  n (x=1,y=-1)

35

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem Theorem 1.2 The multinomial theorem For positive integer n,t, the coefficient of x1n1 x2n2 x3n3  xtnt n ( x  x    x ) in the expansion of 1 2 t

n! , n1!n 2 ! nt !

is

where n1  n 2  n t  n .

36

Chapter 1: Fundamental Principles of Counting

1.3 Combinations: The Binomial Theorem 2 3 2

E.g.. 1.26 The coefficient of a b c d

( a  2b  3c  2d  5) 16

5

in

is

16! (1) 2 ( 2) 3 ( 3) 2 ( 2) 5 ( 5) 4 2 !3!2 !5!4 !

37

Chapter 1: Fundamental Principles of Counting

Exercise 1.3. 9,18, 20,21, 30 1.4 Combinations with Repetition: Distributions

E.g. 1.27 7個人買食物,有四種食物可選擇,有幾種買法? first xxx xx

second xxxx

x xxxx

third

fourth

x

xxx

xxx

10!  4  7  1   7!3!  7 

for x

for 38

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions In general, the number of selections, with repetitions, of r objects from n distinct objects are:

( n  r  1)!  n  r  1   r  r !( n  1)! 

39

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.29 Distribute $1000 to 4 persons (in unit of $100) (a) no restriction (b) at least $100 for anyone

 4  10  1    10 

 4  6  1    6 

(c) at least $100 for anyone, Sam has at least $500

 4  2  1  3  2  1  3  1  1  3  0  1          2   2   1   0  40

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.31 A message: 12 different symbols+45 blanks Transmitted through network

at least 3 blanks between consecutive symbols 11  12  1 45  3  11  12 blanks

 (12 !) 

12

  

available positions 41

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.32 Determine all integer solutions to the equation

x1  x2  x3  x4  7, where xi  0 for all

1  i  4.

select with repetition from x1 , x 2 , x 3 , x 4 7 times For example, if x1 is selected twice, then x1  2 in the final solution. Therefore, C(4+7-1,7)=120

42

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions Equivalence of the following: (a) the number of integer solutions of the equation x1  x2    xn  r , xi  0, 1  i  n (b) the number of selections, with repetition, of size r from a collection of size n

(c) the number of ways r identical objects can be distributed among n distinct containers

43

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.34 How many nonnegative integer solutions are there to the inequality x1  x 2  x 6  10 ? It is equivalent to

x1  x2    x6  x7  10, 0  xi , 1  i  6, 0  x7

which can be transformed to y1  y 2  y 6  y 7  9, where y i  x i fo 1  i  6 y 7  x 7  1r an C(7+9d 1,9)=5005

44

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.35 How many there are in the expansion of ( w  x  y  z) 10 ?

Each distinct term is of the form 10   n1 n2 n3 n4   w x y z , where 0  n i for  n1 , n 2 , n 3 , n 4  1  i  4, and n1  n 2  n 3  n 4  10. Therefore, C(4+10-1,10)=286 45

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.36 number of compositions of an positive integer, where the order of the summands is considered relevant.

4=3+1=1+3=2+2=2+1+1=1+2+1=1+1+2=1+1+1+1 4 has 8 compositions. If order is irrelevant, 4 has 5 partitions.

46

Chapter 1: Fundamental Principles of Counting

What about 7? How many compositions? w1  w 2  7 , w i  0 x1  x 2  5, x i  0

 2  5  1    5 

two summands

x1  x 2  x 3  4

 3  4  1    4 

three summands

x1  x 2  x 3  x 4  3

 4  3  1    3 

6 6  2    Ans.: k 0  k  6

four summands 

47

Chapter 1: Fundamental Principles of Counting

1.4 Combinations with Repetition: Distributions E.g. 1.37 For i:=1 to 20 do How many times is this For j:=1 to i do writeln executed? For k:=1 to j do writeln(i*j+k); any i,j,k satisfying 1  k  j  i  20

will do

That is, select 3 numbers, with repetition, from 20 numbers. C(20+3-1,3)=C(22,3)=1540

48

Chapter 1: Fundamental Principles of Counting

Exercise 1.4

11,12,19,20,22,25,28

Supplementary Exercises

21,24,29

49

Chapter 1: Fundamental Principles of Counting Summary select or order r objects from n distinct objects order is repetitions relevant are allowed type of result formula YES

NO

permutation

P( n , r )  n !/ ( n  r ) !, 0 r  n

YES

YES

arrangement

n r , n, r  0

NO

NO

C( n , r )  n !/[ r !( n  r ) !] 0 r  n combination  n  r  1   with repetition  r 

NO

YES

combination

50