- --
`
`. ;.
`ELEMENTS OF DISCRETE MATHEMATICS
`
`•
`
`Oracle-1024 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF DISCRETE MATHEMATICS
`
`Oracle-1024 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`McGRAW-HILL COMPUTER SCIENCE SERIES
`
`RICHARD w. HAMMING, Bell Telephone Laboratories
`EDWARD A. FEIGENBAUM, Stanford University
`
`BELL AND NEWELL: Computer Structures: Readings and Examples
`COLE: Introduction to Computing
`DONOVAN: Systems Programming
`GEAR: Computer Organization and Programming
`GIVONE: Introduction to Switching Circuit Theory
`GOODMAN AND HEDETNIEMI: Introduction to the Design and Analysis of Algorithms
`HAMMING: Computers and Society
`HAMMING: Introduction to Applied Numerical Analysis
`HELLERMAN: Digital Computer System Principles
`HELLERMAN AND CONROY: Computer System Performance
`KAIN: Automata Theory: Machines and Languages
`KATZAN: Microprogramming Primer
`KOHA VI: Switching and Finite Automata Theory
`LIU: Elements of Discrete Mathematics
`LIU: Introduction to Combinatorial Mathematics
`MADNICK AND DONOVAN: Operating Systems
`MANNA: Mathematical Theory of Computation
`NEWMAN AND SPROULL: Principles of Interactive Computer Graphics
`NILSSON: Artificial Intelligence
`RALSTON: Introduction to Programming and Computer Science
`ROSEN: Programming Systems and Languages
`SALTON: Automatic Information Organization and Retrieval
`STONE: Introduction to Computer Organization and Data Structures
`STONE AND SIEWIOREK: Introduction to Computer Organization and Data Structures:
`PDP-11 Edition
`TONGE AND FELDMAN: Computing: An Introduction to Procedures and Procedure(cid:173)
`Followers
`TREMBLAY AND MANOHAR: Discrete Mathematical Structures with Applications to
`Computer Science
`TREMBLA y AND SORENSON: An Introduction to Data Structures with Applications
`TUCKER: Programming Languages
`WATSON: Timesharing System Design Concepts
`WEGNER: Programming Languages, Information Structures, and Machine Organization
`WIEDERHOLD: Database Design
`WINSTON: The Psychology of Computer Vision
`
`Oracle-1024 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF
`DISCRETE
`MATHEMATICS
`
`C. L. Liu
`Department of Computer Science
`University of Illinois at Urbana-Champaign
`
`McGRAW-HILL BOOK COMPANY
`
`New York St. Louis San Francisco Auckland Bogota Diisseldorf
`Johannesburg London Madrid Mexico Montreal New Delhi Panama
`Paris Sao Paulo Singapore Sydney Tokyo Toronto
`
`Oracle-1024 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`ELEMENTS OF DISCRETE MATHEMATICS
`
`Copyright © 1977 by McGraw-Hill, Inc. All rights reserved. Printed in the
`United States of America. No part of this publication may be reproduced,
`stored in a retrieval system, or transmitted, in any form or by any means,
`electronic, mechanical, photocopying, recording, or otherwise, without the
`prior written permission of the publisher.
`
`0DODO8987654
`
`This book was set in Times. The editors were Peter D. Nalle and
`Madelaine Eichberg; the production supervisor was Robert C. Pedersen.
`The drawings were done by Oxford Illustrators Limited.
`R. R. Donnelley & Sons Company was printer and binder.
`
`Library of Congress Cataloging in Publication Data
`
`Liu, Chung Laung.
`Elements of discrete mathematics.
`
`(McGraw-Hill computer science series)
`Includes bibliographies and index.
`1. Combinatorial analysis. 2. Algebra, Abstract.
`I. Title.
`511
`QA164.L57
`ISBN 0-07-038131-3
`
`76-50063
`
`Oracle-1024 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CONTENTS
`
`PREFACE
`
`1 SETS AND PROPOSITIONS
`1.1
`Introduction
`1.2 Combinations of Sets
`1.3 Finite and Infinite Sets
`1.4 Mathematical Induction
`1.5 Principle of Inclusion and Exclusion
`*1.6 Multisets
`1.7 Propositions
`1.8 Remarks and References
`
`2 PERMUTATIONS AND COMBINATIONS
`Introduction
`2.1
`2.2 The Rules of Sum and Product
`2.3 Permutations
`2.4 Combinations
`*2.5 Generation of Permutations and Combinations
`2.6 Remarks and References
`
`3 RELATIONS AND FUNCTIONS
`3.1
`Introduction
`3.2 A Relational Model for Data Banks
`3.3 Properties of Binary Relations
`3.4 Equivalence Relations and Partitions
`3.5 Partial Ordering Relations and Lattices
`3.6 Chains and Antichains
`* All sections marked with an asterisk can be omitted without disrupting the continuity.
`
`IX
`
`1
`1
`4
`8
`11
`15
`20
`21
`31
`
`33
`33
`33
`34
`39
`43
`48
`
`50
`50
`53
`57
`59
`62
`66
`
`V
`
`Oracle-1024 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`vi CONTENTS
`
`*3.7 A Job-scheduling Problem
`3.8 Functions and the Pigeonhole Principle
`3.9 Remarks and References
`
`4 GRAPHS AND PLANAR GRAPHS
`Introduction
`4.1
`4.2 Basic Terminology
`4.3 Multigraphs and Weighted Graphs
`4.4 Paths and Circuits
`4.5 Shortest Paths in Weighted Graphs
`4.6 Eulerian Paths and Circuits
`4.7 Hamiltonian Paths and Circuits
`*4.8 The Traveling Salesperson Problem
`*4.9 Factors of a Graph
`*4.10 Planar Graphs
`4.11 Remarks and References
`
`5 TREES AND CUT-SETS
`5.1 Trees
`5.2 Rooted Trees
`5.3 Path Lengths in Rooted Trees
`5.4 Prefix Codes
`5.5 Binary Search Trees
`5.6 Spanning Trees and Cut-Sets
`5.7 Minimum Spanning Trees
`*5.8 Transport Networks
`5.9 Remarks and References
`
`6 DISCRETE NUMERIC FUNCTIONS AND GENERATING
`FUNCTIONS
`6.1
`Introduction
`6.2 Manipulation of Numeric Functions
`6.3 Generating Functions
`*6.4 Combinatorial Problems
`6.5 Remarks and References
`
`7 RECURRENCE RELATIONS
`Introduction
`7.1
`7.2 Linear Recurrence Relations with Constant Coefficients
`7.3 Solution by the Method of Generating Functions
`7.4 Sorting Algorithms
`7.5 Remarks and References
`
`8 GROUPS AND RINGS
`Introduction
`8.1
`8.2 Groups
`
`68
`72
`80
`
`82
`82
`84
`87
`90
`92
`94
`100
`104
`110
`113
`127
`
`129
`129
`133
`136
`139
`145
`147
`152
`155
`161
`
`169
`169
`170
`174
`179
`182
`
`187
`187
`188
`194
`197
`203
`
`208
`208
`210
`
`Oracle-1024 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`CONTENTS vii
`
`8.3 Subgroups
`8.4 Generators and Evaluation of Powers
`8.5 Cosets and LaGrange's Theorem
`*8.6 Permutation Groups and Burnside's Theorem
`8.7 Codes and Group Codes
`8.8
`Isomorphisms and Automorphisms
`8.9 Homomorphisms and Normal Subgroups
`8.10 Rings, Integral Domains, and Fields
`*8.11 Ring Homomorphisms
`*8.12 Polynomial Rings and Cyclic Codes
`8.13 Remarks and References
`
`9 BOOLEAN ALGEBRAS
`9.1 Lattices and Algebraic Systems
`9.2 Principle of Duality
`9 .3 Basic Properties of Algebraic Systems Defined by Lattices
`9.4 Distributive and Complemented Lattices
`9.5 Boolean Lattices and Boolean Algebras
`9.6 Uniqueness of Finite Boolean Algebras
`9.7 Boolean Functions and Boolean Expressions
`9.8 Propositional Calculus
`9.9 Design and Implementation of Digital Networks
`9.10 Switching Circuits
`9.11 Remarks and References
`
`INDEX
`
`214
`215
`218
`219
`225
`229
`231
`236
`239
`242
`244
`
`251
`251
`254
`256
`259
`262
`263
`265
`269
`273
`275
`282
`
`289
`
`Oracle-1024 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PREFACE
`
`This book presents a selection of topics from set theory, combinatorics,
`graph theory, and algebra which I consider basic and useful to students in
`Applied Mathematics, Computer Science, and Engineering. It is intended to be
`a textbook for a course in Discrete Mathematics at the sophomore-junior
`level, although it can also be used in a freshman level course since the
`presentation does not assume any background beyond high school mathema(cid:173)
`tics. The material in this book can be covered in a one-semester course at a
`rather brisk pace. On the other hand, it is quite possible to omit some of the
`topics for a slower course. A section marked with an asterisk can be omitted
`without disrupting the continuity.
`This book is an outgrowth of a set of lecture notes I wrote for a course I
`taught in the Department of Computer Science at the University of Illinois at
`Urbana-Champaign. I hope it is not only a record of what I covered in the
`course but also a reflection of how I lectured the material in the classroom. I
`have tried to be rigorous and precise in presenting the mathematical concepts
`and, in the meantime, to avoid complicated formalisms and notations. As a rule
`I would not state a definition or a fact if I could not illustrate the utilization of
`the definition or the fact in some meaningful way later on. Consequently, it is
`quite possible that I have omitted some "important" definitions or facts in this
`book. I trust, however, that the students will be quite capable of looking them
`up somewhere else when such definitions and facts are needed. I have
`attempted to teach my students some useful mathematics in an interesting and
`exciting way. I hope that I have demonstrated to them how mathematics can be
`applied to solve nontrivial real life problems. Furthermore, I hope that
`my students not only learned in the course some powerful mathematical tools
`but also developed their ability to perceive, to formulate, and to solve
`mathematical problems. I have tried to bring in an algorithmic point of view in
`the treatment of several topics, although I decided not to include explicit
`
`ix
`
`Oracle-1024 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`x PREFACE
`
`computer programs, mainly because of time consideration. I hope that some of
`these personal views and tastes can be shared to some extent by the instructor
`using this book.
`I would like to thank James N. Synder, my department head, for his
`encouragement and support; Murray Edelberg, Jane W. S. Liu, and Andrew H.
`Sherman for their careful review of the manuscript; Donald K. Friesen for his
`contribution to the preparation of the Instructor's Manual; and Edward M.
`Reingold and F. Frances Yao for their many helpful suggestions. Several years
`ago, I had an opportunity to serve on a panel on the impact of computing on
`mathematics sponsored by the Committee on the Undergraduate Program in
`· Mathematics of the Mathematical Association of America. I was greatly
`benefited by the panel's discussion on the teaching of discrete mathematics,
`and I am much indebted to the members of the panel. I also thank Glenna
`Gochenour, Connie Nosbisch, Judy Watkins, and June Wingler for their typing
`and editorial assistance. Finally, thanks to Kathleen D. Liu for her assistance in
`the preparation of the index.
`There is a certain amount of overlap between this book and the book
`Introduction to Combinatorial Mathematics I wrote a few years ago. In a
`number of instances, I follow quite closely the presentation in Introduction to
`Combinatorial Mathematics.
`
`C. L. Liu
`
`Oracle-1024 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PERMUTATIONS AND COMBINATIONS
`
`CHAPTER
`
`TWO
`
`2.1 INTRODUCTION
`
`In Sec. 1.5 we discussed some results on the size of finite sets. We shall present
`in this chapter some further results along this line. For example, let A be a
`finite set of size n. We might wish to know the number of distinct subsets of the
`set A, that is, the size of the power set of A, @>(A). Furthermore, among all
`subsets of A, we might want to know the number of subsets that are of size k.
`For example, let A be a set of ten senators. The number of subsets in @>(A),
`which is equal to 210
`, is the number of different committees the senators can
`form [including a committee with no members, corresponding to the empty set
`in @>(A)]. Moreover, the number of subsets of size 6 in @>(A), which is equal to
`210, is the number of different 6-member committees they can form. In this
`chapter, we shall discuss these and related problems in the context of
`permutations and combinations of objects.
`
`2.2 THE RULES OF SUM AND PRODUCT
`
`By an event we shall mean something that takes place. Placing a ball in a box,
`selecting a representative among a group of students, assigning offices to
`professors, and placing bets in a horse race are all examples of events. An event
`can occur in one or more ways. For example, in the case of placing a ball in one
`of several boxes, the number of ways of placing the ball is equal to the number
`of boxes available. When we consider the occurrence of several events, we
`shall follow the rules stated below:
`
`33
`
`Oracle-1024 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`34 ELEMENTS OF DISCRETE MATHEMATICS
`
`Rule of product. If one event can occur in m ways and another event can occur
`in n ways, then there are m x n ways in which these two events can occur
`together.
`Rule of sum. If one event can occur in m ways and another event can occur in
`n ways, then there are m + n ways in which exactly one of these two
`events can occur.
`
`For example, if there are 52 ways to select a representative for the junior
`class and 49 ways to select a representative for the senior class, then according
`to the rule of product, there will be 52 x 49 ways to select the representatives
`for both the junior and senior classes. On the other hand, according to the rule
`of sum, there will be 52 + 49 ways to select a representative for either the junior
`or the senior class. As another example, suppose there are seven different
`courses offered in the morning and five different courses offered in the
`afternoon. There will be 7 x 5 choices for students who want to enroll in one
`course in the morning and one in the afternoon. On the other hand, they will
`have 7 + 5 choices if they want to enroll in only one course.
`
`2.3 PERMUTATIONS
`
`Consider the simple problem of placing three balls colored red, blue, and white
`in ten boxes numbered 1, 2, 3, ... , 10. We want to know the number of distinct
`ways in which the balls can be placed in the boxes, if each box can hold only
`one ball. Let us place the balls one at a time, beginning with the red ball, then
`the blue ball, and then the white ball. Since the red ball can be placed in any one
`of the ten boxes, the blue ball can be placed in any one of the nine remaining
`boxes, and the white ball can be placed in any one of the eight remaining boxes,
`the total number of distinct ways to place these balls is 10 x 9 x 8 = 720.
`The result of this numerical example can be generalized immediately:
`Suppose we are to place r distinctly colored balls in n distinctly numbered
`boxes with the condition that a box can hold only one ball. Since the first ball
`can be placed in any one of then boxes, the second ball can be placed in any
`one of the remaining (n - 1) boxes, ... , and the rth ball can be placed in any
`one of the remaining (n - r + 1) boxes, the total number of distinct ways to
`place the balls is
`
`n (n -
`
`l)(n - 2) · · · (n -
`
`r + 1)
`
`which can also be written ast
`
`n!
`(n - r)!
`
`We use the notation P(n, r) for the quantity n(n -
`
`l)(n - 2) • • • (n -
`
`r + 1).
`
`t n ! reads "n factorial" and is defined to be n (n -
`convention that O ! is equal to 1.
`
`l)(n - 2) · · · 2 x 1. We also have the
`
`Oracle-1024 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PERMUTATIONS AND COMBINATIONS 35
`
`The following examples show that the problem of placing balls in boxes is
`not as uninteresting as it might seem.
`
`Example 2.1 In how many ways can three examinations be scheduled
`within a five-day period so that no two examinations are scheduled in the
`same day? Considering the three examinations as distinctly colored balls
`and the five days as distinctly numbered boxes, we obtain the result
`0
`5 X4X3 =60.
`
`Example 2.2 Suppose that we have seven rooms and want to assign four of
`them to four programmers as offices and use the remaining three rooms for
`computer terminals. The assignment can be made in 7 x 6 x 5 x 4 = 840
`different ways because we can view the problem as that of placing four
`distinct balls (the programmers) into seven distinct boxes (the rooms), with
`the three boxes that are left empty being the rooms for computer terminals.
`(We assume that the programmers are distinct but that all computer
`terminals are identical.)
`□
`
`A problem equivalent to placing balls in boxes is that of arranging or
`permuting distinct objects. By permuting r of n distinct objects, we mean to
`arrange r of these n objects in some order. For example, there are six ways to
`permute two of the three objects a, b, c. They are ab, ba, ac, ca, be, and cb.
`Since to arrange r of n objects amounts to filling r positions with r of the n
`objects, there are n choices of an object for the first position, n - 1 choices of
`an object (from the n - 1 remaining objects) for the second position, ... , and
`n - r + 1 choices of an object (from then - r + 1 remaining objects) for the rth
`position. Consequently, there are n(n -1) · · · (n - r + 1) ways to arranger of n
`objects in order. t
`Consider the following examples:
`
`Example 2.3 Let us determine the number of four-digit decimal numbers
`that contain no repeated digits. Since this is a problem of arranging four of
`the ten digits 0, 1, 2, ... , 9, the answer is P(l0, 4) = 5040. Among these 5040
`numbers, 9 x 8 x 7 = 504 of them have a leading 0. Consequently, 5040-
`504 = 4536 of them do not have a leading 0. The result can also be computed
`as
`9 X 9 X 8 X 7 = 4536
`
`using the argument that the first digit can be any one of the nine digits 1,
`2, ... , 9, the second digit can be any of the nine remaining digits, and so on.
`D
`
`t A slightly different point of view, which might cause some initial confusion but will prove to
`be useful eventually, is to consider the problem as that of placing balls in boxes. Consider n boxes
`corresponding to the n objects, and r balls corresponding to the r positions in the arrangement.
`The placement of a ball in a certain box is equivalent to putting the object corresponding to the box
`in a position corresponding to the ball in an arrangement. Consequently, the number of ways to
`permute r of n objects is P(n, r).
`
`Oracle-1024 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`36 ELEMENTS OF DISCRETE MATHEMATICS
`
`Example 2.4 We note that the number of ways in which we can make up
`strings of four distinct letters followed by three distinct digits is
`P(26, 4) x P(l0, 3) = 258,336,000
`
`□
`
`Let us return to the problem of placing three distinctly colored balls into
`ten distinctly numbered boxes. Suppose a box can hold as many balls as we
`wish. Since the red ball can be placed in any one of the ten boxes, as can the
`blue ball, and as can the white ball, the total number of ways of placement is
`10 X 10 X 10 = 1000
`
`In general, there are n r ways to place r colored balls into n numbered
`boxes if a box can hold as many balls as we wish.
`We consider now some other examples:
`
`Example 2.5 If we are to schedule three examinations within a five-day
`period with no restriction on the number of examinations scheduled each
`day, the total number of ways is 53 = 125.
`□
`
`Example 2.6 Let us determine the number of subsets of a set A whose size
`is r. Consider the problem of placing the r elements of A in two boxes.
`Corresponding to each placement, we can define a subset of A by taking
`the elements placed in box 1 and discarding the elements placed in box 2.
`Since there are 2r ways to place the r elements, there are 2r subsets in
`q>(A).
`□
`
`Similarly, in terms of permutation of objects, we say that, if there are n
`distinct kinds of objects with an infinite supply of each kind, then there are n r
`ways to arrange r of these n kinds of objects, because there are n choices of an
`object for the first position, n choices of an object for the second position, ... ,
`and n choices of an object for the rth position. For example, there are 104
`- P(lO, 4) = 4960 of them
`four-digit decimal sequences. Consequently, 104
`contain one or more repeated digits.
`Example 2.7 We observe first that there are r r-digit binary sequences. We
`now ask among the 2r r-digit binary sequences how many of them have an
`even number of zeros? We can pair off these binary sequences such that
`two sequences in a pair differ only in the rth digits. Clearly, one of the two
`sequences in a pair has an even number of zeros and · the other has an odd
`number of zeros. It follows that there are½· 2r r-digit binary sequences that
`contain an even number of zeros. We now ask for the number of r-digit
`quintary sequences (sequences made up of the digits 0, 1, 2, 3, 4) that
`contain an even number of zeros. We note that among the Y r-digit
`quintary sequences, there are 3r of them that contain only the digits 2, 3,
`and 4. These sequences are, of course, counted as sequences containing an
`even number of zeros. The remaining Y - 3r sequences can be divided into
`
`Oracle-1024 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PERMUTATIONS AND COMBINATIONS 37
`
`groups according to the patterns of 2s, 3s, and 4s in the sequences. (For
`instance, all sequences of the form 23xx 344xx 2xxx will be in one group,
`where each x is either a 0 or a 1.) Since half of the sequences in each group
`has an even number of zeros, the total number of r-digit quintary
`sequences with an even number of zeros is 3' + ½(5' - 3').
`□
`
`Example 2.8 We now give an example of the application of the principle of
`inclusion and exclusion. Suppose we want to know the number of r-digit
`quintary sequences that contain at least a 0, a 1, and a 2. Let A I be the set of
`r-digit quintary sequences in which the digit 0 is missing, A2 be the set of
`r-digit quintary sequences in which the digit 1 is missing, and A3 be the set
`of r-digit quintary sequences in which the digit 2 is missing. Then
`A1 U A2 U A3 is the set of r-digit quintary sequences in which one or more of
`the three digits 0, 1, 2 is missing. Since
`IA1I = IA2I = IA31 = 4'
`IA1 n A2I = IA, n A31 = IA2n A31 = 3'
`IA1 n A2n A31 = 2'
`
`we obtain
`
`IA1 u A2 u A31 = 4' + 4' + 4' - 3' - 3' - 3' + 2'
`= 3 · 4' - 3 · 3' + 2'
`Consequently, the number of r-digit quintary . sequences that contain at
`least a 0, a 1, and a 2 is
`
`5' - 3 · 4' + 3 · 3' - 2'
`
`□
`
`Let us consider the problem of placing four balls, two red, one blue, and one
`white, in ten numbered boxes. Suppose we repaint the two red balls with two
`shades of red, light and dark, so that they become distinguishable. The number of
`ways to place these balls in the ten boxes is then P(l0, 4) = 5040. Among these
`5040 placements, let us consider the placement in which the light red ball is in the
`first box, the dark red ball is in the second box, the blue ball is in the third box, and
`the white ball is in the fourth box, and the placement in which the dark red ball is
`in the first box, the light red ball is in the second box, the blue ball is in the third
`box, and the white ball is in the fourth box. If we do not distinguish between the
`two shades of red, that is, if the two red balls are indistinguishable, these two
`ways of placement actually become one. Indeed, the 5040 placements can be
`paired off in a similar way so that every pair of placements becomes one when we
`do not distinguish the two shades of red. Consequently, there are 5°t0 = 2520 ways
`to place two red balls, one blue ball, and one white ball in ten numbered boxes.
`Following the same argument, we see that the number of ways of placing three
`red balls, one blue ball, and one white ball in ten numbered boxes is
`P(lO, 5) = 5040
`3!
`
`Oracle-1024 p. 15
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`38 ELEMENTS OF DISCRETE MATHEMATICS
`
`because each way to place three indistinguishable red balls, one blue ball, and
`one white ball corresponds to 3 ! ways of placing three distinguishable red balls,
`one blue ball, and one white ball.
`We derive now a general formula for the number of ways to placer colored
`balls inn number boxes, where q1 of these balls are of one color, q2 of them are
`of a second color, ... , and qt of them are of a tth color. We note that a placement
`of the r balls is not changed by rearranging the q I balls of the same color among
`the boxes in which they are placed, or rearranging the q2 balls of the same color
`among the boxes in which they are placed, ... , or rearranging the qt balls of the
`same color among the boxes in which they are placed. On the other hand, if the r
`balls were distinctly colored, any rearrangement will yield a different placement.
`It follows that each way to place the r not completely distinctly colored balls
`corresponds to q1 !q2! · · · q, ! ways to placer distinctly colored balls. Since there
`are P(n, r) ways to placer distinctly colored balls inn numbered boxes, the total
`number of ways to placer colored balls inn numbered boxes, where q1 of these
`balls are of one color, q2 of them are of a second color, ... , and q, of them are of a
`tth color, is
`
`P(n, r)
`
`(2.1)
`
`Example 2.9 We observe that the number of ways to paint 12 offices so that 3
`of them will be painted green, 2 of them will be painted pink, 2 of them will be
`painted yellow, and the remaining ones will be painted white is
`
`12!
`3! 2! 2! 5! = 166,320
`
`In terms of arrangement of objects, we say that there are
`
`n!
`
`□
`
`(2.2)
`
`ways to arrange n objects, where q1 of them are of one kind, q2 of them are of a
`second kind, ... , and q, of them are of a tth kind. Again, if the n objects were all
`distinct, there are n ! ways to arrange them. On the other hand, in an arrangement
`of objects that are not completely distinct, permuting the objects of the same
`kind among themselves will not change the arrangement. We thus obtain the
`formula in (2.2).
`
`Example 2.10 We note that the number of different messages that can be
`represented by sequences of three dashes and two dots is
`
`5!
`3! 2! = 10
`
`□
`
`Oracle-1024 p. 16
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PERMUTATIONS AND COMBINATIONS 39
`
`2.4 COMBINATIONS
`
`Consider now the problem of placing three balls, all of them colored red, in ten
`box.es that are numbered 1, 2, 3, ... , 10. We want to know in how many ways can
`the balls be placed, if each box can hold only one ball. According to (2.1) the
`answer is
`
`10X9X8
`3!
`
`In general, the number of ways of placing r balls of the same color in n numbered
`boxes is
`
`n (n -
`
`The quantity
`
`l)(n - 2) · · · (n -
`r!
`'( n ~ )' is also denoted C(n, r).
`r. n r.
`Let us consider some examples:
`
`r + 1)
`
`n !
`= - - - -
`r!(n-r)!
`
`Example 2.11 Suppose a housekeeper wants to schedule spaghetti dinners
`three times each week. Imagine the spaghetti dinners as three balls and the
`seven days in the week as seven boxes; then the number of ways of
`scheduling is
`
`7!
`3! 4! = 35
`
`□
`
`Example 2.12 We note that there are C(32, 7) binary sequences of length 32
`in each of which there are exactly seven ls, because we can view the
`problem as placing seven ls in 32 numbered boxes (and then fill the empty
`boxes with Os).
`□
`
`A problem equivalent to placing r indistinguishable balls in n numbered
`boxes is that of selection of r objects from n distinct objects. If we are to select r
`objects from n distinct objects, we can imagine the n objects as boxes and mark
`the selected objects with r identical markers, the balls. Consequently, the
`number of ways to select r objects from n distinct objects is also C(n, r).
`According to the definition of C(n, r) it is clear that C(n, r) = C(n, n - r) .
`There is also a simple combinatorial argument that confirms this result: since to
`select r objects from n objects is the same as to pick out the n - r objects that
`are not to be selected, we have C(n, r) = C(n, n - r).
`
`Example 2.13 Among 11 senators there are C(l l, 5) = 462 ways to select a
`committee of 5 members. Moreover, there are C(lO, 4) = 210 ways to select
`a committee of five members so that a particular senator, senator A, is
`always included, and there are C(lO, 5) = 252 ways to select a committee of
`five members so that senator A is always excluded. We now ask in how
`
`Oracle-1024 p. 17
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`40 ELEMENTS OF DISCRETE MATHEMATICS
`
`many ways we can select a committee of five members so that at least one of
`· senator A and senator B will be included. The number of selections
`including both senator A and senator B is C(9, 3) = 84. The number of
`selections including senator A but excluding senator Bis C(9, 4) = 126, as is
`the number of selections including senator B but excluding senator A.
`Consequently, the total number of ways of selection is
`84+ 126+ 126 = 336
`Alternatively, since the total number of committees excluding both A and B
`is C(9, 5), the total number of ways of selection is
`C(l l, 5)- C(9, 5) = 462- 126 = 336
`The problem can also be solved by applying the principle of inclusion
`and exclusion. Among the 462 ways of selecting 5 senators, let A1 and A2 be
`the set of ways of selection that include senator A and senator B,
`respectively. Since
`
`!Ail= C(lO, 4) = 210
`IA2I = C(lO, 4) = 210
`IA1 n A2I = C(9, 3) = 84
`
`IA1 u A2I = 210+210-84 = 336
`
`D
`
`it follows that
`
`If no three diagonals of a convex decagon meet at the same
`Example 2.14
`point inside the decagon, into how many line segments are the diagonals
`divided by their intersections? First of all, the number of diagonals is equal
`to
`
`C(lO, 2)-10 = 45 - 10 = 35
`as there are C(lO, 2) straight lines joining the C(lO, 2) pairs of vertices, but
`10 of these 45 lines are the sides of the decagon. Since for every four vertices
`we can count exactly one intersection between the diagonals, as Fig. 2.1
`sh()WS (the decagon is convex), there are a total of C(lO, 4) = 210
`intersections between the diagonals. Since a diagonal is divided into k + 1
`
`\
`\
`\
`\
`\
`\
`\
`
`----,------
`\
`\
`\
`
`Figure 2.1
`
`Oracle-1024 p. 18
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`PERMUTATIONS AND COMBINATIONS 41
`
`straight-line segments when there are k intersecting points lying on it, and
`since each intersecting point lies on two diagonals, the total number of
`straight-line segments into which the diagonals are divided is 35 + 2 x 210 =
`455.
`□
`
`Suppose we are to place r balls of the same color in n numbered boxes,
`allowing as many balls in a box as we wish. The number of ways to place the balls
`IS
`
`(n + r -1)!
`'( _ 1)' = C(n + r -
`.
`r. n
`
`l, r)
`
`An easy way to see this result is to consider the problem of arranging n + 1 ls and
`r Os with a 1 at the beginning and a 1 at the end of each arrangement. If we
`consider the ls as interbox partitions and the Os as balls, then every snch
`arrangement corresponds to a way of placing r balls of the same color in n
`numbered boxes. For example, let n = 5 and r = 4, the sequence
`
`1011001101
`
`can be viewed as a placement of four balls in five boxes having one ball in the first
`box, no ball in the second box, two balls in the third box, no ball in the fourth box,
`and one ball in the fifth box. According to (2.1), the number of ways of arranging
`n + 1 1 s and r Os with 1 s at both ends of an arrangement is
`
`(n+r-1)!
`(n-l)!r!
`
`We note that the problem of selecting r objects from n distinct objects,
`allowing repeated selections, can be viewed as that of using r identical markers
`to mark the n distinct objects while each object can be marked with arbitrarily
`many markers. Therefore, the number of ways to select r objects from n distinct
`objects, allowing repeated selections, is
`
`(n+r-1)!
`'( -l)' =C(n+r-1,r)
`r. n
`.
`
`(2.3)
`
`Consider the following examples:
`
`Example 2.15 A domino is made up of two squares each of which is marked
`with one, two, three, ... , or six spots, or is left blank. We note that there are
`28 different dominoes in a set, because the number of distinct dominoes is
`the same as the number of ways of selecting two subjects from the seven
`objects "one," "two," "three," ... , "six," and "blank," with repetitions
`allowed. Thus, according to (2.3), the number of distinct dominoes is
`
`C(7 + 2-1, 2) = C(8, 2) = 28
`
`□
`
`Oracle-1024 p. 19
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`42 ELEMENTS OF DISCRETE MATHEMATICS
`
`Example 2.16 We note that when three dice are rolled, the number of
`different outcomes is
`
`C(6 + 3- 1, 3) = C(8, 3) = 56
`
`because rolling three dice is equivalent to selecting three numbers from the
`six numbers 1, 2, 3, 4, 5, 6 with repetitions allowed.
`□
`
`Example 2.17 We ask for the number of different paths for a rookt to move
`from the southwest corner of a chessboard to the northeast corner by
`moving eastward and northward only. If we let a O denote an eastward step
`and a 1 denote a northward step, then the number of paths is equal to the
`number of ways of arranging seven Os and seven ls, which is
`
`14!
`7! 7! = 3432
`
`We ask now how many of these paths consist of four eastward moves
`and three northward moves. (By an eastward move we mean a certain
`number of consecutive eastward steps. A northward move is defined
`similarly.) The number of ways of making up a path with four eastward
`moves is the same as that of placing seven indistinguishable balls in four
`distinct boxes with no box left empty.